scientific article; zbMATH DE number 4205986

MaRDI QIDQ3355236zbMATH OpenFDO

Authors Richard J. Lipton

Publication date 1990

zbMATH Keywords

polynomial-time verifier

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Probabilistic verification of proofs
• Logspace verifiers, NC, and NP
• Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
• scientific article; zbMATH DE number 1670844
• Computationally Sound Proofs

Cited in

(20)

• Batch checking with applications to linear functions
• On games of incomplete information
• Local correctability of expander codes
• Locally decodable codes: a brief survey
• The complexity of debate checking
• Lower bounds for 2-query LCCs over large alphabet
• Local list recovery of high-rate tensor codes and applications
• Best-order streaming model
• High-rate codes with sublinear-time decoding
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• Erasures versus errors in local decoding and property testing
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Succinct arguments for RAM programs via projection codes
• On matrix rigidity and locally self-correctable codes
• Logspace verifiers, NC, and NP
• Fiat-Shamir security of FRI and related SNARKs
• Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
• Linear relaxed locally decodable and correctable codes do not need adaptivity and two-sided error
• Ensuring the quasi-termination of needed narrowing computations
• Checking the correctness of memories

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