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 .
Recommendations
Cites work
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(only showing first 100 items - show all)- Computing and listing \(st\)-paths in public transportation networks
- Problems on finite automata and the exponential time hypothesis
- 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
- Domination parameters with number 2: interrelations and algorithmic consequences
- Greedy domination on biclique-free graphs
- On directed covering and domination problems
- Lift-and-project methods for set cover and knapsack
- Easy capacitated facility location problems, with connections to lot-sizing
- Approximation algorithm for the partial set multi-cover problem
- Minimum constellation covers: hardness, approximability and polynomial cases
- Optimal matroid partitioning problems
- Differentiating-total domination: approximation and hardness results
- Approximation in (poly-) logarithmic space
- On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
- Two-level hub Steiner trees
- The complexity of dependency detection and discovery in relational databases
- The minimum degree group Steiner problem
- An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence
- Tight bounds on subexponential time approximation of set cover and related problems
- Constant round distributed domination on graph classes with bounded expansion
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- On the complexity of minimum \(q\)-domination partization problems
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Approximation algorithm and hardness results for defensive domination in graphs
- Parallel algorithm for minimum partial dominating set in unit disk graph
- Hardness results of connected power domination for bipartite graphs and chordal graphs
- Minimum hitting set of interval bundles problem: computational complexity and approximability
- Algorithms for covering multiple submodular constraints and applications
- The \textsc{red-blue separation} problem on graphs
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Capacitated covering problems in geometric spaces
- A game theoretic approach for minimal connected dominating set
- System of unbiased representatives for a collection of bicolorings
- Improved approximation bounds for the minimum constraint removal problem
- Optimal facility location problem on polyhedral terrains using descending paths
- Global total \(k\)-domination: approximation and hardness results
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Algorithms for optimal replica placement under correlated failure in hierarchical failure domains
- Algorithmic results on double Roman domination in graphs
- An approximation algorithm for vehicle routing with compatibility constraints
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Computational aspects of optimal strategic network diffusion
- A primal-dual algorithm for the minimum partial set multi-cover problem
- Computing a small agreeable set of indivisible items
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Algorithm and hardness results on hop domination in graphs
- A parallel repetition theorem for entangled projection games
- The minimum k-storage problem on directed graphs
- Approximability of guarding weak visibility polygons
- Generalized threshold processes on graphs
- Low-degree test with polynomially small error
- Additive stabilizers for unstable graphs
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Exact learning from an honest teacher that answers membership queries
- The matroid intersection cover problem
- Deleting edges to restrict the size of an epidemic in temporal networks
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- On the approximation hardness of geodetic set and its variants
- Approximation algorithms for priority Steiner tree problems
- Unveiling the truth in liquid democracy with misinformed voters
- Approximation algorithms for the star k-hub center problem in metric graphs
- Analysis of the parity progression ratios
- Small value parallel repetition for general games
- Local search based approximation algorithms for two-stage stochastic location problems
- Dynamic sum-radii clustering
- Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
- A counterexample to strong parallel repetition
- Sensor placement for fault location identification in water networks: a minimum test cover approach
- Parallel repetition in projection games and a concentration bound
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- A PTAS for the Weighted Unit Disk Cover Problem
- Improved approximation algorithm for fault-tolerant facility placement
- The constant inapproximability of the parameterized dominating set problem
- Approximation algorithm for partial set multicover versus full set multicover
- Parallel repetition via fortification: analytic view and the quantum case
- Approximating approximate distance oracles
- Distributed Dominating Set Approximations beyond Planar Graphs
- Information value of two-prover games
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Tight bounds for single-pass streaming complexity of the set cover problem
- Fractional set cover in the streaming model
- Approximating dominating set on intersection graphs of rectangles and L-frames
- New results on directed edge dominating set
- Resolving conflicts for lower-bounded clustering
- Improved approximation bounds for the minimum constraint removal problem
- A Tight Bound for Stochastic Submodular Cover
- How to Keep an Eye on Small Things
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Anchored parallel repetition for nonlocal games
- On Geometric Set Cover for Orthants
- Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
- Approximation in (Poly-) Logarithmic Space
- On Polynomial Time Constructions of Minimum Height Decision Tree
- Stabbing rectangles by line segments -- how decomposition reduces the shallow-cell complexity
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)
