Verifying proofs in constant depth

DOI10.1145/2462896.2462898zbMATH Open1322.68081DBLPjournals/toct/BeyersdorffDKMSSTV13OpenAlexW2106155109WikidataQ59901839 ScholiaQ59901839MaRDI QIDQ2947574FDOQ2947574

Authors:

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/79314/8/JournalRevision.pdf

Recommendations

• Verifying proofs in constant depth
• DLOGTIME proof systems
• Logspace verifiers, NC, and NP

zbMATH Keywords

proof complexitycircuit complexityproof circuitssmall depth proofs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cited In (4)

• Verifying proofs in constant depth
• DLOGTIME proof systems
• Deep Proof Search in MELL
• A circuit complexity approach to transductions

This page was built for publication: Verifying proofs in constant depth

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