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
(only showing first 100 items - show all)- Testing algebraic geometric codes
- Zero knowledge and the chromatic number
- Extracting randomness: A survey and new constructions
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Spot-checkers
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Annealed replication: A new heuristic for the maximum clique problem
- Tight size-degree bounds for sums-of-squares proofs
- On weighted vs unweighted versions of combinatorial optimization problems
- 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
- Fast approximate probabilistically checkable proofs
- 2-transitivity is insufficient for local testability
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Interactive proofs for social graphs
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- Succinct non-interactive arguments via linear interactive proofs
- A PCP theorem for interactive proofs and applications
- Succinct arguments in the quantum random oracle model
- Linear-size constant-query IOPs for delegating computation
- Combinatorial algorithms for distributed graph coloring
- Hardness results for approximate pure Horn CNF formulae minimization
- New tools and connections for exponential-time approximation
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Quantum and non-signalling graph isomorphisms
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- On the severity of Braess's paradox: designing networks for selfish users is hard
- The complexity of estimating min-entropy
- 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
- On deciding the existence of perfect entangled strategies for nonlocal games
- Bounds on 2-query locally testable codes with affine tests
- Three-player entangled XOR games are NP-hard to approximate
- Quantum XOR games
- The graph clustering problem has a perfect zero-knowledge interactive proof
- Testing low-degree polynomials over prime fields
- Approximation algorithms for minimum chain vertex deletion
- 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
- Combinatorial algorithms for distributed graph coloring
- On Dinur’s proof of the PCP theorem
- Interactive proofs with approximately commuting provers
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- On testing monomials in multivariate polynomials
- The 2010 Benjamin Franklin Medal in Computer and Cognitive Science presented to Shafrira Goldwasser, Ph.D.
- ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Testing properties of directed graphs: acyclicity and connectivity*
- A survey on the structure of approximation classes
- Extension complexity of independent set polytopes
- Detecting communities is hard (and counting them is even harder)
- Simple analysis of graph tests for linearity and PCP
- 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
- Shorter arithmetization of nondeterministic computations
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Some recent strong inapproximability results
- Probabilistic checking against non-signaling strategies from linearity testing
- UG-hardness to NP-hardness by losing half
- From local to robust testing via agreement testing
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- scientific article; zbMATH DE number 7250157 (Why is no real title available?)
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- Parallel repetition of two-prover one-round games: an exposition
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- The Complexity of Zero Knowledge
- A simple deterministic reduction for the gap minimum distance of code problem
- Parameterized inapproximability of independent set in \(H\)-free graphs
- A generalization of maximal independent sets
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- Max-3-Lin over non-abelian groups with universal factor graphs
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- A toolbox for barriers on interactive oracle proofs
- Mathematics of computation through the lens of linear equations and lattices
- Derandomized parallel repetition via structured PCPs
- Commitments to quantum states
- Greedy maximal independent sets via local limits
- Cryptography from planted graphs: security with logarithmic-size messages
- Synchronous values of games
- Verifiable isogeny walks: towards an isogeny-based postquantum VDF
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
- STIR: Reed-Solomon proximity testing with fewer queries
- Towards a proof of the 2-to-1 games conjecture
- On independent sets, 2-to-2 games and Grassmann graphs
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- Parameterized inapproximability hypothesis under ETH
- An invariance principle for the multi-slice, with applications
- Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
- Property testing with online adversaries
- On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
- Parallel repetition of k-player projection games
- On approximability of satisfiable k-CSPs. I
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)
