Automata, Languages and Programming

Inhaltsverzeichnis

• Invited Talks.
• Local Search: Simple, Successful, But Sometimes Sluggish.
• When Conflicting Constraints Can Be Resolved – The Lovász Local Lemma and Satisfiability.
• Session 1-Track A. Combinatorial Optimization.
• Plane Spanners of Maximum Degree Six.
• The Positive Semidefinite Grothendieck Problem with Rank Constraint.
• Cycle Detection and Correction.
• Decomposition Width of Matroids.
• Session 2-Track A1. Game Theory.
• The Cooperative Game Theory Foundations of Network Bargaining Games.
• On the Existence of Pure Nash Equilibria in Weighted Congestion Games.
• On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.
• Mean-Payoff Games and Propositional Proofs.
• Session 2-Track A2. Security.
• Online Network Design with Outliers.
• Efficient Completely Non-malleable Public Key Encryption.
• Polynomial-Space Approximation of No-Signaling Provers.
• From Secrecy to Soundness: Efficient Verification via Secure Computation.
• Session 3-Track A1. Data Structures.
• Mergeable Dictionaries.
• Faster Algorithms for Semi-matching Problems (Extended Abstract).
• Clustering with Diversity.
• New Data Structures for Subgraph Connectivity.
• Session 3-Track A2. Sorting & Hashing.
• Tight Thresholds for Cuckoo Hashing via XORSAT.
• Resource Oblivious Sorting on Multicores.
• Interval Sorting.
• Session 4-Track A. Graphs, Nets and Optimization.
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.
• Thresholded Covering Algorithms for Robust and Max-min Optimization.
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem.
• Metrical Task Systems and the k-Server Problem on HSTs.
• Session 5-Track A1. Scheduling.
• Scheduling Periodic Tasks in a Hard Real-Time Environment.
• Scalably Scheduling Power-Heterogeneous Processors.
• BetterScalable Algorithms for Broadcast Scheduling.
• Max-min Online Allocations with a Reordering Buffer.
• Session 5-Track A2. Graphs & Hypergraphs.
• Orientability of Random Hypergraphs and the Power of 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 Approximationsfor 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.