Zur Zeit liegt uns keine Inhaltsangabe vor.
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.