Automata, Languages and Programming

Name: Automata, Languages and Programming | 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011. Proceedings, Part I
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011. Proceedings, Part I

Luca Aceto Monika Henzinger Jirí Sgall(Herausgeber*in)

Springer (Verlag)

Erschienen am 21. Juni 2011

XXIV, 802 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

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

96,29 €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
Session A1: Network Design Problems
Improved Approximation for the Directed Spanner Problem
Introduction
An ${\tilde O}(\sqrt{n})$-Approximation for \directedspanner
Sampling
Antispanners, LP and the Separation Oracle
LP and Rounding for Graphs with Unit-Length Edges
An $\tilde O (n^{1/3})$-Approximation for {\sc Directed 3-Spanner} with
Conclusion
References
An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
Introduction
Preliminaries and Results
An Approximation Algorithm
Subset -Connected Graphs: Deficient Sets, Cores, Halo-Families and Halo-Sets
Covering Halo-Families via Rooted Subset (+1)-Connectivity
Preprocessing to Decrease the Number of Cores
Thickness of Terminals
An O(klog2k)-Approximation Algorithm for |T|2k
An O(klogk)-Approximation Algorithm for |T|k2
References
Approximation Schemes for Capacitated Geometric Network Design
Introduction
Preliminaries
Bounding the Number of Steiner Points in Optimal Solution
Vertex Types of a Minimizer
Graph Analysis and Cycle Argument
Quasi-Polynomial Time Approximation Scheme
Polynomial-Time Approximation Scheme for Single Sink
Final Remarks
References
An O(log n)-Competitive Algorithm for Online Constrained Forest Problems
Introduction
Preliminaries
The Algorithm and Its Analysis
The Primal-Dual Online Algorithm
The Online Prize-Collecting Steiner Tree Problem
Conclusion
References
Session A2: Quantum Computing
On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
Introduction
Preliminaries
The Partition Tree Method
Comparisons between the Powers
On the Advantage of the Factorization Norm Method over the Trace Distance Method
On the Advantage of the Trace Distance Method over the Partition Tree Method
Other Discussions of the Power Comparisons
Concluding Remarks and Open Questions
References
Advice Coins for Classical and Quantum Computation
Introduction
The Distinguishing Problem
The Quantum Case
Coins as Advice
Preliminaries
Superoperators and Linear Algebra
Advice Coin Complexity Classes
Quantum Mechanics Nullifies the Hellman-Cover Theorem
Upper-Bounding the Power of Advice Coins
OpenProblems
References
Quantum Commitments from Complexity Assumptions
Introduction
Definitions
Quantum Interactive Complexity Classes
Quantum Computational Distinguishability
Quantum Commitments
Quantum Commitments Unless $\class{QSZK} \subseteq \class{QMA}$
Quantum Commitments Unless $\class{QIP} \subseteq \class{QMA}$
References
Limitations on Quantum Dimensionality Reduction
Introduction
The JL Lemma in Quantum Information Theory
Our Results
Dimensionality Reduction in the 2-Norm
Operational Meaning of the 2-Norm
Equality Testing without a Reference Frame
Performing a Random Measurement
Dimensionality Reduction in the Trace Norm
Upper Bound
Lower Bound
Conclusions
References
Session A3: Graph Algorithms
On Tree-Constrained Matchings and Generalizations
Introduction
Our Results
Matching Trees
A 3-Approximation by Fractional Local Ratio
A 2-Approximation
Hardness and Inapproximability Results
Matching Posets
A Fractional Local Ratio Algorithm
Hardness
References
Tight Bounds for Linkages in Planar Graphs
Introduction
Preliminaries
Upper Bounds
Basic Definitions
Simple Properties of a Cheap Solution P
Bounding the Number of Segment Types
Bounding the Size of Segment Types
The Lower Bound
References
A Tighter Insertion-Based Approximation of the Crossing Number
Introduction
Preliminaries
Decomposition Trees
Single Edge Insertion with Variable Embedding
MEI Approximation Algorithm
Embedding Preferences and Estimating Additional Crossings via Dirty Passes
Combining All Embedding Preferences
Runtime Analysis of Algorithm 3.1
Crossing Number Approximations
A Note on the Planarization Heuristic
Conclusions
References
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
Introduction
Previous Work on Approximate Distance Oracles
Tunable Approximate Distance Oracle for Planar Graphs
Review of Thorup's Distance Oracle
Our Compact Distance Oracle
Improved Preprocessing Algorithm
Approximate Distance Oracles for Genus g Graphs
References
Session A4: Games, Approximation Schemes, Smoothed Analysis
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
Introduction
Our Results and Some Related Work
Preliminaries, Notation and Basic Properties
Approximation Schemes
Absolute Approximation
Relative Approximation
Uniformly Relative e-Approximation for BW-Games
Smoothed Analysis
References
Pairwise-Interaction Games
Introduction
Overview
Our Results
Related Work
Preliminaries
Notations
Strategic Games
Symmetric Payoff Matrices
Zero-Sum Games
Some Further Results
Open Problems
References
Settling the Complexity of Local Max-Cut (Almost) Completely
Introduction
Preliminaries
Substituting Certain Nodes of Unbounded Degree
Proof of PLS-Completeness
Smoothed Complexity of Local Max-Cut
Conclusion and Open Problems
References
Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
Introduction
Preliminaries
Overlap Structure
PTAS via Dynamic Programming
DP Array
Recurrence Relation
Approximate DP
Proof of Lemma 2
Hierarchical Clique Partition
Clique Clustering for a Single Clique
References
Session A5: Online Algorithms
On Variants of File Caching
Introduction
Reducing the Problem with Rejection to the Problem with Bypassing
Deterministic Algorithms
Caching with Rejection
An Improved Algorithm for Several Cases
Randomized Algorithms
References
On the Advice Complexity of the k-Server Problem
Introduction
A Lower Bound on the Optimality
An Upper Bound for the Euclidean Case
An Upper Bound for the General Case
Relation between Randomization and Advice
References
Sleep Management on Multiple Machines for Energy and Flow Time
Introduction
Sleep Management for Fixed-Speed Machines
Algorithm POOL
Potential Analysis of Fw
Sleep Management and Speed Scaling
Transformation of Offline Schedule
References
Meeting Deadlines: How Much Speed Suffices?
Introduction
The Yardstick Schedule
A Best Possible Deadline Ordered Online Algorithm
Description of the Algorithm
Analysis of the Algorithm
A Lower Bound for LLF
A Lower Bound for EDZL
Concluding Remarks
References
Session A6: Data Structures, Distributed Computing
Range Majority in Constant Time and Linear Space
Introduction
Related Work
Our Results
Range Majority Data Structure
Quadruple Decomposition
Candidates
Data Structures for Counting
Generalization to Range a-Majority Queries
Definitions
Relaxed Triples
Handling Large Alphabets
Concluding Remarks
References
Dynamic Planar Range Maxima Queries
Introduction
Preliminaries
Pointer-Based Data Structure
Data Structure
Query
Update
4-Sided Range Maxima Queries and Rectangular Visibility
3-sided Range Maxima in the RAM Model
Conclusion
References
Compact Navigation and Distance Oracles for Graphs with Small Treewidth
Introduction
Contribution
Tree Decompositions and Variations
Lower Bound
Navigation Oracles
Representing the Tree Decomposition
Neighbor Report
Distance Oracles
Conclusion
References
Player-Centric Byzantine Agreement
Introduction
The Model
Definition and Reductions
Perfect Security
Statistical and Computational Security (With Setup)
PCBA ({p}) (Broadcast with Sender p)
PCBA (C) for an Arbitrary |C |1
Extension: Adding Fail Corruption
Conclusions and Open Problems
References
Session A7: Complexity, Randomness
Limits on the Computational Power of Random Strings
Introduction
Derandomization from Uniform Hardness Assumptions
Background and Definitions
Main Results
Description of the Game
Perspective and Open Problems
References
The Decimation Process in Random k-SAT
Introduction
Results
Related Work
Analyzing the Decimation Process
Shattering, Pairwise Distances, and Ferromagnetism
Rigid Variables
References
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
Introduction
Preliminaries
Distributional Complexity
The 3-MAJh Function and the Hard Distribution
The Jayram-Kumar-Sivakumar Lower Bound
Improved Lower Bound
Improved Depth-Two Algorithm
References
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions
Introduction
Applications of the Conjecture
Prior Work
Our Results and Approach
Outline for the Rest of the Paper
Definitions and Notation
Basics of Boolean Fourier Analysis
Some Boolean Function Classes
Symmetric and d-Part-Symmetric Functions
Theorem 4: Derivatives of Symmetric Functions are Noise-Sensitive
Theorem 5: Spectral Level Entropy Versus Influence
Theorem 2: Extension to d-Part-Symmetric Functions
Closing Remarks
References
Session A8: Submodular Optimization, Matroids
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
Introduction
The Structural Continuous Greedy Algorithm
Taking Advantage of the Structural Continuous Greedy
Related Work
Preliminaries
The Structural Continuous Greedy Algorithm
Simulated Annealing Algorithm
References
Submodular Cost Allocation Problem and Applications
Introduction
Problems Related to MSCA
Overview of Results and Techniques
Monotone MSCA
Submodular Multiway Partition
A 1.5-Approximation for Hypergraph Multiway Partition
Algorithms for Hypergraph Multiway Cut
References
Robust Independence Systems
Introduction
Previous and Our Main Results for the Robustness
Exchangeable Independence Systems
Examples of Exchangeable Independence Systems
Exchangeability and Rank Quotient
Robust Independence Systems in Boolean Lattice
The Proof Outline of Lemma 4
The Proof of Theorem 2
References
Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
Introduction
Preliminaries
Model
Algorithm
Analysis of the Algorithm
Charging Scheme
Lower Bound
Contradiction
Construction of Sequence
References
Session A9: Cryptography, Learning
Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience
Introduction
Definitions
A Compiler Secure against $(\infty,\delta,q)$-Adversaries
References
New Algorithms for Learning in Presence of Errors
Introduction
Learning Parities with Structured Noise
Problem Definition
Constraints and Linearization
Proof for White Noise Case
Learning with Errors
Learning the Majority of Parities Function
Conclusions
References
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
Introduction
Preliminaries
Betting Games
Exact Learning
Exact Learning and Betting Games
References
Session A10: Fixed Parameter Tractability
Constraint Satisfaction Parameterized by Solution Size
Introduction
Preliminaries
Properties of Constraints
Weak Separability
Morphisms
Components
Multivalued Morphism Gadgets
Frequent Instances
Classification for Size Constraints
Classification for Cardinality Constraints
References
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
Introduction
Preliminaries
Kernelization with Respect to Vertex Cover Number: Eliminating Simplicial Vertices
A Polynomial Kernel for Treewidth Parameterized by Feedback Vertex Set
Almost Simplicial Vertices
Clique-Seeing Paths
The Kernelization
Kernelization Lower Bounds
Conclusions
References
Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Introduction
EDGE-SUBSET-FVS Parameterized by |S|
The Outer-Abundant Lemma
Bubbles
The Leaf Bubble Reduction
References
Domination When the Stars Are Out
Introduction
Algorithmic View of the Structure of Claw-Free Graphs
Application to Parameterized Algorithms
Polynomial Kernel for Dominating Set
References
Session A11: Hardness of Approximation
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Introduction
Organization
Preliminaries
Codes
Hardness of Constraint Satisfaction
The Binary Case
Reduction to Nearest Codeword
Reduction to Minimum Distance
Interlude: Linear Approximations to Nonlinear Codes
Reduction to Min Dist(q) for q $\geq$ 3
References
Recoverable Values for Independent Sets
Introduction
Our Results
Related Work
Our Techniques
Handling Low Degree Vertices
Algorithms for MWIS
Algorithms for MIS
MISink-Colored Graphs
References
Vertex Cover in Graphs with Locally Few Colors
Introduction
Vertex Cover Using Bounded Local Biclique Colorings
Vertex Cover in Graphs with Bounded Local Chromatic Number
The Scheduling Application
References
Maximizing Polynomials Subject to Assignment Constraints
Introduction
Overview of the Results
Tensor Triangle Inequality
Linear Programming Relaxation
Problems Satisfying the Tensor Triangle Inequality
Koopmans-Beckman Case: The Problem with Decomposable Coefficients
References
Session A12: Counting, Testing
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid
Introduction
Matroid Preliminaries
Tutte Polynomial and Decomposition
Signatures
The Algorithm
References
Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width
Introduction
Definitions
$\lambda$-Multiplicative Weight Functions
Glauber Dynamics for Edge Subsets
Results
Proof Outline
Vertex Subset Mixing for Bounded Tree-Width
Conclusion
References
Efficient Sample Extractors for Juntas with Applications
Introduction
Notation
Results
Upper Bounds
Lower Bounds
Proof of Theorem 1
Overview
Main Lemmas and Proof of Theorem 1
Additional Definitions and Lemmas
Junta Testers, Smoothness, and Tolerance
Obtaining a Good Pair (I, J)
Proof of Lemma 2
References
Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
Introduction
List Disjunct Matrices and Our Main Results
Applications and Other Results
Error-Correcting List-Disjunct/Separable Matrices
Intuition behind the Blackbox Conversion Procedures
Bounds
Constructions
Black-Box Conversion Using List Recoverability
Black-Box Conversion Using Recursion
Applications
References
Session A13: Complexity
Robust Simulations and Significant Separations
Introduction
Intuition and Techniques
Preliminaries
Complexity Classes, Promise Problems and Advice
Robust Simulations
Significant Separations
Hierarchies
Circuit Lower Bounds
Time-Space Tradeoffs
References
A PCP Characterization of AM
Introduction
CSPs, PCPs, and Complexity Classes
Our Results
Our Methods
Questions for Future Work
Preliminaries
Promise Problems and prAM
An Augmented PCPP
Proof of Theorem 1
Proof of Theorem 5
References
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
Introduction
Previous Results and Upper Bounds
The Cell-Probe Model
Online Convolution
Information Transfer
Recovering Information
The Lower Bound for Online Convolution
Online Multiplication
Retrorse Numbers and the Lower Bound
References
Session A14: Proof Complexity
Automatizability and Simple Stochastic Games
Introduction
Definitions
Main Result
Arithmetic Formulas
Proof of Uniqueness
Proving Max-Node$_n$
Removing the Bottom Fan-In
Consequences and Open Problems
References
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
Introduction
Proof Overview
Proof Systems
Reducing Formula Depth
Proof of Main Theorem
Moving Down the Depth Vector
Putting It Together
Applications and Consequences
Tightness of Our Simulation
Weak Automatizability
References
Parameterized Bounded-Depth Frege Is Not Optimal
Introduction
Parameterized Proof Complexity
Parameterized Versions of Ordinary Proof Systems
Parameterized Bounded-Depth Frege Is Not Weakly fpt-Bounded
Cores and Small Refutations
Discussion and Open Problems
References
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
Introduction
Preliminaries
An Improved Lower Bound for Minimal Unsatisfiability
A Weight Constraint k-DNF Formula Set
The Minimally Unsatisfiable k-DNF Set
Implications for k-DNF Resolution Trade-offs
Concluding Remarks and Open Problems
References
Session A15: Sorting, Matchings, Paths
Sorting by Transpositions Is Difficult
Preliminaries
3-Deletion and Transposition Operations
3DT-Collapsibility Is NP-Hard to Decide
Block Structure
Basic Blocks
Construction of I
Sorting by Transpositions Is NP-Hard
Conclusion
References
Popular Matchings in the Stable Marriage Problem
Introduction
Structural Results
Good Matchings
The Algorithm
Conclusions
References
Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices
Introduction
Preliminaries
Finding a Center of G(L)
The Center Set of G(L)
References
VC-Dimension and Shortest Path Algorithms
Introduction
Definitions
VC-Dimension and USP Systems
Highway Dimension and Shortest Path Covers
Improved Bounds
Extensions
Labeling Algorithm and Average Dimension
Cardinality-Based Highway Dimension
Concluding Remarks
References
Session A16: Constraint Satisfaction, Algebraic Complexity
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
Introduction and Related Work
Preliminaries
Arithmetic Circuit Complexity
CSPs.
.and Their Polynomials
Treewidth
Statement of the Results
Lower Bounds
Upper Bounds on the Complexity
References
The Complexity of Symmetric Boolean Parity Holant Problems
Introduction
Preliminaries
Tractable Families
Affine Signatures
Fibonacci Signatures and [0,1,0]
Matchgate Signatures
Hardness Results and Dichotomy for Holantc
An Initial Hard Problem
More Hardness Results and the Dichotomy
Vanishing Signature Sets
Dichotomy for the Whole Holant Family
References
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
Introduction
Techniques
Preliminaries
Representing Arithmetic Circuits over Z by Boolean Circuits Succinctly
Conditional Lower Bound for Permanent
Proving a Weak Derandomization Hypothesis Unconditionally
Proof of Theorem 1
References
On the Power of Algebraic Branching Programs of Width Two
Introduction
Preliminaries
IMM2,n under Homogeneous Projections
Classification of H2 2Indg
Structure of H2 2Indg-SLPs and Its Implications
Limitation of H2 2-SLPs
Extensions to Regular Projections
References
Session A17: Steiner Problems, Clustering
Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
Introduction
Preliminaries
The Primal-Dual Algorithm
A 3-Approximation on Planar Graphs
Lower Bound
A 9/4-Approximation Algorithm on Planar Graphs
References
Steiner Transitive-Closure Spanners of Low-Dimensional Posets
Introduction
Our Results
Applications
Definitions and Observations
Lower Bound for 2-TC-spanners of the Hypergrid
Lower Bound for k-TC-Spanners for k&2
References
Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
Introduction
Minimum Spanning Sphere
The Chromatic Cone Clustering Problem
Constant Ratio Approximation Algorithm for k=2
(1+) Algorithms for the Case of k=2
A (1+)-Approximation Algorithm for k&2
References
Clustering with Local Restrictions
Introduction
Clustering and Uncrossing
Parameterization by q
Important Separators and Important Sets
Reduction to the Satellite Problem
Solving the Satellite Problem
Parameterization by p
Hardness Results
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken