Analytical approach to parallel repetition
From MaRDI portal
Publication:5259598
DOI10.1145/2591796.2591884zbMATH Open1315.91001arXiv1305.1979OpenAlexW2044471216MaRDI QIDQ5259598FDOQ5259598
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Abstract: We propose an analytical framework for studying parallel repetition, a basic product operation for one-round two-player games. In this framework, we consider a relaxation of the value of a game, , and prove that for projection games, it is both multiplicative (under parallel repetition) and a good approximation for the true value. These two properties imply a parallel repetition bound as mathrm{val}(G^{otimes k}) approx mathrm{val}_+(G^{otimes k}) = mathrm{val}_+(G)^{k} approx mathrm{val}(G)^{k}. Using this framework, we can also give a short proof for the NP-hardness of Label-Cover for all , starting from the basic PCP theorem. We prove the following new results: - A parallel repetition bound for projection games with small soundness. Previously, it was not known whether parallel repetition decreases the value of such games. This result implies stronger inapproximability bounds for Set-Cover and Label-Cover. - An improved bound for few parallel repetitions of projection games, showing that Raz's counterexample is tight even for a small number of repetitions. Our techniques also allow us to bound the value of the direct product of multiple games, namely, a bound on for different projection games .
Full work available at URL: https://arxiv.org/abs/1305.1979
set coverhardness of approximationcopositive programmingparallel repetitionoperator normslabel coverone-round two-player games
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Games involving graphs (91A43)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster Algorithms for Privately Releasing Marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (only showing first 100 items - show all)
- Easy capacitated facility location problems, with connections to lot-sizing
- Approximation in (Poly-) logarithmic space
- Capacitated discrete unit disk cover
- Hardness results of global total \(k\)-domination problem in graphs
- Algorithms for covering multiple submodular constraints and applications
- Approximation algorithm for partial set multicover versus full set multicover
- Hardness results of global Roman domination in graphs
- Greedy domination on biclique-free graphs
- Computing and Listing st-Paths in Public Transportation Networks
- Linear separation of connected dominating sets in graphs
- Complexity and algorithms for semipaired domination in graphs
- On directed covering and domination problems
- Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- The complexity of dependency detection and discovery in relational databases
- Deleting edges to restrict the size of an epidemic in temporal networks
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- Geometric hitting set for segments of few orientations
- Whom to befriend to influence people
- Upper and lower bounds on approximating weighted mixed domination
- On Polynomial Time Constructions of Minimum Height Decision Tree
- Tropical dominating sets in vertex-coloured graphs
- Local Search Based Approximation Algorithms for Two-Stage Stochastic Location Problems
- Covering compact metric spaces greedily
- The ordered covering problem
- Computing and listing \(st\)-paths in public transportation networks
- Minimum constellation covers: hardness, approximability and polynomial cases
- A parallel repetition theorem for entangled projection games
- The minimum degree group Steiner problem
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Two dependency constrained spanning tree problems
- Improved Approximation Algorithm for Fault-Tolerant Facility Placement
- Approximation algorithm for the partial set multi-cover problem
- Optimal matroid partitioning problems
- Set selection under explorable stochastic uncertainty via covering techniques
- Exact learning from an honest teacher that answers membership queries
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Sensor placement for fault location identification in water networks: a minimum test cover approach
- Differentiating-total domination: approximation and hardness results
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Problems on finite automata and the exponential time hypothesis
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Title not available (Why is that?)
- Approximation in (Poly-) Logarithmic Space
- Title not available (Why is that?)
- A PTAS for the Weighted Unit Disk Cover Problem
- Tight approximation bounds for dominating set on graphs of bounded arboricity
- Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
- Time-approximation trade-offs for inapproximable problems
- Lift-and-project methods for set cover and knapsack
- A primal-dual algorithm for the minimum partial set multi-cover problem
- On Geometric Set Cover for Orthants
- Additive stabilizers for unstable graphs
- On Partial Covering For Geometric Set Systems
- Distributed Dominating Set Approximations beyond Planar Graphs
- On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
- Two-level hub Steiner trees
- Domination parameters with number 2: interrelations and algorithmic consequences
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- Dynamic Sum-Radii Clustering
- Tight bounds on subexponential time approximation of set cover and related problems
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Parallel Repetition of Two-Prover One-Round Games: An Exposition
- The minimum \(k\)-storage problem on directed graphs
- Approximation algorithms for the connected sensor cover problem
- Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis
- A Tight Bound for Stochastic Submodular Cover
- On minimum maximal distance-\(k\) matchings
- Improved approximation algorithms for projection games
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs
- Linear conic formulations for two-party correlations and values of nonlocal games
- Title not available (Why is that?)
- Roman \(\{3\}\)-domination in graphs: complexity and algorithms
- Optimal facility location problem on polyhedral terrains using descending paths
- How to Secure Matchings against Edge Failures
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence
- The matroid intersection cover problem
- Global total \(k\)-domination: approximation and hardness results
- Title not available (Why is that?)
- Safe sets and in-dominating sets in digraphs
- An approximation algorithm for vehicle routing with compatibility constraints
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
- Title not available (Why is that?)
- Algorithm and hardness results on hop domination in graphs
- Anchored Parallel Repetition for Nonlocal Games
- Title not available (Why is that?)
- Online multiset submodular cover
- Algorithmic results on double Roman domination in graphs
- Capacitated Covering Problems in Geometric Spaces
- Analysis of the parity progression ratios
- On the complexity of minimum \(q\)-domination partization problems
- Approximability of guarding weak visibility polygons
- A distributed algorithm for a set cover game
- System of unbiased representatives for a collection of bicolorings
- Lower bounds of functions on finite abelian groups
- Algorithmic aspects of small quasi-kernels
Uses Software
This page was built for publication: Analytical approach to parallel repetition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259598)
