Pages that link to "Item:Q4371671"
From MaRDI portal
The following pages link to Interactive proofs and the hardness of approximating cliques (Q4371671):
Displaying 50 items.
- The complexity of estimating min-entropy (Q260395) (← links)
- Bounds on 2-query locally testable codes with affine tests (Q280942) (← links)
- On testing monomials in multivariate polynomials (Q391220) (← links)
- The 2010 Benjamin Franklin Medal in Computer and Cognitive Science presented to Shafrira Goldwasser, Ph.D. (Q398324) (← links)
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy (Q430828) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm (Q498420) (← links)
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR (Q603915) (← links)
- Derandomized parallel repetition via structured PCPs (Q645129) (← links)
- Pseudo-Boolean optimization (Q697569) (← links)
- Quantum information and the PCP theorem (Q835644) (← links)
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)) (Q924126) (← links)
- Inapproximability results for equations over infinite groups (Q974745) (← links)
- Testing algebraic geometric codes (Q1047829) (← links)
- Zero knowledge and the chromatic number (Q1276168) (← links)
- Extracting randomness: A survey and new constructions (Q1305929) (← links)
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function (Q1375058) (← links)
- Spot-checkers (Q1577018) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- Annealed replication: A new heuristic for the maximum clique problem (Q1613385) (← links)
- Tight size-degree bounds for sums-of-squares proofs (Q1686838) (← links)
- On weighted vs unweighted versions of combinatorial optimization problems (Q1854428) (← links)
- Algebraic testing and weight distributions of codes. (Q1874387) (← links)
- Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
- On the approximability of clique and related maximization problems (Q1877696) (← links)
- Fast approximate probabilistically checkable proofs (Q1881217) (← links)
- Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials (Q1944393) (← links)
- 2-transitivity is insufficient for local testability (Q1947041) (← links)
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP (Q2043015) (← links)
- Spartan: efficient and general-purpose zkSNARKs without trusted setup (Q2104239) (← links)
- Succinct non-interactive arguments via linear interactive proofs (Q2136170) (← links)
- A PCP theorem for interactive proofs and applications (Q2170038) (← links)
- Succinct arguments in the quantum random oracle model (Q2175929) (← links)
- Linear-size constant-query IOPs for delegating computation (Q2175951) (← links)
- Combinatorial algorithms for distributed graph coloring (Q2251151) (← links)
- Hardness results for approximate pure Horn CNF formulae minimization (Q2254607) (← links)
- New tools and connections for exponential-time approximation (Q2272598) (← links)
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries (Q2379685) (← links)
- Quantum and non-signalling graph isomorphisms (Q2421559) (← links)
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization (Q2437764) (← links)
- On the severity of Braess's paradox: designing networks for selfish users is hard (Q2496322) (← links)
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes (Q2692970) (← links)
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms (Q2701071) (← links)
- Deciding the existence of perfect entangled strategies for nonlocal games (Q2808532) (← links)
- Three-Player Entangled XOR Games are NP-Hard to Approximate (Q2816299) (← links)
- Quantum XOR Games (Q2828211) (← links)
- Testing low-degree polynomials over prime fields (Q3055771) (← links)
- Approximation Algorithms for Minimum Chain Vertex Deletion (Q3078376) (← links)
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs (Q3088179) (← links)
