Interactive proofs and the hardness of approximating cliques
From MaRDI portal
Publication:4371671
DOI10.1145/226643.226652zbMATH Open0882.68129DBLPjournals/jacm/FeigeGLSS96OpenAlexW2086653003WikidataQ55870237 ScholiaQ55870237MaRDI QIDQ4371671FDOQ4371671
Authors: Shmuel Safra, Shafi Goldwasser, László Lovász, Mario Szegedy, 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/
Recommendations
- Clique problem, cutting plane proofs and communication complexity
- Interactive proofs with approximately commuting provers
- On the complexity of interactive proofs with bounded communication
- A hierarchy theorem for interactive proofs of proximity
- On hardness of approximating the parameterized clique problem
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- A PCP theorem for interactive proofs and applications
- The graph clustering problem has a perfect zero-knowledge interactive proof
- Interactive proofs of proximity: delegating computation in sublinear time
- Interactive proof systems and alternating time-space complexity
Cited In (94)
- On testing monomials in multivariate polynomials
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- The 2010 Benjamin Franklin Medal in Computer and Cognitive Science presented to Shafrira Goldwasser, Ph.D.
- Interactive proofs for social graphs
- The complexity of estimating min-entropy
- Testing properties of directed graphs: acyclicity and connectivity*
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Combinatorial algorithms for distributed graph coloring
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- On Dinur’s proof of the PCP theorem
- From local to robust testing via agreement testing
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Derandomized parallel repetition via structured PCPs
- ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
- Parallel repetition of two-prover one-round games: an exposition
- Pseudo-Boolean optimization
- Quantum and non-signalling graph isomorphisms
- Inapproximability results for equations over infinite groups
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Bounds on 2-query locally testable codes with affine tests
- Combinatorial algorithms for distributed graph coloring
- Quantum XOR games
- Short locally testable codes and proofs: a survey in two parts
- Randomness and computation
- Fast approximate probabilistically checkable proofs
- The graph clustering problem has a perfect zero-knowledge interactive proof
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Succinct non-interactive arguments via linear interactive proofs
- Simple analysis of graph tests for linearity and PCP
- On the approximability of clique and related maximization problems
- Spot-checkers
- Hardness results for approximate pure Horn CNF formulae minimization
- On deciding the existence of perfect entangled strategies for nonlocal games
- A survey on the structure of approximation classes
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Short locally testable codes and proofs
- Towards optimal lower bounds for clique and chromatic number.
- Extracting randomness: A survey and new constructions
- Tight size-degree bounds for sums-of-squares proofs
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- Interactive proofs with approximately commuting provers
- Linear-size constant-query IOPs for delegating computation
- Succinct arguments in the quantum random oracle model
- New tools and connections for exponential-time approximation
- Quantum information and the PCP theorem
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Zero knowledge and the chromatic number
- Testing algebraic geometric codes
- Title not available (Why is that?)
- A PCP theorem for interactive proofs and applications
- Extension complexity of independent set polytopes
- Shorter arithmetization of nondeterministic computations
- A generalization of maximal independent sets
- Testing low-degree polynomials over prime fields
- Three-player entangled XOR games are NP-hard to approximate
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Optimal testing of Reed-Muller codes
- Annealed replication: A new heuristic for the maximum clique problem
- 2-transitivity is insufficient for local testability
- Algebraic testing and weight distributions of codes.
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
- UG-hardness to NP-hardness by losing half
- A toolbox for barriers on interactive oracle proofs
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- On weighted vs unweighted versions of combinatorial optimization problems
- Title not available (Why is that?)
- Some recent strong inapproximability results
- Title not available (Why is that?)
- Cryptography from planted graphs: security with logarithmic-size messages
- Composition of low-error 2-query PCPs using decodable PCPs
- Parameterized inapproximability of independent set in \(H\)-free graphs
- The Complexity of Zero Knowledge
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Max-3-Lin over non-abelian groups with universal factor graphs
- A simple deterministic reduction for the gap minimum distance of code problem
- Probabilistic checking against non-signaling strategies from linearity testing
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Synchronous values of games
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Mathematics of computation through the lens of linear equations and lattices
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
- STIR: Reed-Solomon proximity testing with fewer queries
- Commitments to quantum states
- Detecting communities is hard (and counting them is even harder)
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Verifiable isogeny walks: towards an isogeny-based postquantum VDF
- Approximation algorithms for minimum chain vertex deletion
- Greedy maximal independent sets via local limits
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
- Bravely, moderately: a common theme in four recent works
This page was built for publication: Interactive proofs and the hardness of approximating cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371671)
