
Automata, Languages and Programming
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Content
- 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
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.