Interactive proofs and the hardness of approximating cliques
From MaRDI portal
Publication:4371671
DOI10.1145/226643.226652zbMath0882.68129OpenAlexW2086653003WikidataQ55870237 ScholiaQ55870237MaRDI QIDQ4371671
Mario Szegedy, Shafi Goldwasser, László Lovász, Shmuel Safra, Uriel Feige
Publication date: 21 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1996-43/
Related Items
Annealed replication: A new heuristic for the maximum clique problem, Algebraic testing and weight distributions of codes., Towards optimal lower bounds for clique and chromatic number., On the approximability of clique and related maximization problems, Bounds on 2-query locally testable codes with affine tests, Fast approximate probabilistically checkable proofs, Quantum information and the PCP theorem, Interactive Proofs with Approximately Commuting Provers, Succinct non-interactive arguments via linear interactive proofs, Simple analysis of graph tests for linearity and PCP, Some recent strong inapproximability results, Testing properties of directed graphs: acyclicity and connectivity*, Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, A PCP theorem for interactive proofs and applications, On locally decodable codes, self-correctable codes, and \(t\)-private PIR, Succinct arguments in the quantum random oracle model, Linear-size constant-query IOPs for delegating computation, On testing monomials in multivariate polynomials, The 2010 Benjamin Franklin Medal in Computer and Cognitive Science presented to Shafrira Goldwasser, Ph.D., Tight size-degree bounds for sums-of-squares proofs, Max-3-Lin over non-abelian groups with universal factor graphs, Quantum and non-signalling graph isomorphisms, Pseudorandom sets in Grassmann graph have near-perfect expansion, Deciding the existence of perfect entangled strategies for nonlocal games, Unnamed Item, A toolbox for barriers on interactive oracle proofs, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, Mathematics of computation through the lens of linear equations and lattices, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, 2-transitivity is insufficient for local testability, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, Unnamed Item, Extension Complexity of Independent Set Polytopes, Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms, Derandomized parallel repetition via structured PCPs, A survey on the structure of approximation classes, An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)), Parallel Repetition of Two-Prover One-Round Games: An Exposition, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Shorter arithmetization of nondeterministic computations, An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm, Combinatorial algorithms for distributed graph coloring, Hardness results for approximate pure Horn CNF formulae minimization, A generalization of maximal independent sets, Pseudo-Boolean optimization, Inapproximability results for equations over infinite groups, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Optimal Testing of Reed-Muller Codes, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, On the severity of Braess's paradox: designing networks for selfish users is hard, New tools and connections for exponential-time approximation, Testing low-degree polynomials over prime fields, Unnamed Item, Unnamed Item, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, The Complexity of Zero Knowledge, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, Approximation Algorithms for Minimum Chain Vertex Deletion, Parameterized inapproximability of independent set in \(H\)-free graphs, Three-Player Entangled XOR Games are NP-Hard to Approximate, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Short Locally Testable Codes and Proofs, Bravely, Moderately: A Common Theme in Four Recent Works, Randomness and Computation, Unnamed Item, Unnamed Item, Unnamed Item, UG-hardness to NP-hardness by losing half, Combinatorial Algorithms for Distributed Graph Coloring, Quantum XOR Games, Zero knowledge and the chromatic number, Spot-checkers, Testing algebraic geometric codes, Clique is hard to approximate within \(n^{1-\epsilon}\), On Dinur’s proof of the PCP theorem, Extracting randomness: A survey and new constructions, On weighted vs unweighted versions of combinatorial optimization problems, Unnamed Item, Spartan: efficient and general-purpose zkSNARKs without trusted setup, The complexity of estimating min-entropy
