Analytical approach to parallel repetition
From MaRDI portal
Publication:5259598
DOI10.1145/2591796.2591884zbMath1315.91001arXiv1305.1979OpenAlexW2044471216MaRDI QIDQ5259598
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.1979
copositive programmingoperator normshardness of approximationset coverparallel repetitionlabel coverone-round two-player games
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
Anchored Parallel Repetition for Nonlocal Games ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Algorithmic aspects of small quasi-kernels ⋮ Two dependency constrained spanning tree problems ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Set selection under explorable stochastic uncertainty via covering techniques ⋮ Unique response Roman domination: complexity and algorithms ⋮ Controlling entity integrity with key sets ⋮ Real-time passenger bus routing problems with preferences and tradeoffs ⋮ Geometric dominating-set and set-cover via local-search ⋮ Complexity results on cosecure domination in graphs ⋮ Justifying groups in multiwinner approval voting ⋮ Safe sets and in-dominating sets in digraphs ⋮ Sequence Hypergraphs: Paths, Flows, and Cuts ⋮ Unnamed Item ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Unnamed Item ⋮ Locating service and charging stations ⋮ Observation routes and external watchman routes ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Adaptive Submodular Ranking and Routing ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ The Computational Complexity of and Approximation Algorithms for Variants of the Component Selection Problem ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Monitoring the edges of a graph using distances ⋮ How to Secure Matchings against Edge Failures ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Hardness results of global total \(k\)-domination problem in graphs ⋮ Computing and Listing st-Paths in Public Transportation Networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Capacitated discrete unit disk cover ⋮ Linear separation of connected dominating sets in graphs ⋮ Approximation in (Poly-) Logarithmic Space ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Unnamed Item ⋮ On Partial Covering For Geometric Set Systems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations ⋮ A distributed algorithm for a set cover game ⋮ On Directed Covering and Domination Problems ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Relativistic (or 2-Prover 1-Round) Zero-Knowledge Protocol for $$\mathsf {NP}$$ Secure Against Quantum Adversaries ⋮ On the complexity of minimum \(q\)-domination partization problems ⋮ Hardness results of global Roman domination in graphs ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Computing and listing \(st\)-paths in public transportation networks ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ 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 ⋮ Unnamed Item ⋮ Sensor placement for fault location identification in water networks: a minimum test cover approach ⋮ Exact learning from an honest teacher that answers membership queries ⋮ 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 ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Generalized threshold processes on graphs ⋮ The \textsc{red-blue separation} problem on graphs ⋮ The matroid intersection cover problem ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Tight approximation bounds for dominating set on graphs of bounded arboricity ⋮ Low-degree test with polynomially small error ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Time-approximation trade-offs for inapproximable problems ⋮ New Results on Directed Edge Dominating Set ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Additive stabilizers for unstable graphs ⋮ Capacitated covering problems in geometric spaces ⋮ A game theoretic approach for minimal connected dominating set ⋮ System of unbiased representatives for a collection of bicolorings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Local Search Based Approximation Algorithms for Two-Stage Stochastic Location Problems ⋮ Improved approximation bounds for the minimum constraint removal problem ⋮ Optimal facility location problem on polyhedral terrains using descending paths ⋮ Dynamic Sum-Radii Clustering ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- 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
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: Analytical approach to parallel repetition
