A Parallel Repetition Theorem
From MaRDI portal
Publication:4388898
DOI10.1137/S0097539795280895zbMath0911.68082OpenAlexW1970259241WikidataQ56564995 ScholiaQ56564995MaRDI QIDQ4388898
Publication date: 10 May 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795280895
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (only showing first 100 items - show all)
Towards optimal lower bounds for clique and chromatic number. ⋮ On regularity of Max-CSPs and Min-CSPs ⋮ Bayesian agency: linear versus tractable contracts ⋮ Inapproximability results for equations over finite groups ⋮ Quantum information and the PCP theorem ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Simple analysis of graph tests for linearity and PCP ⋮ Quantum hedging in two-round prover-verifier interactions ⋮ Quantum coin hedging, and a counter measure ⋮ Generalized XOR non-locality games with graph description on a square lattice ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality ⋮ Approximating the minimal sensor selection for supervisory control ⋮ Anchored Parallel Repetition for Nonlocal Games ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ Interactive Information Complexity ⋮ A query efficient non-adaptive long code test with perfect completeness ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ A strong direct product theorem for quantum query complexity ⋮ An information statistics approach to data stream and communication complexity ⋮ Derandomized parallel repetition theorems for free games ⋮ Power optimization for connectivity problems ⋮ On generalizations of network design problems with degree bounds ⋮ Reoptimization of constraint satisfaction problems with approximation resistant predicates ⋮ Semi-quantum money ⋮ Unbounded violations of bipartite Bell inequalities via operator space theory ⋮ Classical, quantum and nonsignalling resources in bipartite games ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ On the hardness of learning intersections of two halfspaces ⋮ On the configuration LP for maximum budgeted allocation ⋮ Exponential inapproximability of selecting a maximum volume sub-matrix ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Parallel repetition of computationally sound protocols revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Quantum money with mintage supervision ⋮ Derandomized parallel repetition via structured PCPs ⋮ PCP characterizations of NP: toward a polynomially-small error-probability ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ An All-or-Nothing Flavor to the Church-Turing Hypothesis ⋮ Information value of two-prover games ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Information complexity and applications. ⋮ On the computational complexity of measuring global stability of banking networks ⋮ Random constructions in Bell inequalities: a survey ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Approximability of Capacitated Network Design ⋮ AN IMPLICIT COVER PROBLEM IN WILD POPULATION STUDY ⋮ Complete partitions of graphs ⋮ Improved approximation algorithms for projection games ⋮ Vertex cover might be hard to approximate to within \(2 - \varepsilon \) ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Eliminating cycles in the discrete torus ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Inapproximability results for equations over infinite groups ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Distinguishing Distributions Using Chernoff Information ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Parallel and Concurrent Security of the HB and HB + Protocols ⋮ Large violation of Bell inequalities with low entanglement ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Unnamed Item ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ A k-PROVERS PARALLEL REPETITION THEOREM FOR A VERSION OF NO-SIGNALING MODEL ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs ⋮ Short Locally Testable Codes and Proofs ⋮ On Approximating an Implicit Cover Problem in Biology ⋮ UG-hardness to NP-hardness by losing half ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Geometric stability via information theory ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Reducing complexity assumptions for statistically-hiding commitment ⋮ On the hardness of approximating label-cover ⋮ Approximating fault-tolerant group-Steiner problems ⋮ An Efficient Parallel Repetition Theorem ⋮ Parallel Repetition Theorems for Interactive Arguments ⋮ Almost Optimal Bounds for Direct Product Threshold Theorem ⋮ On Khot’s unique games conjecture ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ On Dinur’s proof of the PCP theorem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence ⋮ Unnamed Item ⋮ A parallel repetition theorem for entangled projection games ⋮ Rank-one quantum games
This page was built for publication: A Parallel Repetition Theorem
