scientific article; zbMATH DE number 2212170

MaRDI QIDQ5694913zbMATH OpenFDO

Authors Johan Hastad

Publication date 5 October 2005

zbMATH Keywords

complexity theoryinapproximabilityprobabilistically checkable proofs

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4053608
• scientific article; zbMATH DE number 4114622
• Approximability and proof complexity
• Complexity theory and theory of algorithms
• scientific article; zbMATH DE number 2090609
• Complexity of approximation problems
• Computability and complexity theory
• scientific article; zbMATH DE number 486435
• scientific article; zbMATH DE number 1069617
• scientific article; zbMATH DE number 1418967

Cited in

(12)

• Probabilistically checkable proofs and their consequences for approximation algorithms
• Interactive and probabilistic proof-checking
• Probabilistic verification of proofs in calculuses
• Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
• On Dinur’s proof of the PCP theorem
• Hard-core theorems for complexity classes
• scientific article; zbMATH DE number 58312 (Why is no real title available?)
• scientific article; zbMATH DE number 512858 (Why is no real title available?)
• scientific article; zbMATH DE number 727431 (Why is no real title available?)
• Computationally Sound Proofs
• scientific article; zbMATH DE number 2161249 (Why is no real title available?)
• Complexity Approximation Principle

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 Q5694913)