Verifying and decoding in constant depth

MaRDI QIDQ3549643zbMATH OpenFDO

Authors Dan Gutfreund, Alexander D. Healy, Tali Kaufman, Guy N. Rothblum, Shafi Goldwasser

Publication date 5 January 2009

zbMATH Keywords

error correcting codesinteractive proof systemscomputationally bounded receiverpotentially malicious sendersender-receiver setting

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Specification and verification (program logics, model checking, etc.) (68Q60) Decoding (94B35)

Recommendations

• Constant-round interactive proofs for delegating computation
• Constant-round interactive proofs for delegating computation
• scientific article; zbMATH DE number 5485522
• Delegating computation: interactive proofs for muggles
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

Cited in

(14)

• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Fine-grained secure computation
• Theory of Cryptography
• Homomorphic evaluation of lattice-based symmetric encryption schemes
• Instance-hiding interactive proofs
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
• Majority vs. approximate linear sum and average-case complexity below NC^1
• scientific article; zbMATH DE number 7440191 (Why is no real title available?)
• A technique for hardness amplification against AC^0
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Randomness extractors in AC^0 and NC^1: optimal up to constant factors
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

This page was built for publication: Verifying and decoding in constant depth

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