_____
 ____  __
  ______     _______
    ____________________
           _______________
          _________________
          ________________
           ______________
            ____________
            __________
            ________
            _______
            _____
            _____
            ___
            ___
            ___


  Chair


Sergio Rajsbaum, Compaq CRL/UNAM, USA/Mexico

[Top] [Home] [All LATIN Chairs]

  Program Committee


Amihood Amir, Bar-Ilan Univ., Israel
Mauricio Ayala Rincón, Brazilia Univ., Brazil
Ricardo Baeza-Yates, Univ. of Chile, Chile
Michael Bender, SUNY Stony Brook, USA
Leopoldo Bertossi, Carleton Univ., Canada
Allan Borodin, Univ. of Toronto, Canada
Bernard Chazelle, Princeton Univ., USA
Lenore Cowen, Tufts Univ., USA
Volker Diekert, Stuttgart, Germany
Javier Esparza, Univ. of Edimburgh, Scotland
Martin Farach-Colton, Rutgers Univ., USA
David Fernandez-Baca, Iowa State Univ., USA
Esteban Feuerstein, Univ. of Buenos Aires, Argentina
Juan Garay, Bell Labs, USA
Oscar H. Ibarra, UC Santa Barbara, USA
Marcos Kiwi, Univ. of Chile, Chile
Yoshiharu Kohayakawa, Univ. de São Paulo, Brasil
Elias Koutsoupias, UC Los Angeles, USA
Evangelos Kranakis, Carleton Univ., Canada
Daniel Leivant, Indiana Univ., USA
Alex Lopez-Ortiz, Univ. of Waterloo, Canada
Yoram Moses, Technion, Israel
Daniel Panario, Carleton Univ., Canada
Sergio Rajsbaum (Chair), Compaq CRL and UNAM, Mexico
Alex Russell, Univ. Connecticut, USA
Maria José Serna, Univ. Politècnica de Catalunya, Spain
Gadiel Seroussi, Hewlet Packard, USA
Igor Shparlinski, Macquarie Univ., Australia
Imre Simon, Univ. de São Paulo, Brasil
Janos Simon, Univ. of Chicago, USA

[Top] [Home] [All LATIN PCs]

  Organizing Committee


Edgar Chávez (chair), Universidad Michoacana, México
Sergio Rajsbaum, Compaq/UNAM, USA/México

[Top] [Home] [All LATIN Org. Committees]

  Invited Speakers


Jennifer T. Chayes (Microsoft Research), Phase Transitions in Computer Science
Phase transitions are familiar phenomena in physical systems. But they also occur in many probabilistic and combinatorial models, including random versions of some classic problems in theoretical computer science.

In this talk, I will discuss phase transitions in several systems, including the random graph — a simple probabilistic model which undergoes a critical transition from a disordered to an ordered phase; k-satisfiability — a canonical model in theoretical computer science which undergoes a transition from solvability to insolvability; and optimum partitioning — a fundamental problem in combinatorial optimization, which undergoes a transition from existence to non-existence of a perfect optimizer.

Technically, phase transitions only occur in infinite systems. However, real systems and the systems we simulate are large, but finite. Hence the question of finite-size scaling: Namely, how does the transition behavior emerge from the behavior of large, finite systems? Results on the random graph, satisfiability and optimum partitioning locate the critical windows of these transitions and establish interesting features within these windows.

No knowledge of phase transitions will be assumed in this talk

Christos H. Papadimitriou (U. California, Berkeley), The Internet, the Web, and Algorithms
The Internet and the worldwide web, unlike all other computational artifacts, were not deliberately designed by a single entity, but emerged from the complex interactions of many. As a result, they must be approached very much the same way that cells, galaxies or markets are studied in other sciences: By speculative (and falsifiable) theories trying to explain how selfish algorithmic actions could have led to what we observe. I present several instances of recent work on this theme, with several collaborators
Joel Spencer (Courant Institute), Erdős Magic
The Probabilistic Method is a lasting legacy of the late Paul Erdős. We give two examples — both problems first formulated by Erdős in the 1960s with new results in the last few years and both with substantial open questions. Further in both examples we take a Computer Science vantagepoint, creating a probabilistic algorithm to create the object (coloring, packing respectively) and showing that with positive probability the created object has the desired properties.

Given \(m\) sets each of size \(n\) (with an arbitrary intersection pattern) we want to color the underlying vertices Red and Blue so that no set is monochromatic. Erdős showed this may always be done if \(m< 2(n-1)\), we give a recent argument of Srinivasan and Radhukrishnan that extends this to \(m < c 2n\sqrt{n/\ln n}\). One first colors randomly and then recolors the blemishes with a clever random sequential algorithm.

In a universe of size \(N\) we have a family of sets, each of size \(k\), such that each vertex is in \(D\) sets and any two vertices have only \(o(D)\) common sets. Asymptotics are for fixed \(k\) with \(N,D\). We want an asymptotic packing, a subfamily of \(N/k\) disjoint sets. Erdős and Hanani conjectured such a packing exists (in an important special case of asymptotic designs) and this conjecture was shown by Rödl. We give a simple proof of the speaker that analyzes the random greedy algorithm.

Jorge Urrutia (UNAM), Open Problems in Computational Geometry
In this paper we present a collection of problems which have defied solution for some time. We hope that this paper will stimulate renewed interest in these problems, leading to solutions to at least some of them.
Umesh V. Vazirani (U. California, Berkeley), Quantum Algorithms
Quantum computers are the only model of computing to credibly violate the modified Church-Turing thesis, which states that any reasonable model of com-putation can be simulated by a probabilistic Turing Machine with at most poly-nomial factor simulation overhead. This is dramatically demonstrated by Shor’s polynomial time algorithms for factorization and discrete logarithms [13]. Shor’s algorithm, as well as the earlier algorithm due to Simon [12] can both be cast into the general framework of the hidden subgroup problem (see for example [10]). Two recent papers [11],  [9] study how well this framework extends to solving the hidden subgroup problem for non-abelian groups (which includes the graph iso-morphism problem).

Grigni, M., Schulman, S., Vazirani, M., Vazirani, U.. Quantum Mechnical Algorithms for the Non beli n Hidden Subgroup Problem. In: Proceedings of the Thirty-third Annual ACM Symposium on the Theory of Computing Crete, Greece, 2001.

L. Hales and S. Hallgren. Quantum Fourier S mpling Simplified. In: Proceedings of the Thirty-first Annual ACM Symposium on the Theory of Computing pages 330–338,Atlanta,Georgia, 1–4 May 1999.

Hallgren, S., Russell, A., T-Shma, A.. Normal subgroup reconstruction and quantum computation using group representations. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing 627–635, 2000.

D. Simon. On the power of quantum computation. In: Proc. 35th Symposium on Foundations of Computer Science (FOCS), 1994.

Shor P. W.. Polynomial-time algorithms for prime factorization and discrete alogarithms on a quantum computer. SIAM J. Comp., 26 No.5, pp 1484–1509, October 1997. Mihalis Yannakakis (Avaya Laboratories), Testing and Checking of Finite State Systems

Finite state machines have been used to model a wide variety of systems, including sequential circuits, communication protocols, and other types of reactive systems, i.e., systems that interact with their environment. In testing problems we are given a system, which we may test by providing inputs and observing the outputs produced.

The goal is to design test sequences so that we can deduce desired information about the given system under test, such as whether it implements correctly a given specification machine (conformance testing), or whether it satisfies given requirement properties (black-box checking).

In this talk we will review some of the theory and algorithms on basic testing problems for systems modeled by different types of finite state machines. Conformance testing of deterministic machines has been investigated for a long time; we will discuss various efficient methods. Testing of nondeterministic and probabilistic machines is related to games with incomplete information and to partially observable Markov decisions processes.

The verification of properties for finite state systems with a known structure (i.e., “white box” checking) is known as the model-checking problem, and has been thoroughly studied for many years, yielding a rich theory, algorithms and tools. Black-box checking, i.e., the verification of properties for systems with an unknown structure, combines elements from model checking, conformance testing and learning.


[Top] [Home] [All LATIN Inv. Speakers]

  Papers


Jennifer Chayes, Phase Transitions in Computer Science. [Bibtex]

Christos Papadimitriou, The Internet, the Web, and Algorithms. [Bibtex]

Joel Spencer, Erdős Magic. [Bibtex]

Jorge Urrutia, Open Problems in Computational Geometry. [Bibtex]

Umesh V. Vazirani, Quantum Algorithms. [Bibtex]

Mihalis Yannakakis, Testing and Checking of Finite State Systems. [Bibtex]

Fabrizio Luccio and Linda Pagli, From Algorithms to Cryptography. [Bibtex]

Eric Goubault and Martin Raussen, Dihomotopy as a Tool in State Space Analysis. [Bibtex]

Abdullah N. Arslan and Ömer Egecioglu, Algorithms for Local Alignment with Length Constraints. [Bibtex]

Marília D. V. Braga and Joao Meidanis, An Algorithm That Builds a Set of Strings Given Its Overlap Graph. [Bibtex]

Christiane Frougny, Conversion between Two Multiplicatively Dependent Linear Numeration Systems. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, Star Height of Reversible Languages and Universal Automata. [Bibtex]

Howard Straubing and Denis Thérien, Weakly Iterated Block Products of Finite Monoids. [Bibtex]

Maria Isabel Gonzalez Vasco, Mats Näslund and Igor Shparlinski, The Hidden Number Problem in Extension Fields and Its Applications. [Bibtex]

Theodoulos Garefalakis, The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves. [Bibtex]

Rod Canfield, Sylvie Corteel and Pawel Hitczenko, Random Partitions with Non Negative rth Differences. [Bibtex]

Frédérique Bassino, Beta-Expansions for Cubic Pisot Numbers. [Bibtex]

Prosenjit Bose and Qingda Wang, Facility Location Constrained to a Polygonal Domain. [Bibtex]

Hanno Lefmann and Niels Schmitt, A Deterministic Polynomial Time Algorithm for Heilbronn's Problem in Dimension Three. [Bibtex]

Edgar Chávez and Gonzalo Navarro, A Metric Index for Approximate String Matching. [Bibtex]

Wojciech Rytter, On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm. [Bibtex]

Derek G. Corneil, Feodor F. Dragan and Ekkehard Köhler, On the Power of BFS to Determine a Graphs Diameter. [Bibtex]

Martín Matamala, Erich Prisner and Ivan Rapaport, \(k\)-pseudosnakes in Large Grids. [Bibtex]

Tiziana Calamoneri and Rossella Petreschi, \(L(2, 1)\)-Coloring Matrogenic Graphs. [Bibtex]

Ruy Luiz Milidiú, Artur Alves Pessoa and Eduardo Sany Laber, Pipeline Transportation of Petroleum Products with No Due Dates. [Bibtex]

Enrico Pontelli and Desh Ranjan, Ancestor Problems on Pure Pointer Machines. [Bibtex]

Renato Carmo, Jair Donadelli, Yoshiharu Kohayakawa and Eduardo Sany Laber, Searching in Random Partially Ordered Sets. [Bibtex]

Brett Stevens and Eric Mendelsohn, Packing Arrays. [Bibtex]

Michael Drmota and Wojciech Szpankowski, Generalized Shannon Code Minimizes the Maximal Redundancy. [Bibtex]

S. Muthukrishnan and Cenk Sahinalp, An Improved Algorithm for Sequence Comparison with Block Reversals. [Bibtex]

Blaise Genest and Anca Muscholl, Pattern Matching and Membership for Hierarchical Message Sequence Charts. [Bibtex]

Jianer Chen and Iyad Kanj, Improved Exact Algorithms for MAX-SAT. [Bibtex]

Steffen van Bakel and Mariangiola Dezani-Ciancaglini, Characterising Strong Normalisation for Explicit Substitutions. [Bibtex]

Roel Bloo, Fairouz Kamareddine, Twan Laan and Rob Nederpelt, Parameters in Pure Type Systems. [Bibtex]

Rusins Freivalds and Carl H. Smith, Category, Measure, Inductive Inference: A Triality Theorem and Its Applications. [Bibtex]

Frédéric Herbreteau, Franck Cassez, Alain Finkel, Olivier Roux and Grégoire Sutre, Verification of Embedded Reactive Fiffo Systems. [Bibtex]

Alejandro Hevia and Marcos Kiwi, Electronic Jury Voting Protocols. [Bibtex]

Gonzalo Tornaría, Square Roots Modulo \(p\). [Bibtex]

Goran Konjevod, Soohyun Oh and Andréa W. Richa, Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities. [Bibtex]

Jean-Christophe Dubacq and Véronique Terrier, Signals for Cellular Automata in Dimension 2 or Higher. [Bibtex]

Paolo Boldi and Sebastiano Vigna, Holographic Trees. [Bibtex]

Prosenjit Bose, Luc Devroye, William S. Evans and David G. Kirkpatrick, On the Spanning Ratio of Gabriel Graphs and \(\beta\)-skeletons. [Bibtex]

Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison and Godfried T. Toussaint, In-Place Planar Convex Hull Algorithms. [Bibtex]

Michael A. Bender and Martin Farach-Colton, The Level Ancestor Problem Simplified. [Bibtex]

Claudson F. Bornstein and Santosh Vempala, Flow Metrics. [Bibtex]

Howard Straubing, On Logical Descriptions of Regular Languages. [Bibtex]

Mario Szegedy and Xiaomin Chen, Computing Boolean Functions from Multiple Faulty Copies of Input Bits. [Bibtex]

Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita, Inapproximability Results on Stable Marriage Problems. [Bibtex]

Hadas Shachnai and Tami Tamir, Tight Bounds for Online Class-Constrained Packing. [Bibtex]

R. Sai Anand and Thomas Erlebach, On-line Algorithms for Edge-Disjoint Paths in Trees of Rings. [Bibtex]

James Abello, Mauricio G. C. Resende and Sandra Sudarsky, Massive Quasi-Clique Detection. [Bibtex]

Jochen Alber and Rolf Niedermeier, Improved Tree Decomposition Based Algorithms for Domination-like Problems. [Bibtex]



[Top] [Home] [All LATIN Papers]

  Sponsors


Universidad Michoacana de San Nicolás de Hidalgo, México
Sociedad Chilena de Ciencias de la Computación (SCCC)
Sociedad Mexicana de Ciencias de la Computación
European Association for Theoretical Computer Science (EATCS)
Compaq

[Top] [Home] [All LATIN Sponsors]

  Location


Loct'2002

The conference was held at the Oasis Hotel, Cancun, Mexico.

Cancun is located off the northeast point of Mexico's Yucatan peninsula directly south of New Orleans, Louisiana, with unparalleled natural attractions: powdery white sand and coral beaches, and turquoise Caribbean waters. The average temperature in April is 26.7 C (80.06 F). There are over two hundred restaurants offering Yucatan specialties, Mexican and international food. It is easy to arrange excursions to important archeological Maya sites such as Chichen-Itza, Tulum, and Coba. There are direct flights and good air connections to many cities in Mexico and abroad.


[Top] [Home] [All LATIN Locations]

  Photos


Taken by Edgar Chávez
Taken by Ricardo Baeza

[Top] [Home] [All LATIN Photos]

  Statistics


General:
No. of submissions 104
No. of accepted papers 46
% of accepted papers 44.2%
Total No. of authors 108
Avg. No. of authors per paper 2.35
No. of countries represented 21
 
No. of papers according to how many authors work in Latin-America
    At least one 7(15.2%)
    All 5(10.9%)


Statistics by Country of Author's Affiliation

Authors*Papers**

31.0(28.7%)14.18(30.8%)USA
14.5(13.4%)6.73(14.6%)France
13.0(12.0%)4.33(9.4%)Canada
10.0(9.3%)3.50(7.6%)Brazil
7.0(6.5%)3.50(7.6%)Italy
6.0(5.6%)2.67(5.8%)Germany
4.5(4.2%)1.92(4.2%)Chile
3.5(3.2%)2.25(4.9%)UK
3.0(2.8%)0.75(1.6%)Japan
3.0(2.8%)0.75(1.6%)Netherlands
2.0(1.9%)0.67(1.4%)Denmark
2.0(1.9%)1.00(2.2%)Switzerland
1.0(0.9%)0.33(0.7%)Spain
1.0(0.9%)0.33(0.7%)Sweden
1.0(0.9%)0.50(1.1%)Austria
1.0(0.9%)0.50(1.1%)Mexico
1.0(0.9%)0.50(1.1%)Latvia
1.0(0.9%)0.33(0.7%)Australia
1.0(0.9%)0.25(0.5%)Iceland
1.0(0.9%)0.50(1.1%)Israel
0.5(0.5%)0.50(1.1%)Poland

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Statistics by Region of Author's Affiliation

Authors*Papers**

44.0(40.7%)18.52(40.3%)USA & Canada
43.5(40.3%)19.98(43.4%)Europe
15.5(14.4%)5.92(12.9%)Latin-America
4.0(3.7%)1.08(2.4%)Australia & Asia
1.0(0.9%)0.50(1.1%)Middle East

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Africa

Australia & Asia

Japan Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi;
Australia Shparlinski, Igor;

Europe

Denmark Katajainen, Jyrki; Raussen, Martin;
Austria Drmota, Michael;
Poland Rytter, Wojciech;
Netherlands Bloo, Roel; Laan, Twan; Nederpelt, Rob;
Sweden Näslund, Mats;
Spain Gonzalez Vasco, Maria Isabel;
Italy Boldi, Paolo; Calamoneri, Tiziana; Dezani-Ciancaglini, Mariangiola; Luccio, Fabrizio; Pagli, Linda; Petreschi, Rossella; Vigna, Sebastiano;
Switzerland Anand, R. Sai; Erlebach, Thomas;
Iceland Halldórsson, Magnús M.;
UK Garefalakis, Theodoulos; Kamareddine, Fairouz; Rytter, Wojciech; van Bakel, Steffen;
France Bassino, Frédérique; Cassez, Franck; Corteel, Sylvie; Dubacq, Jean-Christophe; Finkel, Alain; Frougny, Christiane; Genest, Blaise; Goubault, Eric; Herbreteau, Frédéric; Lombardy, Sylvain; Muscholl, Anca; Roux, Olivier; Sakarovitch, Jacques; Sutre, Grégoire; Terrier, Véronique;
Germany Alber, Jochen; Köhler, Ekkehard; Lefmann, Hanno; Niedermeier, Rolf; Prisner, Erich; Schmitt, Niels;
Latvia Freivalds, Rusins;

Latin-America

Brazil Bornstein, Claudson F.; Braga, Marília D. V.; Carmo, Renato; Donadelli, Jair; Kohayakawa, Yoshiharu; Laber, Eduardo Sany; Meidanis, Joao; Milidiú, Ruy Luiz; Pessoa, Artur Alves;
Mexico Chávez, Edgar;
Chile Hevia, Alejandro; Kiwi, Marcos; Matamala, Martín; Navarro, Gonzalo; Rapaport, Ivan;

Middle East

Israel Tamir, Tami;

USA & Canada

Canada Bose, Prosenjit; Corneil, Derek G.; Devroye, Luc; Evans, William S.; Kirkpatrick, David G.; Mendelsohn, Eric; Morin, Pat; Morrison, Jason; Stevens, Brett; Thérien, Denis; Toussaint, Godfried T.; Wang, Qingda;
USA Abello, James; Arslan, Abdullah N.; Bender, Michael A.; Brönnimann, Hervé; Canfield, Rod; Chen, Jianer; Chen, Xiaomin; Egecioglu, Ömer; F. Dragan, Feodor; Farach-Colton, Martin; Hevia, Alejandro; Hitczenko, Pawel; Iacono, John; Kanj, Iyad; Konjevod, Goran; Muthukrishnan, S.; Oh, Soohyun; Pontelli, Enrico; Ranjan, Desh; Resende, Mauricio G. C.; Richa, Andréa W.; Sahinalp, Cenk; Shachnai, Hadas; Smith, Carl H.; Straubing, Howard; Sudarsky, Sandra; Sutre, Grégoire; Szegedy, Mario; Szpankowski, Wojciech; Tornaría, Gonzalo; Vempala, Santosh;

[Top] [Home] [All LATIN Statistics]