Bounded-Depth Frege is a propositional proof system in proof complexity where proofs are restricted to formulas of bounded logical depth, distinguishing it from unrestricted Frege systems by limiting the nesting depth of logical connectives in the formulas used during derivations.
23
Publications
975
Citations
28
Authors
25
Institutions
Publications per year
2017–2026
2
Variants
Bounded-depth Frege System
Parents
Publications
23
Non-Automatizability of Bounded-Depth Frege Proofs
Marı́a Luisa Bonet, Carlos Domingo, Ricard Gavald� et al. · Computational Complexity · 2004 · 71 citations
Lower bounds for cutting planes proofs with small coefficients
Toniann Pitassi, Ran Raz · 1995 · 58 citations · Full text
1–5 of 23
Authors
28
- TP
8
h-index
- EB
3
h-index
- AU
2
h-index
- RI
2
h-index
- RR
2
h-index
1–5 of 28
Institutions
25
University of California San Diego
San Diego, United States
4 h-index
6 publications
379 citations
University of Toronto
Toronto, Canada
3 h-index
3 publications
107 citations
Universitat Politècnica de Catalunya
Barcelona, Spain
3 h-index
8 publications
298 citations
Tokyo Institute of Technology
Tokyo, Japan
2 h-index
2 publications
88 citations
University of Washington
Seattle, United States
2 h-index
3 publications
116 citations
University of Arizona
Tucson, United States
2 h-index
2 publications
165 citations
Weizmann Institute of Science
Rehovot, Israel
2 h-index
2 publications
206 citations
KTH Royal Institute of Technology
Stockholm, Sweden
2 h-index
2 publications
47 citations
1–8 of 25
Venues
- Computational Complexity
CC · 3 publications · 236 citations
3
h-index
- Random Structures and Algorithms
1 publications · 12 citations
1
h-index
- Theoretical Computer Science
1 publications · 13 citations
1
h-index
- The Philosophical Quarterly
1 publications · 21 citations
1
h-index
- Logical Methods in Computer Science
LMCS · 1 publications · 28 citations
1
h-index
1–5