Chair


Sergio Rajsbaum,
Compaq CRL/UNAM, USA/Mexico.


[Top]
[Home]
[All LATIN Chairs]


Program Committee


Amihood Amir, BarIlan Univ., Israel.
Mauricio Ayala Rincón, Brazilia Univ., Brazil.
Ricardo BaezaYates, 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 FarachColton, Rutgers Univ., USA.
David FernandezBaca, 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. deSao Paulo, Brasil.
Elias Koutsoupias, UC Los Angeles, USA.
Evangelos Kranakis, Carleton Univ., Canada.
Daniel Leivant, Indiana Univ., USA.
Alex LopezOrtiz, 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. Politecnica de Cataluña, Spain.
Gadiel Seroussi, Hewlet Packard, USA.
Igor Shparlinski, Macquarie Univ., Australia.
Imre Simon, Univ. de Sao 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;
ksatisfiability  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
nonexistence 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 finitesize 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), Erdos Magic.
The Probabilistic Method is a lasting legacy of the late Paul
Erdos. We give two examples  both problems first formulated by Erdos
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. Erdos showed this may always be done if m< 2(n1),
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. Erdos and Hanani
conjectured such a packing exists (in an important special case of
asymptotic designs) and this conjecture was shown by Rodl. 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.
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
(blackbox 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 modelchecking
problem, and has been thoroughly studied for many years, yielding a
rich theory, algorithms and tools. Blackbox 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, Erdos 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, BetaExpansions 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 ConstantSpace LinearTime 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, kpseudosnakes 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 MAXSAT. [Bibtex]
Steffen van Bakel and Mariangiola DezaniCiancaglini, 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 TimeDependent Edge Reliabilities. [Bibtex]
JeanChristophe 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 betaskeletons. [Bibtex]
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison and Godfried T. Toussaint, InPlace Planar Convex Hull Algorithms. [Bibtex]
Michael A. Bender and Martin FarachColton, 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 ClassConstrained Packing. [Bibtex]
R. Sai Anand and Thomas Erlebach, Online Algorithms for EdgeDisjoint Paths in Trees of Rings. [Bibtex]
James Abello, Mauricio G. C. Resende and Sandra Sudarsky, Massive QuasiClique Detection. [Bibtex]
Jochen Alber and Rolf Niedermeier, Improved Tree Decomposition Based Algorithms for Dominationlike Problems. [Bibtex]


[Top]
[Home]
[All LATIN Papers]


Sponsors



[Top]
[Home]
[All LATIN Sponsors]


Location


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 ChichenItza,
Tulum, and Coba. There are direct flights and good air connections to
many cities in Mexico and abroad.


[Top]
[Home]
[All LATIN Locations]


Photos



[Top]
[Home]
[All LATIN Photos]


Statistics


General: 
No. of submissions  104  
No. of accepted papers  45  
% of accepted papers  43.3%  
Total No. of authors  106  
Avg. No. of authors per paper  2.36  
No. of countries represented  21  

No. of papers according to how many authors work in LatinAmerica 
At least one  7  (15.6%) 
All  5  (11.1%) 
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
Africa
Australia & Asia
Europe
Germany 
Alber, Jochen;
Köhler, Ekkehard;
Lefmann, Hanno;
Niedermeier, Rolf;
Prisner, Erich;
Schmitt, Niels;

Italy 
Boldi, Paolo;
Calamoneri, Tiziana;
DezaniCiancaglini, Mariangiola;
Petreschi, Rossella;
Vigna, Sebastiano;

Spain 
Gonzalez Vasco, Maria Isabel;

Poland 
Rytter, Wojciech;

UK 
Garefalakis, Theodoulos;
Kamareddine, Fairouz;
Rytter, Wojciech;
van Bakel, Steffen;

Denmark 
Katajainen, Jyrki;
Raussen, Martin;

Iceland 
Halldórsson, Magnús M.;

Austria 
Drmota, Michael;

Switzerland 
Anand, R. Sai;
Erlebach, Thomas;

Netherlands 
Bloo, Roel;
Laan, Twan;
Nederpelt, Rob;

France 
Bassino, Frédérique;
Cassez, Franck;
Corteel, Sylvie;
Dubacq, JeanChristophe;
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;

Latvia 
Freivalds, Rusins;

Sweden 
Näslund, Mats;

LatinAmerica
Chile 
Hevia, Alejandro;
Kiwi, Marcos;
Matamala, Martín;
Navarro, Gonzalo;
Rapaport, Ivan;

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;

Middle East
USA & Canada
USA 
Abello, James;
Arslan, Abdullah N.;
Bender, Michael A.;
Brönnimann, Hervé;
Canfield, Rod;
Chen, Xiaomin;
Egecioglu, Ömer;
F. Dragan, Feodor;
FarachColton, 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;

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;



[Top]
[Home]
[All LATIN Statistics]

