Interactive proofs and the hardness of approximating cliques
From MaRDI portal
Publication:4371671
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.
- scientific article; zbMATH DE number 7250157 (Why is no real title available?)
- The complexity of estimating min-entropy
- Some recent strong inapproximability results
- Interactive proofs for social graphs
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Testing properties of directed graphs: acyclicity and connectivity*
- Combinatorial algorithms for distributed graph coloring
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- On Dinur’s proof of the PCP theorem
- Derandomized parallel repetition via structured PCPs
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- From local to robust testing via agreement testing
- Pseudo-Boolean optimization
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Inapproximability results for equations over infinite groups
- ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
- Quantum and non-signalling graph isomorphisms
- Parallel repetition of two-prover one-round games: an exposition
- Bounds on 2-query locally testable codes with affine tests
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Combinatorial algorithms for distributed graph coloring
- Quantum XOR games
- Cryptography from planted graphs: security with logarithmic-size messages
- Short locally testable codes and proofs: a survey in two parts
- Randomness and computation
- Fast approximate probabilistically checkable proofs
- Composition of low-error 2-query PCPs using decodable PCPs
- The graph clustering problem has a perfect zero-knowledge interactive proof
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Parameterized inapproximability of independent set in \(H\)-free graphs
- Succinct non-interactive arguments via linear interactive proofs
- The Complexity of Zero Knowledge
- Simple analysis of graph tests for linearity and PCP
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- On the approximability of clique and related maximization problems
- Max-3-Lin over non-abelian groups with universal factor graphs
- Spot-checkers
- A simple deterministic reduction for the gap minimum distance of code problem
- Hardness results for approximate pure Horn CNF formulae minimization
- Probabilistic checking against non-signaling strategies from linearity testing
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- On deciding the existence of perfect entangled strategies for nonlocal games
- A survey on the structure of approximation classes
- Synchronous values of games
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Towards optimal lower bounds for clique and chromatic number.
- Short locally testable codes and proofs
- Mathematics of computation through the lens of linear equations and lattices
- 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
- Linear-size constant-query IOPs for delegating computation
- Succinct arguments in the quantum random oracle model
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
- Interactive proofs with approximately commuting provers
- Quantum information and the PCP theorem
- New tools and connections for exponential-time approximation
- Testing algebraic geometric codes
- Zero knowledge and the chromatic number
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- STIR: Reed-Solomon proximity testing with fewer queries
- Shorter arithmetization of nondeterministic computations
- A PCP theorem for interactive proofs and applications
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- Extension complexity of independent set polytopes
- Testing low-degree polynomials over prime fields
- A generalization of maximal independent sets
- Three-player entangled XOR games are NP-hard to approximate
- Detecting communities is hard (and counting them is even harder)
- Commitments to quantum states
- 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
- Annealed replication: A new heuristic for the maximum clique problem
- Optimal testing of Reed-Muller codes
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Approximation algorithms for minimum chain vertex deletion
- 2-transitivity is insufficient for local testability
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Verifiable isogeny walks: towards an isogeny-based postquantum VDF
- Algebraic testing and weight distributions of codes.
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
- Greedy maximal independent sets via local limits
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
- Bravely, moderately: a common theme in four recent works
- UG-hardness to NP-hardness by losing half
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- A toolbox for barriers on interactive oracle proofs
- On weighted vs unweighted versions of combinatorial optimization problems
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)
