A Randomized Algorithm for BBCSPs in the Prover-Verifier Model

DOI10.1007/978-3-540-75292-9_31MaRDI QIDQ3525105zbMATH OpenOpenAlexFDO

Authors K. Subramani

Publication date 17 September 2008

Published in Theoretical Aspects of Computing – ICTAC 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75292-9_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Randomized proof-labeling schemes
• Randomized proof-labeling schemes
• Proofs of Randomized Algorithms in Coq
• Proofs of randomized algorithms in Coq
• Probabilistically checkable proofs and their consequences for approximation algorithms
• On the concrete efficiency of probabilistically-checkable proofs
• Towards mechanized correctness proofs for cryptographic algorithms: axiomatization of a probabilistic Hoare style logic
• Constant-space, constant-randomness verifiers with arbitrarily small error
• Underapproximation for Model-Checking Based on Random Cryptographic Constructions
• Modular verification of protocol equivalence in the presence of randomness

Cited in

(2)

• On memoryless provers and insincere verifiers
• Verifiable Obtained Random Subsets for Improving SPHINCS+

This page was built for publication: A Randomized Algorithm for BBCSPs in the Prover-Verifier Model

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