scientific article; zbMATH DE number 1405671

MaRDI QIDQ4938652zbMATHFDO

Authors Mario Szegedy

Publication date 22 June 2000

zbMATH Keywords

three-valued logicholographic proof checkingrandomized non-deterministic machine

Mathematics Subject Classification ID

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

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

(7)

• Short locally testable codes and proofs
• Fast approximate probabilistically checkable proofs
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Combinatorial PCPs with efficient verifiers
• Combinatorial PCPs with short proofs
• Short locally testable codes and proofs: a survey in two parts
• Low-degree test with polynomially small error

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)