scientific article; zbMATH DE number 1405671

MaRDI QIDQ4938652zbMATH OpenFDO

Authors Mario Szegedy

Publication date 22 June 2000

zbMATH Keywords

holographic proof checkingrandomized non-deterministic machinethree-valued logic

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Many-valued logic (03B50) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 512858
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Nearly-linear size holographic proofs
• scientific article; zbMATH DE number 4049622
• scientific article; zbMATH DE number 1754535

Cited in

(8)

• Fast approximate probabilistically checkable proofs
• Low-degree test with polynomially small error
• Combinatorial PCPs with short proofs
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Short locally testable codes and proofs
• scientific article; zbMATH DE number 512858 (Why is no real title available?)
• Combinatorial PCPs with efficient verifiers
• Short locally testable codes and proofs: a survey in two parts

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938652)