7. LATIN 2006: Valdivia, Chile

Keynotes

• Ricardo A. Baeza-Yates:
  Algorithmic Challenges in Web Search Engines. 1-7
  
• Anne Condon:
  RNA Molecules: Glimpses Through an Algorithmic Lens. 8-10
  
• Ferran Hurtado:
  Squares. 11-12
  
• R. Ravi:
  Matching Based Augmentations for Approximating Connectivity Problems. 13-24
  
• Madhu Sudan:
  Modelling Errors and Recovery for Communication. 25-25
  
• Sergio Verdú:
  Lossless Data Compression Via Error Correction. 26-27
  
• Avi Wigderson:
  The Power and Weakness of Randomness in Computation. 28-29
  

Regular Contributions

• Saurabh Agarwal, Gudmund Skovbjerg Frandsen:
  A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. 30-42
  
• Nir Ailon, Steve Chien, Cynthia Dwork:
  On Clusters in Markov Chains. 43-55
  
• Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer:
  An Architecture for Provably Secure Computation. 56-67
  
• Elói Araújo, José Soares:
  Scoring Matrices That Induce Metrics on Sequences. 68-79
  
• Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid:
  Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. 80-92
  
• Boris Aronov, Alan R. Davis, John Iacono, Albert Siu Cheong Yu:
  The Complexity of Diffuse Reflections in a Simple Polygon. 93-104
  
• Argimiro Arratia, Carlos E. Ortiz:
  Counting Proportions of Sets: Expressive Power with Almost Order. 105-117
  
• Abdullah N. Arslan:
  Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets. 118-129
  
• Nuttapong Attrapadung, Yang Cui, David Galindo, Goichiro Hanaoka, Ichiro Hasuo, Hideki Imai, Kanta Matsuura, Peng Yang, Rui Zhang:
  Relations Among Notions of Security for Identity Based Encryption Schemes. 130-141
  
• Ilya Baran, Erik D. Demaine, Dmitriy A. Katz:
  Optimally Adaptive Integration of Univariate Lipschitz Functions. 142-153
  
• Benjamín René Callejas Bedregal, Santiago Figueira:
  Classical Computability and Fuzzy Turing Machines. 154-165
  
• Boaz Ben-Moshe, Binay K. Bhattacharya, Qiaosheng Shi:
  An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. 166-177
  
• Thorsten Bernholt, Thomas Hofmeister:
  An Algorithm for a Generalized Maximum Subsequence Problem. 178-189
  
• Nayantara Bhatnagar, Dana Randall, Vijay V. Vazirani, Eric Vigoda:
  Random Bichromatic Matchings. 190-201
  
• Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell:
  Eliminating Cycles in the Discrete Torus. 202-210
  
• Claudson F. Bornstein, Eduardo Sany Laber, Marcelo Mas:
  On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions. 211-223
  
• Jérémie Bourdon, Brigitte Vallée:
  Pattern Matching Statistics on Correlated Sources. 224-237
  
• Patricia Bouyer, Nicolas Markey, Pierre-Alain Reynier:
  Robust Model-Checking of Linear-Time Properties in Timed Automata. 238-249
  
• Hajo Broersma, Matthew Johnson, Daniël Paulusma, Iain A. Stewart:
  The Computational Complexity of the Parallel Knock-Out Problem. 250-261
  
• Gruia Calinescu, Adrian Dumitrescu, János Pach:
  Reconfigurations in Graphs and Grids. 262-273
  
• Laura Chaubard:
  C-Varieties, Actions and Wreath Product. 274-285
  
• Edgar Chávez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia:
  Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. 286-297
  
• Vicky Choi, Navin Goyal:
  An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. 298-310
  
• Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young:
  Oblivious Medians Via Online Bidding. 311-322
  
• Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley:
  Efficient Computation of the Relative Entropy of Probabilistic Automata. 323-336
  
• Ho-Kwok Dai, Hung-Chi Su:
  A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences. 337-348
  
• Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu:
  De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). 349-361
  
• Sandeep Dey, Nicolas Schabanel:
  Customized Newspaper Broadcast: Data Broadcast with Dependencies. 362-373
  
• Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke, Uwe T. Zimmermann:
  On Minimum k-Modal Partitions of Permutations. 374-385
  
• Frederic Dorn, Jan Arne Telle:
  Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm. 386-397
  
• Douglas G. Down, George Karakostas:
  Maximizing Throughput in Queueing Networks with Limited Flexibility. 398-409
  
• Feodor F. Dragan, Chenyu Yan:
  Network Flow Spanners. 410-422
  
• Khaled M. Elbassioni:
  Finding All Minimal Infrequent Multi-dimensional Intervals. 423-434
  
• Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor:
  Cut Problems in Graphs with a Budget Constraint. 435-446
  
• Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro:
  Lower Bounds for Clear Transmissions in Radio Networks. 447-454
  
• Nazim Fatès, Damien Regnault, Nicolas Schabanel, Eric Thierry:
  Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. 455-466
  
• Hervé Fournier, Antoine Vigneron:
  Lower Bounds for Geometric Diameter Problems. 467-478
  
• Pierre Fraigniaud, Nicolas Nisse:
  Connected Treewidth and Connected Graph Searching. 479-490
  
• Martin Fürer:
  A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. 491-501
  
• Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers:
  The Committee Decision Problem. 502-514
  
• Ling Gai, Guochuan Zhang:
  Common Deadline Lazy Bureaucrat Scheduling Revisited. 515-523
  
• Joachim Giesen, Eva Schuberth, Milos Stojakovic:
  Approximate Sorting. 524-531
  
• Michel X. Goemans, Jan Vondrák:
  Stochastic Covering and Adaptivity. 532-543
  
• Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton:
  Algorithms for Modular Counting of Roots of Multivariate Polynomials. 544-555
  
• Venkatesan Guruswami, Valentine Kabanets:
  Hardness Amplification Via Space-Efficient Direct Products. 556-568
  
• Mikael Hammar, Bengt J. Nilsson, Mia Persson:
  The Online Freeze-Tag Problem. 569-579
  
• Herman J. Haverkort, Laura Toma:
  I/O-Efficient Algorithms on Near-Planar Graphs. 580-591
  
• Pinar Heggernes, Federico Mancini:
  Minimal Split Completions of Graphs. 592-604
  
• Regant Y. S. Hung, Hing-Fung Ting:
  Design and Analysis of Online Batching Systems. 605-616
  
• Wojciech Jawor, Marek Chrobak, Christoph Dürr:
  Competitive Analysis of Scheduling Algorithms for Aggregated Links. 617-628
  
• James King:
  A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains. 629-640
  
• Goran Konjevod, Andréa W. Richa, Donglin Xia:
  On Sampling in Higher-Dimensional Peer-to-Peer Systems. 641-652
  
• Evangelos Kranakis, Danny Krizanc, Euripides Markou:
  Mobile Agent Rendezvous in a Synchronous Torus. 653-664
  
• Lap Chi Lau, Michael Molloy:
  Randomly Colouring Graphs with Girth Five and Large Maximum Degree. 665-676
  
• Orlando Lee, Aaron Williams:
  Packing Dicycle Covers in Planar Graphs with No K₅-e Minor. 677-688
  
• Loïck Lhote, Brigitte Vallée:
  Sharp Estimates for the Main Parameters of the Euclid Algorithm. 689-702
  
• Veli Mäkinen, Gonzalo Navarro:
  Position-Restricted Substring Searching. 703-714
  
• Yan Mayster, Mario A. Lopez:
  Rectilinear Approximation of a Set of Points in the Plane. 715-726
  
• Frédéric Mazoit:
  The Branch-Width of Circular-Arc Graphs. 727-736
  
• Eduardo Moreno, Martín Matamala:
  Minimal Eulerian Circuit in a Labeled Digraph. 737-744
  
• Frank Neumann, Marco Laumanns:
  Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization. 745-756
  
• Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan, Marie-France Sagot:
  RISOTTO: Fast Extraction of Motifs with Mismatches. 757-768
  
• Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige:
  Minimum Cost Source Location Problems with Flow Requirements. 769-780
  
• Daniel Sawitzki:
  Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms. 781-792
  
• Igor Shparlinski, Arne Winterhof:
  Constructions of Approximately Mutually Unbiased Bases. 793-799
  
• Yngve Villanger:
  Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. 800-811