Making IP=PSPACE practical: efficient interactive protocols for BDD algorithms

DOI10.1007/978-3-031-37709-9_21MaRDI QIDQ6535701zbMATH OpenFDO

Authors Eszter Couillard, Philipp Czerner, Javier Esparza, Rupak Majumdar

Publication date 1 February 2024

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-37709-9_21

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 66620
• IP = PSPACE
• Time-optimal interactive proofs for circuit evaluation
• scientific article; zbMATH DE number 5485522
• Finite state verifiers I

Cites work

• Algebraic methods for interactive proof systems
• Clausal abstraction for DQBF
• Clausal proofs for pseudo-Boolean reasoning
• Computational Complexity
• DepQBF 6.0: a search-based QBF solver beyond traditional QCDCL
• Dual proof generation for quantified Boolean formulas with a BDD-based solver
• Extended Resolution Proofs for Conjoining BDDs
• Extended Resolution Proofs for Symbolic SAT Solving with Quantification
• Flexible proof production in an industrial-strength SMT solver
• Generating extended resolution proofs with a BDD-based SAT solver
• Graph-Based Algorithms for Boolean Function Manipulation
• Handbook of satisfiability. In 2 parts
• scientific article; zbMATH DE number 1798181 (Why is no real title available?)
• scientific article; zbMATH DE number 1903378 (Why is no real title available?)
• scientific article; zbMATH DE number 4185024 (Why is no real title available?)
• IP = PSPACE
• QBF Resolution Systems and Their Proof Complexities
• The knowledge complexity of interactive proof-systems

Cited in

(2)

• A resolution-based interactive proof system for UNSAT
• A resolution-based interactive proof system for UNSAT

This page was built for publication: Making \(\mathsf{IP}=\mathsf{PSPACE}\) practical: efficient interactive protocols for BDD algorithms

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