LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings [Paperback]

Keynotes.- Algorithmic Challenges in Web Search Engines.- RNA Molecules: Glimpses Through an Algorithmic Lens.- Squares.- Matching Based Augmentations for Approximating Connectivity Problems.- Modelling Errors and Recovery for Communication.- Lossless Data Compression Via Error Correction.- The Power and Weakness of Randomness in Computation.- Regular Contributions.- A New GCD Algorithm for Quadratic Number Rings with Unique Factorization.- On Clusters in Markov Chains.- An Architecture for Provably Secure Computation.- Scoring Matrices That Induce Metrics on Sequences.- Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.- The Complexity of Diffuse Reflections in a Simple Polygon.- Counting Proportions of Sets: Expressive Power with Almost Order.- Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets.- Relations Among Notions of Security for Identity Based Encryption Schemes.- Optimally Adaptive Integration of Univariate Lipschitz Functions.- Classical Computability and Fuzzy Turing Machines.- An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees.- An Algorithm for a Generalized Maximum Subsequence Problem.- Random Bichromatic Matchings.- Eliminating Cycles in the Discrete Torus.- On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions.- Pattern Matching Statistics on Correlated Sources.- Robust Model-Checking of Linear-Time Properties in Timed Automata.- The Computational Complexity of the Parallel Knock-Out Problem.- Reconfigurations in Graphs and Grids.- -Varieties, Actions and Wreath Product.- Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges.- An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.- Oblivious Medians Via Online Bidding.- Efficient Computation of the Relative Entropy of Probabilistic Automata.- A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequencesl3#