University of Chile, Chile.|
[All LATIN Chairs]
Argimiro Arratia Quesada, U. Valladolid, Spain.|
Marcelo Arenas, U. Toronto, Canada.
José R. Correa, U. Adolfo Ibáñez, Chile.
Luc Devroye, McGill U., Canada.
Guillermo Durán, U. Chile & U. Buenos Aires, Chile & Argentina.
Antonio Fernández, U. Rey Juan Carlos, Spain.
David Fernández-Baca, Iowa State U., USA.
Afonso Ferreira, CNRS & COST Office, France.
Fedor Fomin, U. Bergen, Norway.
Joachim von zur Gathen, Bonn U., Germany.
Cristina Gomes Fernandes, U. de São Paulo, Brazil.
Mordecai Golin, Hong Kong UST, Hong Kong.
Alejandro Hevia, UC San Diego & U. Chile, USA & Chile.
Marcos Kiwi (Chair), U. Chile, Chile.
Hugo Krawczyk, IBM Research, USA.
Eduardo Laber, PUC-Rio, Brazil.
Martin Matamala, U. Chile, Chile.
Jiří Matoušek, Charles U., Czech Republic.
Gonzalo Navarro, U. Chile, Chile.
Daniel Panario, Carleton U., Canada.
Andreas Schulz, MIT, USA.
Jacques Sakarovitch, CNRS/ENST, France.
Amin Shokrollahi, EPFL, Switzerland.
Mona Singh, Princeton U., USA.
Howard Straubing, Boston College, USA.
Shang-Hua Teng, Boston U., USA.
Luca Trevisan, UC Berkeley, USA.
Jorge Urrutia, UNAM, Mexico.
Umesh Vazirani, UC Berkeley, USA.
Santosh Vempala, MIT, USA.
Alfredo Viola, U. de la República, Uruguay.
Yoshiko Wakabayashi, U. de São Paulo, Brazil.
[All LATIN PCs]
University of Chile, Chile.|
José R. Correa,
Adolfo Ibáñez University, Chile.
[All LATIN Org. Committees]
(Universidad de Chile & Universitat Pompeu Fabra), Algorithmic Challenges in Web Search Engine.|
In this paper we present the main algorithmic challenges that large Web
search engines face today. These challenges are present in all the modules
of a Web retrieval system, ranging from the gathering of the data to be
indexed (crawling) to the selection and ordering of the answers to a query
(searching and ranking). Most of the challenges are ultimately related to
the quality of the answer or the efficiency in obtaining it, although some are
relevant even to the existence of search engines: context based advertising.
Anne Condon ,
(RNA molecules: glimpses through an algorithmic lens), U. British Columbia.
Dubbed the ``architects of eukaryotic complexity'',
RNA molecules are increasingly in the spotlight, in recognition of the
important catalytic and regulatory roles they play in our cells and
their promise in therapeutics. Our goal is to describe the ways in
which algorithms can help shape our understanding of RNA structure and
(Universitat Politècnica de Catalunya), Squares.
In this talk we present several results and open
problems having squares, the basic geometric entity, as a common
thread. These results have been gathered from various papers;
coauthors and precise references are given in the descriptions
(Matching Based Augmentations for Approximating Connectivity Problems), Carnegie Mellon University.
We describe a very simple idea for designing approximation
algorithms for connectivity problems: For a spanning tree problem,
the idea is to start with the empty set of edges, and add matching
paths between pairs of components in the current graph that have
desirable properties in terms of the objective function of the
spanning tree problem being solved. Such matching augment the
solution by reducing the number of connected components to roughly
half their original number, resulting in a logarithmic number of
such matching iterations. A logarithmic performance ratio results
for the problem by appropriately bounding the contribution of each
matching to the objective function by that of an optimal solution.
(Modelling Errors and Recovery for Communication), MIT.
In this survey, we trace the initial application of these ideas to
traveling salesperson problems through a simple tree pairing
observation down to more sophisticated applications for buy-at-bulk
type network design problems.
The theory of error-correction has had two divergent schools
of thought, going back to the works of Shannon and Hamming.
In the Shannon school, error is presumed to have been effected
probabilistically. In the Hamming school, the error is modeled
as effected by an all-powerful adversary. The two schools lead
to drastically different limits. In the Shannon model, a binary
channel with error-rate close to, but less than, 50\% is useable
for effective communication. In the Hamming model, a binary
channel with an error-rate of more than 25\% prohibits unique
recovery of the message.
(Lossless Data Compression via Error Correction), Princeton.
In this talk, we describe the notion of list-decoding, as a
bridge between the Hamming and Shannon models. This model
relaxes the notion of recovery to allow for a "list of candidates".
We describe results in this model, and then show how these results
can be applied to get unique recovery under "computational
restrictions" on the channel's ability, a model initiated by
R.~Lipton in 1994.
Based on joint works with Venkatesan Guruswami (U. Washington),
and with Silvio Micali (MIT), Chris Peikert (MIT) and David
This plenary talk gives an overview of recent joint work with
G. Caire and S. Shamai on the use of linear error correcting codes
for lossless data compression, joint source/channel coding and
interactive data exchange.
(The power and weakness of randomness in computation), IAS.
Humanity has grappled with the meaning and utility of randomness
for centuries. Research in the Theory of Computation in the last
thirty years has enriched this study considerably. We describe
two main aspects of this research on randomness, demonstrating its
power and weakness respectively.
[All LATIN Inv. Speakers]
Ricardo Baeza-Yates, Algorithmic Challenges in Web Search Engines. [Bibtex]
Anne Condon, RNA Molecules: Glimpses Through an Algorithmic Lens. [Bibtex]
Ferran Hurtado, Squares. [Bibtex]
R. Ravi, Matching Based Augmentations for Approximating Connectivity Problems. [Bibtex]
Madhu Sudan, Modelling Errors and Recovery for Communication. [Bibtex]
Sergio Verdú, Lossless Data Compression Via Error Correction. [Bibtex]
Avi Wigderson, The Power and Weakness of Randomness in Computation. [Bibtex]
Saurabh Agarwal and Gudmund Skovbjerg Frandsen, A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. [Bibtex]
Nir Ailon, Steve Chien and Cynthia Dwork, On Clusters in Markov Chains. [Bibtex]
Miklós Ajtai, Cynthia Dwork and Larry J. Stockmeyer, An Architecture for Provably Secure Computation. [Bibtex]
Elói Araújo and José Soares, Scoring Matrices That Induce Metrics on Sequences. [Bibtex]
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman and Michiel H. M. Smid, Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. [Bibtex]
Boris Aronov, Alan R. Davis, John Iacono and Albert Siu Cheong Yu, The Complexity of Diffuse Reflections in a Simple Polygon. [Bibtex]
Argimiro Arratia and Carlos Ortiz, Counting Proportions of Sets: Expressive Power with Almost Order. [Bibtex]
Abdullah N. Arslan, Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets. [Bibtex]
Nuttapong Attrapadung, Yang Cui, David Galindo, Goichiro Hanaoka, Ichiro Hasuo, Hideki Imai, Kanta Matsuura, Peng Yang and Rui Zhang, Relations Among Notions of Security for Identity Based Encryption Schemes. [Bibtex]
Ilya Baran, Erik D. Demaine and Dmitriy A. Katz, Optimally Adaptive Integration of Univariate Lipschitz Functions. [Bibtex]
Benjamín René Callejas Bedregal and Santiago Figueira, Classical Computability and Fuzzy Turing Machines. [Bibtex]
Boaz Ben-Moshe, Binay K. Bhattacharya and Qiaosheng Shi, An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. [Bibtex]
Thorsten Bernholt and Thomas Hofmeister, An Algorithm for a Generalized Maximum Subsequence Problem. [Bibtex]
Nayantara Bhatnagar, Dana Randall, Vijay V. Vazirani and Eric Vigoda, Random Bichromatic Matchings. [Bibtex]
Béla Bollobás, Guy Kindler, Imre Leader and Ryan O'Donnell, Eliminating Cycles in the Discrete Torus. [Bibtex]
Claudson F. Bornstein, Eduardo Sany Laber and Marcelo Mas, On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions. [Bibtex]
Jérémie Bourdon and Brigitte Vallée, Pattern Matching Statistics on Correlated Sources. [Bibtex]
Patricia Bouyer, Nicolas Markey and Pierre-Alain Reynier, Robust Model-Checking of Linear-Time Properties in Timed Automata. [Bibtex]
Hajo Broersma, Matthew Johnson, Daniël Paulusma and Iain A. Stewart, The Computational Complexity of the Parallel Knock-Out Problem. [Bibtex]
Gruia Calinescu, Adrian Dumitrescu and János Pach, Reconfigurations in Graphs and Grids. [Bibtex]
Laura Chaubard, C-Varieties, Actions and Wreath Product. [Bibtex]
Edgar Chávez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho and Jorge Urrutia, Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. [Bibtex]
Vicky Choi and Navin Goyal, An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. [Bibtex]
Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young, Oblivious Medians Via Online Bidding. [Bibtex]
Corinna Cortes, Mehryar Mohri, Ashish Rastogi and Michael Riley, Efficient Computation of the Relative Entropy of Probabilistic Automata. [Bibtex]
Ho-Kwok Dai and Hung-Chi Su, A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences. [Bibtex]
Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh and Mihai Patrascu, De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). [Bibtex]
Sandeep Dey and Nicolas Schabanel, Customized Newspaper Broadcast: Data Broadcast with Dependencies. [Bibtex]
Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke and Uwe T. Zimmermann, On Minimum k-Modal Partitions of Permutations. [Bibtex]
Frederic Dorn and Jan Arne Telle, Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm. [Bibtex]
Douglas G. Down and George Karakostas, Maximizing Throughput in Queueing Networks with Limited Flexibility. [Bibtex]
Feodor F. Dragan and Chenyu Yan, Network Flow Spanners. [Bibtex]
Khaled Elbassioni, Finding All Minimal Infrequent Multi-dimensional Intervals. [Bibtex]
Roee Engelberg, Jochen Könemann, Stefano Leonardi and Joseph Naor, Cut Problems in Graphs with a Budget Constraint. [Bibtex]
Martin Farach-Colton, Rohan J. Fernandes and Miguel A. Mosteiro, Lower Bounds for Clear Transmissions in Radio Networks. [Bibtex]
Nazim Fatès, Damien Regnault, Nicolas Schabanel and Eric Thierry, Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. [Bibtex]
Hervé Fournier and Antoine Vigneron, Lower Bounds for Geometric Diameter Problems. [Bibtex]
Pierre Fraigniaud and Nicolas Nisse, Connected Treewidth and Connected Graph Searching. [Bibtex]
Martin Fürer, A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. [Bibtex]
Eli Gafni, Sergio Rajsbaum, Michel Raynal and Corentin Travers, The Committee Decision Problem. [Bibtex]
Ling Gai and Guochuan Zhang, Common Deadline Lazy Bureaucrat Scheduling Revisited. [Bibtex]
Joachim Giesen, Eva Schuberth and Milos Stojakovic, Approximate Sorting. [Bibtex]
Michel X. Goemans and Jan Vondrák, Stochastic Covering and Adaptivity. [Bibtex]
Parikshit Gopalan, Venkatesan Guruswami and Richard J. Lipton, Algorithms for Modular Counting of Roots of Multivariate Polynomials. [Bibtex]
Venkatesan Guruswami and Valentine Kabanets, Hardness Amplification Via Space-Efficient Direct Products. [Bibtex]
Mikael Hammar, Bengt J. Nilsson and Mia Persson, The Online Freeze-Tag Problem. [Bibtex]
Herman J. Haverkort and Laura Toma, I/O-Efficient Algorithms on Near-Planar Graphs. [Bibtex]
Pinar Heggernes and Federico Mancini, Minimal Split Completions of Graphs. [Bibtex]
Regant Y. S. Hung and Hing-Fung Ting, Design and Analysis of Online Batching Systems. [Bibtex]
Wojciech Jawor, Marek Chrobak and Christoph Dürr, Competitive Analysis of Scheduling Algorithms for Aggregated Links. [Bibtex]
James King, A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains. [Bibtex]
Goran Konjevod, Andréa W. Richa and Donglin Xia, On Sampling in Higher-Dimensional Peer-to-Peer Systems. [Bibtex]
Evangelos Kranakis, Danny Krizanc and Euripides Markou, Mobile Agent Rendezvous in a Synchronous Torus. [Bibtex]
Lap Chi Lau and Michael Molloy, Randomly Colouring Graphs with Girth Five and Large Maximum Degree. [Bibtex]
Orlando Lee and Aaron Williams, Packing Dicycle Covers in Planar Graphs with No K5-e Minor. [Bibtex]
Loïck Lhote and Brigitte Vallée, Sharp Estimates for the Main Parameters of the Euclid Algorithm. [Bibtex]
Veli Mäkinen and Gonzalo Navarro, Position-Restricted Substring Searching. [Bibtex]
Yan Mayster and Mario A. Lopez, Rectilinear Approximation of a Set of Points in the Plane. [Bibtex]
Frédéric Mazoit, The Branch-Width of Circular-Arc Graphs. [Bibtex]
Eduardo Moreno and Martín Matamala, Minimal Eulerian Circuit in a Labeled Digraph. [Bibtex]
Frank Neumann and Marco Laumanns, Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization. [Bibtex]
Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan and Marie-France Sagot, RISOTTO: Fast Extraction of Motifs with Mismatches. [Bibtex]
Mariko Sakashita, Kazuhisa Makino and Satoru Fujishige, Minimum Cost Source Location Problems with Flow Requirements. [Bibtex]
Daniel Sawitzki, Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms. [Bibtex]
Igor Shparlinski and Arne Winterhof, Constructions of Approximately Mutually Unbiased Bases. [Bibtex]
Yngve Villanger, Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. [Bibtex]
[All LATIN Papers]
[All LATIN Sponsors]
LATIN 2006 took place at the Hotel Villa del Rio in Valdivia, Chile. The
Hotel is set on the North shore of the Calle Calle river and has
beautiful open riverside gardens and Marina.
Situated at the confluence of two navigable rivers, Valdivia is one
of the south's most charismatic cities. Nearby Spanish forts at Corral
and Niebla are reminders of the city's importance during the colonial
era, when it was one of few fortified cities maintained by the Spanish
in Mapuche Indian territory; subtle German architecture dates from the
late 19th-century influx of European immigrants. The Rio Cruces Nature
Sanctuary, a protected wetlands north of the city, is home to a
variety of aquatic birds and is a favorite destination for boat trips.
[All LATIN Locations]
[All LATIN Photos]
|No. of submissions|| 192|
|No. of accepted papers|| 66|
|% of accepted papers|| 34.4%|
|Total No. of authors|| 179|
|Avg. No. of authors per paper|| 2.71|
|No. of countries represented|| 26|
|No. of papers according to how many authors work in Latin-America|
| At least one|| 8||(12.1%)|
| All|| 4||(6.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.
Australia & Asia
Hung, Regant Y. S.;
Di Stefano, Gabriele;
Telle, Jan Arne;
Frandsen, Gudmund Skovbjerg;
Lübbecke, Marco E.;
Meyer auf der Heide, Friedhelm;
Zimmermann, Uwe T.;
Stewart, Iain A.;
Carvalho, Alexandra M.;
Haverkort, Herman J.;
Nilsson, Bengt J.;
Bedregal, Benjamín René Callejas;
Bornstein, Claudson F.;
Laber, Eduardo Sany;
USA & Canada
Bhattacharya, Binay K.;
Down, Douglas G.;
Lau, Lap Chi;
Smid, Michiel H. M.;
Arslan, Abdullah N.;
Davis, Alan R.;
Demaine, Erik D.;
Dragan, Feodor F.;
Fernandes, Rohan J.;
Goemans, Michel X.;
Katz, Dmitriy A.;
Lipton, Richard J.;
Lopez, Mario A.;
Mosteiro, Miguel A.;
Richa, Andréa W.;
Stockmeyer, Larry J.;
Vazirani, Vijay V.;
Young, Neal E.;
Yu, Albert Siu Cheong;
[All LATIN Statistics]