article

Lower bounds to the size of constant-depth propositional proofs

Author:

Jan KrajíčekAuthors Info & Claims

Journal of Symbolic Logic, Volume 59, Issue 1

Pages 73 - 86

https://doi.org/10.2307/2275250

Published: 01 March 1994 Publication History

Abstract

No abstract available.

Cited By

View all

Miyamoto KMoser G(2024)Herbrand complexity and the epsilon calculus with equalityArchive for Mathematical Logic10.1007/s00153-023-00877-363:1-2(89-118)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00153-023-00877-3
Folwarczný L(2023)On Protocols for Monotone Feasible InterpolationACM Transactions on Computation Theory10.1145/358375415:1-2(1-17)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3583754
Bonacina IBonet M(2022)On the strength of Sherali-Adams and Nullstellensatz as propositional proof systemsProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533344(1-12)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533344
Show More Cited By

Index Terms

Lower bounds to the size of constant-depth propositional proofs

Recommendations

Quasipolynomial size proofs of the propositional pigeonhole principle

Cook and Reckhow proved in 1979 that the propositional pigeonhole principle has polynomial size extended Frege proofs. Buss proved in 1987 that it also has polynomial size Frege proofs; these Frege proofs used a completely different proof method based ...
Verifying proofs in constant depth

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC⁰ circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages ...
Lower bounds for uniform constant depth circuits

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Symbolic Logic Volume 59, Issue 1

March 1994

343 pages

ISSN:0022-4812

Editors:
Peter Aczel
Manchester Univ., Manchester, UK
,
Wilfried Buchholz
Univ. Mu¨nchen, Munich, Germany
,
Sy D. Friedman
Massachusetts Institute of Technology, Cambridge
,
Julia Knight
Univ. of Notre Dame, Notre Dame, IN
,
Steffen Lempp
Univ. of Wisconsin, Madison
,
Andre Scedrov
Univ. of Pennsylvania, Philadelphia
,
Johan van Benthem
Univ. van Amsterdam, Amsterdam, The Netherlands
,
John P. Burgess
Priceton Univ., Princeton, NJ
,
George Boolos,
Gerhard Jäger,
Michael Makkai

Issue’s Table of Contents

Publisher

Association for Symbolic Logic, Inc.

United States

Publication History

Published: 01 March 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Miyamoto KMoser G(2024)Herbrand complexity and the epsilon calculus with equalityArchive for Mathematical Logic10.1007/s00153-023-00877-363:1-2(89-118)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00153-023-00877-3
Folwarczný L(2023)On Protocols for Monotone Feasible InterpolationACM Transactions on Computation Theory10.1145/358375415:1-2(1-17)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1145/3583754
Bonacina IBonet M(2022)On the strength of Sherali-Adams and Nullstellensatz as propositional proof systemsProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533344(1-12)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533344
Part FThapen NTzameret IGorla D(2021)First-order reasoning and efficient semi-algebraic proofsProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470546(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470546
Atserias AMüller M(2020)Automating Resolution is NP-HardJournal of the ACM10.1145/340947267:5(1-17)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1145/3409472
Garlík MKołodziejczyk L(2018)Some Subsystems of Constant-Depth Frege with ParityACM Transactions on Computational Logic10.1145/324312619:4(1-34)Online publication date: 20-Nov-2018
https://dl.acm.org/doi/10.1145/3243126
Grochow JPitassi T(2018)Circuit Complexity, Proof Complexity, and Polynomial Identity TestingJournal of the ACM10.1145/323074265:6(1-59)Online publication date: 26-Nov-2018
https://dl.acm.org/doi/10.1145/3230742
Lauria MPudlák PRödl VThapen N(2017)The complexity of proving that a graph is RamseyCombinatorica10.1007/s00493-015-3193-937:2(253-268)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00493-015-3193-9
Carlucci LGalesi NLauria M(2016)On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey TautologiesACM Transactions on Computational Logic10.1145/294680117:4(1-25)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1145/2946801
Filmus YPitassi TSanthanam R(2015)Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower BoundsACM Transactions on Computation Theory10.1145/26562097:2(1-16)Online publication date: 11-May-2015
https://dl.acm.org/doi/10.1145/2656209
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Quasipolynomial size proofs of the propositional pigeonhole principle

Verifying proofs in constant depth

Lower bounds for uniform constant depth circuits

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations