Automata, Languages, and Programming

Name: Automata, Languages, and Programming | 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I

Artur Czumaj Kurt Mehlhorn Andrew Pitts Roger Wattenhofer(Herausgeber*in)

Springer (Verlag)

Erschienen am 23. Juni 2012

860 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31594-7 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Organization
Table of Contents
Track A - Algorithms, Complexity and Games
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method
Introduction
Motivation and Past Work
Past Work on the Interpolation Method for Random CSPs
Highlights of the Interpolation Method on RCSPs
Why an Energetic Interpolation Method
Energetic Interpolation for General CSPs
The Interpolation Method on Sparse Degree Sequences
Applying Energetic Interpolation to Random CSPs
Random k-SAT
Random Max-k-Lin-2
Computing Explicit Energetic Interpolation Bounds for k-SAT
References
The NOF Multiparty Communication Complexity of Composed Functions
Introduction
Preliminaries
Communication Complexity of Composed Functions
sym g
modm g
maj g
nor g
Conclusion
References
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
Introduction
Technical Preliminaries
Quantum Upper and Lower Bound
Classical Upper and Lower Bound
Conclusion
References
Efficient Submodular Function Maximization under Linear Packing Constraints
Introduction
Submodular Maximization with Linear Packing Constraints
The Algorithm
Analysis
Submodular Maximization with Binary Packing Constraints
The Algorithm
Analysis
References
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
Introduction, Main Results
Technical Ingredients
Strategy for the Main Result
Organization of the Paper
Group-Theoretic Preliminaries
Twisted Code Equivalence
Permutational Isomorphism for Transitive Groups
Further Group-Theoretic Preliminaries
Transitive Groups: Outline of the Proof of Theorem 3
Semisimple Group Isomorphism: The Proof of Theorem 1
The Framework
Semisimple Groups with a Unique Minimal Normal Subgroup
All Semisimple Groups
Comparison with Prior Work
References
Clustering under Perturbation Resilience
Introduction
Notation and Preliminaries
-Perturbation Resilience for Center-Based Objectives
(, )-Perturbation Resilience for the k-Median Objective
Structure of (,)-Perturbation Resilience
Approximating the Optimal Clustering
-Perturbation Resilience for the Min-Sum Objective
Discussion and Open Questions
References
Secretary Problems with Convex Costs
Introduction
Notation and Preliminaries
Unconstrained Profit Maximization
Matroid-Constrained Profit Maximization
Multi-dimensional Profit Maximization
References
Nearly Simultaneously Resettable Black-Box Zero Knowledge
Introduction
Overview of Our Contribution
Other Related Work
Preliminaries, Definitions and Tools
Black-Box rZK with t-Resettable Soundness
From a rZK Proof System to a New rZK Proof System
An Admissible, Near-Compatible rZK Proof System
High-Level Simulator Strategy in the Proof of Theorem 6
References
Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity
Complexity of Complexity Can Be High
The Game
How White Can Win
Proof of Gacs' Theorem
Modified Game and the Proof of Theorem 1
Version for Prefix Complexity
Strings with Maximal Plain and Non-maximal Prefix-Free Complexity
References
On Quadratic Programming with a Ratio Objective
Introduction
Our Results
Algorithms for QP-Ratio
An (n1/3) Rounding Algorithm
Integrality Gap Instance
The Bipartite Case
Algorithms for Special Cases
Hardness of Approximating QP-Ratio
Candidate Hard Instances
Reduction from Random k-AND
Reductions from Ratio versions of CSPs
Normalized QP-Ratio
References
De-amortizing Binary Search Trees
Introduction
Pop-Tarts
Simulation
De-amortization
References
Efficient Sampling Methods for Discrete Distributions
Introduction
Subset Sampling
Proportional Sampling
Proportional Sampling on Unsorted Probabilities
Subset Sampling
Proportional Sampling on Sorted Probabilities
Special Case 1/2 1
General Case
Relaxations
References
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Introduction
Problem Setting, Main Result and Techniques
Related Results
Preliminaries
Linear Program and the Fractional Algorithm
Online Algorithm for a Fractional LP Solution
Randomized Rounding Algorithm
References
Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
Introduction
Related Work and Our Results
The Main Idea behind Our Algorithm
Extended LP Formulation
The LP
Algorithm
Clustering
Randomized Facility Opening
Analysis
How to Apply Scaling
References
Testing Coverage Functions
Introduction
The W-Transform: Characterizing Coverage Functions
Reconstructing Succinct Coverage Functions
Testing Coverage Functions Is Hard?
Consistent Coverage Functions and Farkas Lemma
Nullity of Farkas Certificate
W-Distance and Usual Distance
References
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
Introduction
Our Results and Techniques
Preliminaries
Basic Construction of Sparse Fault-Tolerant Spanners
Achieving Small Hop-Diameter
Achieving Bounded Degree
Fault-Tolerant Single-Sink Spanners
(k, 1 + )-VFTS with Bounded Degree
References
A Dependent LP-Rounding Approach for the k-Median Problem
Introduction
Our Results
The Approximation Algorithm for the k-Median Problem
Filtering Phase
Bundling Phase
Matching Phase
Sampling Phase
Outline of the Proof of the 3.25-Approximation Ratio
Running Time of the Algorithm
Generalization of the Algorithm to Variants of k-Median
Approximation Algorithms for Knapsack-Median and Matroid-Median
References
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
Introduction
Algorithm for Node-Weighted EC-SNDP and Proper Functions
A Primal-Dual Algorithm for the Augmentation Problem
Proof of Theorem 3
References
Computing the Visibility Polygon of an Island in a Polygonal Domain
Introduction
Preliminaries
Our Algorithm
Observations
Computing Vis(P*)
The Convex Version
References
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Introduction
Preliminaries
Iterative Compression
Covering the Shadow of a Solution
Reducing the Instance by Torso
Finding a Shadowless Solution
FPT Algorithm for Disjoint Subset-DFVS Reduction
Conclusion and Open Problems
References
Max-Cut Parameterized above the Edwards-Erd?os Bound
Introduction
Preliminaries
Fixed-Parameter Algorithm for Max-Cut above the Edwards-Erdos Bound
Polynomial Kernel for Max-Cut above Edwards-Erdos
Discussion and Open Problems
References
Clique Cover and Graph Separation: New Incompressibility Results
Introduction
Preliminaries
Clique Cover
AND-Cross-Composition
Cross-Composition
Directed Multiway Cut
Multicut
bold0mu mumu kkkkkk-Way Cut
Conclusion and Open Problems
References
The Inverse Shapley Value Problem
Introduction
Reformulation of Shapley-Shubik Indices
A Useful Anti-concentration Result
A Useful Algorithmic Tool
Our Main Results
References
Zero-One Rounding of Singular Vectors
Introduction
Our Results
Related Work
Preliminaries and Notation
Dyadic Rounding of Vectors
Rounding Singular Vectors
Rounding Multiple Singular Vectors Simultaneously
Rounding SVD to Cut Decompositio
Open Problems
References
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
Introduction
Label Cover and Probabilistically Checkable Proofs
The Basic k-Spanner Problem and Previous Work
Our Results
The Error in ELD and Our Techniques
Sampling Lemma for 2-Query PCPs
Label Cover and Min-Rep with Large (Super)Girth
References
Space-Constrained Interval Selection
Introduction
Preliminaries
The Main Algorithm
Lower Bound(s)
References
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
*-0.1in Introduction
Definitions and Background
Generalizing Newton's Method Using Linear Programming
References
Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima
Introduction
Preliminaries
The Data Structure
A Recursive Formulation and Its Space Usage
The Slab-Rank and Slab-Select Problems
Encoding 2-Sided Queries
Data Structures for 2-Sided Queries
Putting Things Together
Succinct Indices for 2-Sided Queries
Conclusions
References
Universal Factor Graphs
Introduction
Preprocessing
Universal Factor Graphs
Some Research Goals
Related Work
Our Results
Overview of Proofs
Subexp-Universal Families
Threshold-Universal Families
Threshold-Universal Families with Nearly Tight Bounds
References
Parameterized Approximation via Fidelity Preserving Transformations
Introduction
Our Results
Related Work
Main Technique: Fidelity Preserving Transformations
Approximation via Shrinking
-Fidelity Kernels
Parametrization by Problem Objective
Obtaining -Shrinking by Simple Reduction Steps
Applications of the Technique
The Parametrized Steiner Tree Problem
The Shrinking Technique for Parameterized Steiner Tree
Applicability
Discussion
References
Backdoors to Acyclic SAT
Introduction
Weak Backdoor Sets
Strong Backdoor Sets
#SAT and Implied Cycle Cutsets
Preliminaries
Background and Methods
Weak Forest-BDSs
Strong Forest-BDSs
Conclusion
References
Dominators, Directed Bipolar Orders, and Independent Spanning Trees
Introduction
Terminology and Related Work
Linear-Time Verification and Construction Algorithms
Alternative Verification Algorithms
Using Headers
Using Semidominators
References
Hardness of Approximation for Quantum Problems
Introduction and Results
Definitions
Hardness of Approximation
A Canonical cq2-Complete Problem
References
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)
Introduction
Preliminaries
The Tutte Polynomial
Implementing New Edge Weights, Series Compositions and Parallel Compositions
Computational Problems
A Glimpse at the Hardness Result
A Very Brief Glimpse at the Tractability Results
Putting Things Together for Points with |y|&1
References
Stochastic Vehicle Routing with Recourse
Introduction
Algorithm for Polynomial Scenarios
Algorithm for General Distributions
UGC Hardness of Approximation
References
The Online Metric Matching Problem for Doubling Metrics
Introduction
Notation and Preliminaries
The Harmonic Algorithm for the Line
Proof of the Hybrid Lemma: A Coupling Argument
The Random-Subtree Algorithm
References
Approximating Sparse Covering Integer Programs Online
Introduction
An Algorithm for a Special Class for Covering LPs
The Online Algorithm for CIPs
Fractional Solution with Upper Bounds and KC-inequalities
Online Rounding
References
Streaming and Communication Complexity of Clique Approximation
Introduction
Problem Definitions
Our Methodology
Lower Bounds
r vs. logn
R(s)-1 vs. s-1
r2 vs. 2r-1
Upper Bounds
References
Distributed Private Heavy Hitters
Introduction
Our Results
Our Techniques
Related Work
Preliminaries
Differential Privacy
Probabilistic Tools
Information Theoretic Upper and Lower Bounds.
An Upper Bound via Johnson-Lindenstrauss Projections
A Lower Bound via Anti-concentration
Efficient Algorithms
GLPS Sparse Recovery
The Bucket Mechanism
Discussion and Open Questions
References
A Thirty Year Old Conjecture about Promise Problems
Introduction
Preliminaries
ESY Conjecture
Unpredictability
ESY Conjecture for Bounded Truth-Table Reductions
Length-Increasing Reductions
General Reductions
Application to Probabilistic Encryption
Discussion
References
Minimum Latency Submodular Cover
Introduction
Algorithm for Minimum Latency Submodular Cover
Stochastic Submodular Ranking
References
Constant-Time Algorithms for Sparsity Matroids
Introduction
Preliminaries
Testing (k,)-Fullness
Approximating the Rank of Mk,0(G)
Approximating the Rank of Mk,(G)
Testing (k, )-Edge-Connected-Orientability
References
CRAM: Compressed Random Access Memory
Introduction
Our Contributions
Organization of the Paper
Preliminaries
Empirical Entropy
Review of Ferragina and Venturini's Data Structure
Entropies of Similar Strings
Memory Management
A Data Structure for Maintaining the CRAM
Phase 0: Preprocessing
Algorithm for Access
Algorithm for Replace
Space Analysis
Concluding Remarks
References
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
Introduction
Preliminaries
Quantum Query Framework
Quantum Search Algorithms
Graph Collision
Problem Description
Relation to Boolean Matrix Multiplication
Algorithm for Graph Collision
Boolean Matrix Multiplication
Algorithm
Lower Bound
References
Faster Fully Compressed Pattern Matching by Recompression
Introduction
Basic Notions, Outline of the Algorithm
Details
References
NNS Lower Bounds via Metric Expansion for l8 and EMD
Introduction
Expansion and Its Relation to Complexity of NNS
Robust Expansion of l
Earth Mover Distance
References
Quantum Adversary (Upper) Bound
Introduction
A Nonconstructive Upper Bound on Query Complexity
Example Where the General Adversary Upper Bound Is Useful
Quantum Algorithms for Constant-Fault Direct Trees
Span Program Algorithm
Quantum Haar Transform Algorithm
Extensions and Related Problems
Conclusions and Future Work
References
Solving PLANAR k-TERMINAL CUT in O(ncVk) Time
Introduction
Preliminaries
Reducing the Problem to the Biconnected Case
Algorithm for Problem B
Proof of Theorem 4.7
Realization
References
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
Introduction
Preliminaries
Important Separators and Shadows
The Algorithm
Potential Function and Simple Operations
Degree Reduction
Overview on the Branching Step
Branchings and Reductions
Conclusions
References
Preserving Terminal Distances Using Minors
Introduction
Our Results
Related Work
A Lower Bound of (k2)
(k) Bounds for Constant Treewidth Graphs
An Upper Bound of O(p3k)
A Lower Bound of (pk)
Concluding Remarks
References
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Introduction
Our Results
Notations
An Approximation Algorithm for Min-Size k-ACSS
A Lower Bound on the Integrality Gap
Construction
Lower Bounding the Integrality Gap
Conclusion
References
Classical and Quantum Partition Bound and Detector Inefficiency
Introduction
Communication Complexity and the Partition Bound
Bell Experiments
Summary of Results
Related Work
Preliminaries
Classical Partition Bound
Local and Quantum Distributions
Communication Complexity Measures
Partition Bound and Detector Inefficiency
The Partition Bound for Distributions
The Efficiency Bound
Lower Bound for Quantum Communication Complexity
Proving Concrete Lower Bounds Using the Dual
Upper Bounds for One- and Two-Way Communication
Conclusion and Open Problems
References
Testing Similar Means
Introduction
Our Contributions
Related Work
Results for the Query Model
Results for the Sampling Model
A Lower Bound
Upper Bounds
References
The Parameterized Complexity of k-Edge Induced Subgraphs
Introduction
Our Approach
Counting k-Edge Induced Subgraphs
Organization of Our Paper
Preliminaries
Parameterized Complexity
Graphs
Relational Structures and First-Order Logic
Tree-Width and Local Tree-Width
Some Easy Positive Instances
A Further Combinatorial Lemma
Easy Instances by Model-Checking
The Algorithm
Counting k-Edge Induced Subgraphs
References
Converting Online Algorithms to Local Computation Algorithms
Introduction
Background
Our Results
Related Work
Preliminaries
Bounding the Size of a Random Query Tree
The Problem and Our Main Results
Overview of the Proof
Bounding the Increase in Subtree Size as We Go Up Levels
Hypergraph 2-Coloring and k-CNF
Maximal Matching
The Bipartite Case and Local Load Balancing
The Bipartite Case
Local Load Balancing
Random Ordering
References
Assigning Sporadic Tasks to Unrelated Parallel Machines
Introduction
Preliminaries
Arbitrary Number of Machines
Constant Number of Machines
References
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
Introduction
The Reduction
Gadget Construction
Construction
Pair (x,y) Multiway Cut
Multiway Cut pair (x,y)
References
The Power of Recourse for Online MST and TSP
Introduction
Problem Definitions
An Online PTAS with Amortized Constant Budget
The Non-amortized Scenario
A Greedy Algorithm with Budget 2
The Full Information Scenario
Applications to TSP
References
Geometry of Online Packing Linear Programs
Introduction
OTP for Almost 1-dim Columns
Connection to PAC Learning
Similarity via Witnesses
Small Witness Sets for Almost 1-dim Columns
Robust OTP
Robust DPA
Open Problems
References
Self-assembly with Geometric Tiles
Introduction
Overview
Results
Model
Basics
Geometric Tiles and the Basic (GTAM)
Two-Handed Geometric Tile Assembly Model
GTAM Complexities: Squares and =1 Assembly
n n 2GAM Squares with O(loglogn) Tile Types
References
Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation
Introduction
The Configuration LP
Local Search with Better Run-Time Analysis
Description of Algorithm
Example of Algorithm Execution
Analysis of Algorithm
Conclusions
References
Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
Introduction
Representation, Commitment, and Translation
Validation Domain: The Financial Application Domain Settings
Inputs and Straight Line Computations
Generic Commitment Schemes
The Main Theorem: SBB ZK Arguments for SLC
Proving Correctness of Additions and Equalities
Proving Correctness of Multiplications
Proving Inequalities x y, When x,y & p/32
Exponential Reduction of Probability of Cheating and Multiple Proofs of Correctness
Putting It All Together
References
Parameterized Tractability of Multiway Cut with Parity Constraints
Introduction
Preliminaries
PMWC Parameterized by the Solution Size
Bounding the Number of Even Terminals
Removing Even Terminals
Important Separators
Important Separator Sequences and a Generalization of Important Separators
Conclusion
References
Set Cover Revisited: Hypergraph Cover with Hard Capacities
Introduction
Our Approach and Contributions
Vertex Cover on Multigraphs with Hard Capacities
Rounding Algorithm
Proof of Theorem 3
Rounding Algorithm for MM
References
On the Limits of Sparsification
Introduction
Preliminaries
Basic Complexity Notions
Sparsification and Simplification
The Limits of Sparsification
Non-sparsifiability of CNFs
A Hierarchy Theorem for Non-Sparsifiability
Simplifying AC0 to CNFs
Circuit Lower Bounds for Depth-3 Circuits
References
Certifying 3-Connectivity in Linear Time
Introduction
BG-Paths
Chain Decompositions and Certificates
A Certifying Algorithm for 3-Connectivity in Linear Time
Reduction to Overlapping Intervals
References
Epsilon-Net Method for Optimizations over Separable States
Introduction
Epsilon Net
The Main Algorithm
Simulation of Several Variants of QMA(2)
Exponential Running Time Algorithm in 69645069 1muQ1mu86422285 F
References
Faster Algorithms for Privately Releasing Marginals
Introduction
Our Results and Techniques
Preliminaries
Differentially Private Sanitizers
Query Function Families
Polynomial Approximations
From Polynomial Approximations to Data Release Algorithms
Applications
Releasing Monotone Disjunctions
Releasing Monotone r-of-k Queries
Releasing Decision Lists
References
Stochastic Matching with Commitment
Introduction
Our Results
Previous Work
Informal Description of the Proof Technique
Preliminaries
The Model
Definitions
Sampling Technique
Matching Algorithm on Unweighted Erdos-Rényi graphs
Analysis
References
Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
Introduction
Our Results
Earth-Mover Distance
Introduction to Earth-Mover Distance
Applying our Results to Earth-Mover Distance
The Embedding
Analysis
No Underestimation
No Overestimation
Proof for Theorem 2
References
A Matrix Hyperbolic Cosine Algorithm and Applications
Introduction
Balancing Matrices: A Matrix Hyperbolic Cosine Algorithm
Alon-Roichman Expanding Cayley Graphs
Fast Isotropic Sparsification and Spectral Sparsification
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken