Pages that link to "Item:Q4388899"
From MaRDI portal
The following pages link to Free Bits, PCPs, and Nonapproximability---Towards Tight Results (Q4388899):
Displaying 46 items.
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete (Q2954372) (← links)
- Approximation and Hardness Results for the Max k-Uncut Problem (Q2958303) (← links)
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (Q2968149) (← links)
- Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors (Q2968154) (← links)
- Satisfying Degree-d Equations over GF[2] n (Q3088098) (← 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)
- On the Complexity of Computational Problems Regarding Distributions (Q3088193) (← links)
- Introduction to Testing Graph Properties (Q3088198) (← links)
- On Khot’s unique games conjecture (Q3109809) (← links)
- A query efficient non-adaptive long code test with perfect completeness (Q3192387) (← links)
- Graphs and Algorithms in Communication Networks on Seven League Boots (Q3404458) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- Asymptotics of the chromatic number for quasi-line graphs (Q3503489) (← links)
- Why Greed Works for Shortest Common Superstring Problem (Q3506957) (← links)
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2) (Q3541815) (← links)
- Probabilistic checking of proofs; a new characterization of NP (Q4230321) (← links)
- Proof verification and hardness of approximation problems (Q4230322) (← links)
- Cube vs. Cube Low Degree Test. (Q4638094) (← links)
- Simple analysis of graph tests for linearity and PCP (Q4800393) (← links)
- Coloration de graphes : fondements et applications (Q4809665) (← links)
- Limitation on the Rate of Families of Locally Testable Codes (Q4933361) (← links)
- Testing Juntas: A Brief Survey (Q4933362) (← links)
- Short Locally Testable Codes and Proofs: A Survey in Two Parts (Q4933364) (← links)
- Introduction to Testing Graph Properties (Q4933365) (← links)
- Invariance in Property Testing (Q4933370) (← links)
- Query-Efficient Dictatorship Testing with Perfect Completeness (Q4933378) (← links)
- Explicit strong LTCs with inverse poly-log rate and constant soundness (Q5009557) (← links)
- Imperfect gaps in Gap-ETH and PCPs (Q5091784) (← links)
- Reducing Testing Affine Spaces to Testing Linearity of Functions (Q5098778) (← links)
- (Q5111721) (← links)
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More (Q5115701) (← links)
- Distributed Graph Algorithms and their Complexity: An Introduction (Q5135263) (← links)
- An Improved Dictatorship Test with Perfect Completeness (Q5136305) (← links)
- Proximity Oblivious Testing and the Role of Invariances (Q5894226) (← links)
- Proximity Oblivious Testing and the Role of Invariances (Q5894230) (← links)
- On the advantage over a random assignment (Q5894908) (← links)
- Extracting all the randomness and reducing the error in Trevisan's extractors (Q5917498) (← links)
- Linear-consistency testing. (Q5946056) (← links)
- Max-3-Lin over non-abelian groups with universal factor graphs (Q6053470) (← links)
- Revisiting alphabet reduction in Dinur’s PCP. (Q6062158) (← links)
- Optimizing concurrency under Scheduling by Edge Reversal (Q6087133) (← links)
- Pseudorandom sets in Grassmann graph have near-perfect expansion (Q6101019) (← links)
- Max-Cut via Kuramoto-Type Oscillators (Q6168211) (← links)
- Mathematics of computation through the lens of linear equations and lattices (Q6198651) (← links)
