
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
- 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
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.