LATIN 2010 - 9th Latin American Theoretical Informatics Symposium

Accepted Papers

See here for the list of accepted papers with abstracts.

  • The Complexity of Counting Eulerian Tours in 4-Regular Graphs
    Qi Ge and Daniel Stefankovic

  • Compact Rich-Functional Binary Relation Representations
    Jérémy Barbay, Francisco Claude and Gonzalo Navarro

  • Optimal Succinctness for Range Minimum Queries
    Johannes Fischer

  • A larger lower bound on the OBDD complexity of the most significant bit of multiplication
    Beate Bollig

  • Visiting a Sequence of Points with a Bevel-Tip Needle
    Atlas F. Cook IV, Carola Wenk, Ovidiu Daescu, Steven Bitner, Yam K. Cheung and Anastasia Kurdia

  • Euclidean Prize-collecting Steiner Forest
    MohammadHossein Bateni and MohammadTaghi Hajiaghayi

  • Time Complexity of Distributed Topological Self-Stabilization: The Case of Graph Linearization
    Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid and Hanjo Täubig

  • The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
    Jonathan Backer and Mark Keil

  • Colorful Strips
    Greg Aloupis, Jean Cardinal, Sebastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian

  • Average Parameterization and Partial Kernelization for Computing Medians
    Nadja Betzler, Jiong Guo, Christian Komusiewicz and Rolf Niedermeier

  • Packet Routing on the Grid
    Britta Peis, Martin Skutella and Andreas Wiese

  • Efficient Edge Domination on Hole-free Graphs in Polynomial Time
    Andreas Brandstädt, Christian Hundt and Ragnar Nevries

  • Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata
    Viliam Geffert and Giovanni Pighizzini

  • Rank Selection in Multidimensional Data
    Amalia Duch, Conrado Martinez and Rosa M. Jimenez

  • Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight
    Tsunehiko Kameda, Ichiro Suzuki and John Z. Zhang

  • Layered Working-Set Trees
    Prosenjit Bose, Karim Douïeb, Vida Dujmović and John Howat

  • Gradual sub-lattice reduction and a new complexity for factoring polynomials
    Andrew Novocin and Mark van Hoeij

  • Radix cross-sections for length morphisms
    Sylvain Lombardy and Jacques Sakarovitch

  • Prize-Collecting Steiner Networks via Iterative Rounding
    MohammadTaghi Hajiaghayi and Arefeh Nasri

  • Modelling the LLL algorithm via sandpiles
    Brigitte Vallee and Manfred Madritsch

  • Lightweight Data Indexing and Compression in External Memory
    Paolo Ferragina, Travis Gagie and Giovanni Manzini

  • Homotopic Rectilinear Routing with Few Links and Thick Edges
    Bettina Speckmann and Kevin Verbeek

  • Approximating Maximum Diameter-Bounded Subgraphs
    Yuichi Asahiro, Eiji Miyano and Kazuaki Samizo

  • Tilings robust to errors
    Alexis Ballier, Emmanuel Jeandel and Bruno Durand

  • Randomized truthful algorithms for scheduling selfish tasks on parallel machines
    Eric Angel, Evripidis Bampis and Nicolas Thibault

  • Largest Induced Acyclic Tournament in Random Digraphs: A 2-point concentration
    C.R. Subramanian and Kunal Dutta

  • The interval constrained 3-coloring problem
    Jaroslaw Byrka, Andreas Karrenbauer and Laura Sanita

  • Quasi-Proportional Mechanisms: Prior-free Revenue Maximization
    Vahab Mirrokni, S. Muthukrishnan and Uri Nadav

  • Limit theorems for random MAX-$2$-XORSAT
    Rasendrahasina Vonjy and Ravelomanana Vlady

  • Complexity of Operations on Cofinite Languages
    Frédérique Bassino, Laura Giambruno and Cyril Nicaud.

  • Matching Points with Things
    Greg Aloupis, Jean Cardinal, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila-Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara and Perouz Taslakian

  • Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
    Edyta Szymanska, Marek Karpinski and Andrzej Rucinski

  • Counting reducible, squareful, and relatively irreducible multivariate polynomials over finite fields
    Joachim von zur Gathen, Alfredo Viola and Konstantin Ziegler

  • Randomised Broadcasting: Memory vs. Randomness
    Petra Berenbrink, Robert Elsaesser and Thomas Sauerwald

  • The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
    Gero Greiner and Riko Jacob

  • Kernelization Through Tidying---A Case Study Based on s-Plex Cluster Vertex Deletion
    Rene van Bevern, Hannes Moser and Rolf Niedermeier

  • Quotient Complexity of Ideal Languages
    Janusz Brzozowski, Galina Jiraskova and Baiyu Li

  • Connectivity is Not a Limit for Kernelization: Planar Connected Dominating Set
    Navid Imani and Qianping Gu

  • Optimal Polygonal Representation of Planar Graphs
    Emden Gansner, Yifan Hu, Michael Kaufmann and Stephen Kobourov

  • The Language Theory of Bounded Context-Switching
    Salvatore La Torre, Madhusudan Parthasarathy and Gennaro Parlato

  • Minimum-perimeter intersecting polygons
    Adrian Dumitrescu and Minghui Jiang

  • Lipschitz Unimodal and Isotonic Regression on Paths and Trees
    Pankaj Agarwal, Jeff Phillips and Bardia Sadri

  • Fast Set Intersection and Two Patterns Matching
    Hagai Cohen and Ely Porat

  • The Power of Fair Pricing Mechanisms
    Christine Chung, Katrina Ligett, Kirk Pruhs and Aaron Roth

  • Faithful Representations of Graphs by Islands in the Extended Grid
    Michael Coury, Pavol Hell, Jan Kratochvil and Tomas Vyskocil

  • Finding the smallest gap between sums of square roots
    Qi Cheng and Yu-Hsin Li

  • The Size and Depth of Layered Boolean Circuits
    Anna Gal and Jing-Tang Jang

  • Communication-Efficient Construction of the Plane Localized Delaunay Graph
    Prosenjit Bose, Paz Carmi, Michiel Smid and Daming Xu

  • Counting hexagonal patches and independent sets in circle graphs
    Paul Bonsma and Felix Breuer

  • Sharp Separation and Applications to Exact and Parameterized Algorithms
    Fedor Fomin, Fabrizio Grandoni, Daniel Lokshtanov and Saket Saurabh

  • On Quadratic Threshold CSPs
    Per Austrin, Siavosh Benabbas and Avner Magen

  • Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming
    Leonor Vázquez and Carles Padró

  • Local search performance guarantees for restricted related parallel machine scheduling
    Diego Recalde, Cyriel Rutten, Petra Schuurman and Tjark Vredeveld

  • Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width
    Martin Fürer

  • Ambiguity and Deficiency in Costas Arrays and APN Permutations
    Daniel Panario, Brett Stevens and Qiang Wang

  • Finding the best CAFE is NP-hard
    Elizabeth Maltais and Lucia Moura