The following pages link to Probabilistic checking of proofs (Q3841041):
Displaying 50 items.
- Combinatorial PCPs with short proofs (Q260390) (← links)
- Bounds on 2-query locally testable codes with affine tests (Q280942) (← links)
- Sparse approximation is provably hard under coherent dictionaries (Q340554) (← links)
- Refereed delegation of computation (Q385709) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- Combinatorial PCPs with efficient verifiers (Q483706) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- Unrelated parallel machine scheduling -- perspectives and progress (Q505093) (← links)
- Improved approximation algorithms for projection games (Q513283) (← links)
- Best-order streaming model (Q534570) (← links)
- Testing juntas (Q598252) (← links)
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR (Q603915) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- On the hardness of learning intersections of two halfspaces (Q619909) (← links)
- Derandomized parallel repetition via structured PCPs (Q645129) (← links)
- PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
- Towards lower bounds on locally testable codes via density arguments (Q693000) (← links)
- Characterizations of locally testable linear- and affine-invariant families (Q764306) (← links)
- Quantum information and the PCP theorem (Q835644) (← links)
- Hard constraint satisfaction problems have hard gaps at location 1 (Q837178) (← links)
- Committee polyhedral separability: complexity and polynomial approximation (Q890319) (← links)
- Finding large 3-free sets. I. The small \(n\) case (Q927879) (← links)
- Deterministically testing sparse polynomial identities of unbounded degree (Q976069) (← links)
- Cryptography with constant input locality (Q1037233) (← links)
- APX-hardness of domination problems in circle graphs (Q1045943) (← links)
- Testing algebraic geometric codes (Q1047829) (← links)
- Approximating maximum independent sets by excluding subgraphs (Q1196452) (← links)
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems (Q1305935) (← links)
- Probabilistically checkable proofs and their consequences for approximation algorithms (Q1344618) (← links)
- Quantum multi-prover interactive proof systems with limited prior entanglement. (Q1401955) (← links)
- Spot-checkers (Q1577018) (← links)
- Interactive and probabilistic proof-checking (Q1577488) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- The hunting of the SNARK (Q1698394) (← links)
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems (Q1730018) (← links)
- PSPACE has constant-round quantum interactive proof systems (Q1870552) (← 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)
- Efficient checking of polynomials and proofs and the hardness of approximation problems (Q1906841) (← links)
- Exponential inapproximability of selecting a maximum volume sub-matrix (Q1939669) (← links)
- 2-transitivity is insufficient for local testability (Q1947041) (← links)
- Max NP-completeness made easy (Q1960655) (← links)
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) (Q2018136) (← links)
- The Chinese deliveryman problem (Q2025136) (← links)
- Smooth and strong PCPs (Q2029773) (← links)
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension (Q2046271) (← links)
- Spartan: efficient and general-purpose zkSNARKs without trusted setup (Q2104239) (← links)
- A PCP of proximity for real algebraic polynomials (Q2117096) (← links)
