LATIN 2006


Chair
Program Committee
Organizing Committee
Invited Speakers
Proceeding
Papers
Sponsors
Location
Photos
Statistics


Chair
Marcos Kiwi, University of Chile, Chile.

[Top] [Home] [All LATIN Chairs]

Program Committee
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.

[Top] [Home] [All LATIN PCs]

Organizing Committee
Alejandro Hevia, University of Chile, Chile.
José R. Correa, Adolfo Ibáñez University, Chile.

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

Invited Speakers
Ricardo Baeza-Yates, (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 function.
Ferran Hurtado, (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 that follow.
R. Ravi, (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.

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.

Madhu Sudan, (Modelling Errors and Recovery for Communication), MIT.
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.

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 Wilson (MIT).

Sergio Verdú, (Lossless Data Compression via Error Correction), Princeton.
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.
Avi Wigderson, (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.

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

Papers
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]



[Top] [Home] [All LATIN Papers]

Sponsors
Anillo en Redes
Centro de Modelamiento Matemático, U. Chile
CLEI: Centro Latinoamericano de Estudios en Informática
IFIP: International Federation for Information Processing

[Top] [Home] [All LATIN Sponsors]

Location

Conference Site

LATIN 2006 took place at the Hotel Villa del Rio in Valdivia. 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.


[Top] [Home] [All LATIN Locations]

Photos

[Top] [Home] [All LATIN Photos]

Statistics
General:
No. of submissions 224
No. of accepted papers 66
% of accepted papers 29.5%
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%)


Statistics by Country of Author's Affiliation

Authors*Papers**

62.0(34.6%)21.60(32.7%)USA
24.0(13.4%)10.33(15.7%)France
20.0(11.2%)7.37(11.2%)Canada
11.0(6.1%)1.89(2.9%)Japan
9.0(5.0%)4.50(6.8%)Germany
7.0(3.9%)3.00(4.5%)Brazil
5.0(2.8%)1.25(1.9%)UK
5.0(2.8%)3.00(4.5%)Norway
4.0(2.2%)1.50(2.3%)Switzerland
3.0(1.7%)0.75(1.1%)Italy
3.0(1.7%)1.00(1.5%)Sweden
3.0(1.7%)0.58(0.9%)Mexico
3.0(1.7%)1.50(2.3%)Chile
3.0(1.7%)1.25(1.9%)Denmark
2.0(1.1%)0.64(1.0%)Australia
2.0(1.1%)1.00(1.5%)Hong Kong
2.0(1.1%)1.00(1.5%)China
2.0(1.1%)0.61(0.9%)Netherlands
2.0(1.1%)0.50(0.8%)Israel
1.0(0.6%)0.14(0.2%)Belgium
1.0(0.6%)0.50(0.8%)Argentina
1.0(0.6%)0.50(0.8%)Finland
1.0(0.6%)0.25(0.4%)Portugal
1.0(0.6%)0.50(0.8%)Austria
1.0(0.6%)0.50(0.8%)Spain
1.0(0.6%)0.33(0.5%)Greece

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**

82.0(45.8%)29.0(43.9%)USA & Canada
64.0(35.8%)26.4(40.0%)Europe
15.0(8.4%)3.5(5.4%)Australia & Asia
14.0(7.8%)5.6(8.5%)Latin-America
2.0(1.1%)1.0(1.5%)China
2.0(1.1%)0.5(0.8%)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

Australia Gudmundsson, Joachim; Shparlinski, Igor;
Hong Kong Hung, Regant Y. S.; Ting, Hing-Fung;
Japan Attrapadung, Nuttapong; Cui, Yang; Fujishige, Satoru; Hanaoka, Goichiro; Hasuo, Ichiro; Imai, Hideki; Makino, Kazuhisa; Matsuura, Kanta; Sakashita, Mariko; Yang, Peng; Zhang, Rui;

China

China Gai, Ling; Zhang, Guochuan;

Europe

UK Broersma, Hajo; Johnson, Matthew; Leader, Imre; Paulusma, Daniël; Stewart, Iain A.;
Italy Di Stefano, Gabriele; Leonardi, Stefano; Pisanti, Nadia;
Sweden Hammar, Mikael; Nilsson, Bengt J.; Persson, Mia;
Germany Bernholt, Thorsten; Elbassioni, Khaled; Hofmeister, Thomas; Krause, Stefan; Lübbecke, Marco E.; Meyer auf der Heide, Friedhelm; Neumann, Frank; Sawitzki, Daniel; Zimmermann, Uwe T.;
Switzerland Giesen, Joachim; Laumanns, Marco; Schuberth, Eva; Stojakovic, Milos;
Belgium Langerman, Stefan;
Norway Dorn, Frederic; Heggernes, Pinar; Mancini, Federico; Telle, Jan Arne; Villanger, Yngve;
Netherlands Galindo, David; Haverkort, Herman J.;
France Bourdon, Jérémie; Bouyer, Patricia; Chaubard, Laura; Dürr, Christoph; Dey, Sandeep; Fatès, Nazim; Fournier, Hervé; Fraigniaud, Pierre; Lhote, Loïck; Markey, Nicolas; Marsan, Laurent; Mazoit, Frédéric; Nisse, Nicolas; Raynal, Michel; Regnault, Damien; Reynier, Pierre-Alain; Sagot, Marie-France; Schabanel, Nicolas; Thierry, Eric; Travers, Corentin; Vallée, Brigitte; Vigneron, Antoine;
Finland Mäkinen, Veli;
Portugal Carvalho, Alexandra M.;
Austria Winterhof, Arne;
Denmark Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg; Pagh, Rasmus;
Spain Arratia, Argimiro;
Greece Markou, Euripides;

Latin-America

Mexico Chávez, Edgar; Rajsbaum, Sergio; Urrutia, Jorge;
Chile Matamala, Martín; Moreno, Eduardo; Navarro, Gonzalo;
Brazil Araújo, Elói; Bedregal, Benjamín René Callejas; Bornstein, Claudson F.; Laber, Eduardo Sany; Lee, Orlando; Mas, Marcelo; Soares, José;
Argentina Figueira, Santiago;

Middle East

Israel Engelberg, Roee; Naor, Joseph;

USA & Canada

Canada Ben-Moshe, Boaz; Bhattacharya, Binay K.; Bose, Prosenjit; Dobrev, Stefan; Down, Douglas G.; Goyal, Navin; Könemann, Jochen; Kabanets, Valentine; Karakostas, George; King, James; Kranakis, Evangelos; Krizanc, Danny; Lau, Lap Chi; Molloy, Michael; Opatrny, Jaroslav; Shi, Qiaosheng; Smid, Michiel H. M.; Stacho, Ladislav; Williams, Aaron;
USA Ailon, Nir; Ajtai, Miklós; Aronov, Boris; Arslan, Abdullah N.; Baran, Ilya; Bhatnagar, Nayantara; Bollobás, Béla; Calinescu, Gruia; Chien, Steve; Choi, Vicky; Chrobak, Marek; Cortes, Corinna; Dai, Ho-Kwok; Davis, Alan R.; Demaine, Erik D.; Dragan, Feodor F.; Dumitrescu, Adrian; Dwork, Cynthia; Fürer, Martin; Farach-Colton, Martin; Fernandes, Rohan J.; Gafni, Eli; Goemans, Michel X.; Gopalan, Parikshit; Guruswami, Venkatesan; Iacono, John; Jawor, Wojciech; Katz, Dmitriy A.; Kenyon, Claire; Kindler, Guy; Konjevod, Goran; Lipton, Richard J.; Lopez, Mario A.; Mayster, Yan; Mohri, Mehryar; Mosteiro, Miguel A.; Noga, John; O'Donnell, Ryan; Ortiz, Carlos; Pach, János; Patrascu, Mihai; Randall, Dana; Rastogi, Ashish; Richa, Andréa W.; Riley, Michael; Stockmeyer, Larry J.; Su, Hung-Chi; Toma, Laura; Vazirani, Vijay V.; Vigoda, Eric; Vondrák, Jan; Xia, Donglin; Yan, Chenyu; Young, Neal E.; Yu, Albert Siu Cheong;


[Top] [Home] [All LATIN Statistics]