Automata, Languages and Programming

Multiple Choices.- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.- Dynamic Programming for Graphs on Surfaces.- Interval Graphs: Canonical Representation in Logspace.- Session 6-Track A. Best Paper Award.- Approximating the Partition Function of the Ferromagnetic Potts Model.- Session 7-Track A. Algebraic Problems.- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.- On Sums of Roots of Unity.- Exponential Time Complexity of the Permanent and the Tutte Polynomial.- On Approximate Horn Formula Minimization.- Session 8-Track A. Networks & Communication Complexity.- Choosing, Agreeing, and Eliminating in Communication Complexity.- Additive Spanners in Nearly Quadratic Time.- Composition Theorems in Communication Complexity.- Network Design via Core Detouring for Problems without a Core.- Session 9-Track A1. Complexity & Automata.- Weak Completeness Notions for Exponential Time.- Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.- On the Complexity of Searching in Trees: Average-Case Minimization.- Session 9-Track A2. Finding & Testing.- Finding Is as Easy as Detecting for Quantum Walks.- Improved Constructions for Non-adaptive Threshold Group Testing.- Testing Non-uniform k-Wise Independent Distributions over Product Spaces.- Session 10-Track A1. Approximations.- A Sublogarithmic Approximation for Highway and Tollbooth Pricing.- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm.- Cell Probe Lower Bounds and Approximations for Range Mode.- SDP Gaps for 2-to-1 and Other Label-Cover Variants.- Session 10-Track A2. Streaming & Preprocessing.- Data Stream Algorithms for Codeword Testing.- Streaming Algorithms for Independent Sets.- Preprocessing of Min Ones Problems: A Dichotomy.- Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems.- Session 11-Track A1. Adaptive, Knowledge & Optimality.- Optimal Trade-Offs for Succinct String Indexes.- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.- Concurrent Knowledge Extraction in the Public-Key Model.- Session 11-Track A2. Covering, Graphs & Independence.- On the k-Independence Required by Linear Probing and Minwise Independence.- Covering and Packing in Linear Space.- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs.