LATIN 2010: Theoretical Informatics

Inhalt

Continuous and Discrete Methods in Computer Science.- Colorful Strips.- The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions.- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set.- Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines.- Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width.- Average Parameterization and Partial Kernelization for Computing Medians.- Sharp Separation and Applications to Exact and Parameterized Algorithms.- Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight.- The Language Theory of Bounded Context-Switching.- Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling.- Packet Routing on the Grid.- Faithful Representations of Graphs by Islands in the Extended Grid.- The I/O Complexity of Sparse Matrix Dense Matrix Multiplication.- Sparse Recovery Using Sparse Random Matrices.- Optimal Succinctness for Range Minimum Queries.- Compact Rich-Functional Binary Relation Representations.- Radix Cross-Sections for Length Morphisms.- Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata.- Quotient Complexity of Ideal Languages.- Complexity of Operations on Cofinite Languages.- Fast Set Intersection and Two-Patterns Matching.- Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields.- A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication.- Modelling the LLL Algorithm by Sandpiles.- Communication-Efficient Construction of the Plane Localized Delaunay Graph.- Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization.- Randomised Broadcasting: Memory vs. Randomness.- Limit Theorems for Random MAX-2-XORSAT.- On Quadratic Threshold CSPs.- Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming.- Finding the Best CAFE Is NP-Hard.- The Size and Depth of Layered Boolean Circuits.- Lipschitz Unimodal and Isotonic Regression on Paths and Trees.- Ambiguity and Deficiency in Costas Arrays and APN Permutations.- Iterated Shared Memory Models.- Optimal Polygonal Representation of Planar Graphs.- Minimum-Perimeter Intersecting Polygons.- Finding the Smallest Gap between Sums of Square Roots.- Matching Points with Things.- Homotopic Rectilinear Routing with Few Links and Thick Edges.- Tilings Robust to Errors.- Visiting a Sequence of Points with a Bevel-Tip Needle.- Euclidean Prize-Collecting Steiner Forest.- Prize-Collecting Steiner Networks via Iterative Rounding.- Kernelization through Tidying.- Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials.- The Power of Fair Pricing Mechanisms.- Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization.- Some Observations on Holographic Algorithms.- The Interval Constrained 3-Coloring Problem.- Counting Hexagonal Patches and Independent Sets in Circle Graphs.- Approximating Maximum Diameter-Bounded Subgraphs.- Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration.- The Complexity of Counting Eulerian Tours in 4-Regular Graphs.- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time.- Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs.- Rank Selection in Multidimensional Data.- Layered Working-Set Trees.- Lightweight Data Indexing and Compression in External Memory.