Pages that link to "Item:Q4371671"
From MaRDI portal
The following pages link to Interactive proofs and the hardness of approximating cliques (Q4371671):
Displaying 43 items.
- 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)
- Short Locally Testable Codes and Proofs (Q3088191) (← links)
- Bravely, Moderately: A Common Theme in Four Recent Works (Q3088192) (← links)
- Randomness and Computation (Q3088199) (← links)
- Combinatorial Algorithms for Distributed Graph Coloring (Q3095316) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- Interactive Proofs with Approximately Commuting Provers (Q3448798) (← links)
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2) (Q3541815) (← links)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP (Q3608306) (← links)
- Probabilistic checking of proofs (Q3841041) (← links)
- Testing properties of directed graphs: acyclicity and connectivity* (Q4543627) (← links)
- Extension Complexity of Independent Set Polytopes (Q4606697) (← links)
- (Q4638096) (← links)
- Simple analysis of graph tests for linearity and PCP (Q4800393) (← links)
- Short Locally Testable Codes and Proofs: A Survey in Two Parts (Q4933364) (← links)
- Optimal Testing of Reed-Muller Codes (Q4933377) (← links)
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs (Q4933379) (← links)
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (Q5002681) (← links)
- Explicit strong LTCs with inverse poly-log rate and constant soundness (Q5009557) (← links)
- Some recent strong inapproximability results (Q5054856) (← links)
- (Q5090398) (← links)
- UG-hardness to NP-hardness by losing half (Q5091753) (← links)
- (Q5093398) (← links)
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More (Q5115701) (← links)
- (Q5121905) (← links)
- (Q5121908) (← links)
- (Q5121910) (← links)
- Parallel Repetition of Two-Prover One-Round Games: An Exposition (Q5135260) (← links)
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − <i>ɛ</i> (Q5219712) (← links)
- The Complexity of Zero Knowledge (Q5458822) (← links)
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem (Q5892608) (← links)
- Parameterized inapproximability of independent set in \(H\)-free graphs (Q5925689) (← links)
- A generalization of maximal independent sets (Q5931790) (← links)
- Max-3-Lin over non-abelian groups with universal factor graphs (Q6053470) (← links)
- Pseudorandom sets in Grassmann graph have near-perfect expansion (Q6101019) (← links)
- Mathematics of computation through the lens of linear equations and lattices (Q6198651) (← links)
- Greedy maximal independent sets via local limits (Q6541390) (← links)
- Cryptography from planted graphs: security with logarithmic-size messages (Q6581792) (← links)
- Synchronous values of games (Q6617161) (← links)
- Verifiable isogeny walks: towards an isogeny-based postquantum VDF (Q6618603) (← links)
- Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance (Q6637522) (← links)
- STIR: Reed-Solomon proximity testing with fewer queries (Q6660306) (← links)
