×
Author ID: buss.samuel-r Recent zbMATH articles by "Buss, Samuel R."
Published as: Buss, Samuel R.; Buss, Sam; Buss, Samuel; Buss, S.; Buss, S. R.
Homepage: https://mathweb.ucsd.edu/~sbuss/
External Links: MGP · ORCID · dblp
all top 5

Co-Authors

44 single-authored
13 Beckmann, Arnold
12 Bonet, Maria Luisa
7 Pitassi, Toniann
6 Kohlenbach, Ulrich Wilhelm
6 Thapen, Neil
5 Friedman, Sy-David
5 Impagliazzo, Russell
5 Müller, Moritz
5 Rathjen, Michael
4 Aisenberg, James
4 Knop, Alexander
4 Pudlák, Pavel
3 Iemhoff, Rosalie
3 Johannsen, Jan
3 Kołodziejczyk, Leszek Aleksander
3 Krajíček, Jan
3 Löwe, Benedikt
2 Alekhnovich, Michael
2 Cenzer, Douglas
2 Clote, Peter G.
2 Crǎciun, Adrian
2 Grigor’ev, Dmitriĭ Yur’evich
2 Hoffmann, Jan-Philipp
2 Ignatyev, Alexey A.
2 Istrate, Gabriel I.
2 Itsykson, Dmitry M.
2 Johnson, Alan S.
2 Kabanets, Valentine
2 Kolokolova, Antonina
2 Koucký, Michal
2 Kuznets, Roman
2 Marques-Silva, João P.
2 Minnes, Mia
2 Moran, Shlomo
2 Morgado, António
2 Remmel, Jeffrey Brian
2 Schwichtenberg, Helmut
2 Sokolev, Dmitry
2 Turán, Gyorgy
2 Yianilos, Peter N.
1 Ambos-Spies, Klaus
1 Atserias, Albert
1 Beame, Paul W.
1 Brydges, David C.
1 Carlen, Eric Anders
1 Chen, Yijia
1 Cook, Stephen Arthur
1 Cooper, Stuart Barry
1 Das, Anupam
1 Faris, William G.
1 Fleming, Noah
1 Flum, Jörg
1 Gross, Leonhard
1 Gupta, Arvind
1 Hájek, Petr
1 Hay, Louise
1 Hook, Julian L.
1 Ignjatović, Aleksandar
1 Kapron, Bruce M.
1 Kechris, Alexander S.
1 Keĭlis-Borok, Vladimir Isaakovich
1 Lawler, Gregory Francis
1 Mints, Grigoriĭ Efroimovich
1 Nelson, Joseph Edward
1 Normann, Dag
1 Papadimitriou, Christos Harilaos
1 Pillay, Anand
1 Pollett, Chris
1 Ramachandran, Vijaya
1 Ramyaa, Ramyaa
1 Razborov, Aleksandr Aleksandrovich
1 Riazanov, Artur
1 Roşu, Grigore
1 Scott, Philip J.
1 Segerlind, Nathan
1 Sgall, Jiří
1 Shore, Richard Arnold
1 Simon, Barry
1 Soltys, Michael
1 Sorbi, Andrea
1 Soskov, Ivan Nikolaev
1 Takeuti, Gaisi
1 Tsitsiklis, John N.
1 Villani, Cédric
1 Williams, Richard Ryan
1 Yolcu, Emre
1 Zdanowski, Konrad

Publications by Year

Citations contained in zbMATH Open

110 Publications have been cited 1,357 times in 871 Documents Cited by Year
Bounded arithmetic. Zbl 0649.03042
Buss, Samuel R.
154
1986
Handbook of proof theory. Zbl 0898.03001
72
1998
An introduction to proof theory. Zbl 0912.03024
Buss, Samuel R.
65
1998
Polynomial size proofs of the propositional pigeonhole principle. Zbl 0636.03053
Buss, Samuel R.
59
1987
The polynomial hierarchy and intuitionistic bounded arithmetic. Zbl 0654.03043
Buss, S. R.
58
1986
On truth-table reducibility to SAT. Zbl 0800.68443
Buss, Samuel R.; Hay, Louise
36
1991
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1007.03052
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
33
2001
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
32
1997
First-order proof theory of arithmetic. Zbl 0911.03029
Buss, Samuel R.
32
1998
An optimal parallel algorithm for formula evaluation. Zbl 0825.68424
Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.
29
1992
A switching lemma for small restrictions and lower bounds for \(k\)-DNF resolution. Zbl 1059.03063
Segerlind, Nathan; Buss, Sam; Impagliazzo, Russell
29
2004
The undecidability of \(k\)-provability. Zbl 0749.03039
Buss, Samuel R.
25
1991
An application of Boolean complexity to separation problems in bounded arithmetic. Zbl 0799.03066
Buss, Samuel R.; Krajíček, Jan
25
1994
Propositional proofs and reductions between NP search problems. Zbl 1252.03127
Buss, Samuel R.; Johnson, Alan S.
25
2012
Resolution proofs of generalized pigeonhole principles. Zbl 0709.03006
Buss, Samuel R.; Turán, György
24
1988
Towards NP-P via proof complexity and search. Zbl 1257.03086
Buss, Samuel R.
23
2012
Diffusion, quantum theory, and radically elementary mathematics. Zbl 1104.81003
22
2006
Unshuffling a square is NP-hard. Zbl 1285.68130
Buss, Sam; Soltys, Michael
21
2014
Relating the bounded arithmetic and polynomial time hierarchies. Zbl 0829.03035
Buss, Samuel R.
19
1995
Are there hard examples for Frege systems? Zbl 0834.03021
Bonet, Maria Luisa; Buss, Samuel R.; Pitassi, Toniann
19
1995
Resolution and the weak pigeonhole principle. Zbl 0910.03036
Buss, Sam; Pitassi, Toniann
19
1998
Size-depth tradeoffs for Boolean formulae. Zbl 0802.68067
Bonet, Maria Luisa; Buss, Samuel R.
18
1994
Alogtime algorithms for tree isomorphism, comparison, and canonization. Zbl 0884.68098
Buss, Samuel R.
17
1997
Resolution trees with lemmas: resolution refinements that characterize DLL algorithms with clause learning. Zbl 1159.03009
Buss, Samuel R.; Hoffmann, Jan; Johannsen, Jan
17
2008
Minimum propositional proof length is NP-hard to linearly approximate. Zbl 0977.03032
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
16
2001
Axiomatizations and conservation results for fragments of bounded arithmetic. Zbl 0699.03032
Buss, Samuel R.
15
1990
On Herbrand’s theorem. Zbl 1540.03102
Buss, Samuel R.
15
1995
Algorithms for Boolean formula evaluation and for tree contraction. Zbl 0792.68046
Buss, Samuel R.
14
1993
Fragments of approximate counting. Zbl 1338.03107
Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Thapen, Neil
14
2014
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs. Zbl 1353.03071
Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Zdanowski, Konrad
14
2015
Propositional consistency proofs. Zbl 0749.03040
Buss, Samuel R.
13
1991
Improved witnessing and local improvement principles for second-order bounded arithmetic. Zbl 1287.03105
Beckmann, Arnold; Buss, Samuel R.
13
2014
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
13
2020
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic. Zbl 1204.03056
Beckmann, Arnold; Buss, Samuel R.
12
2009
Propositional proof complexity: an introduction. Zbl 0946.68128
Buss, Samuel R.
12
1999
Minimum propositional proof length is NP-hard to linearly approximate (extended abstract). Zbl 0911.03028
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
12
1998
On Gödel’s theorems on lengths of proofs. I: Number of lines and speedup for arithmetics. Zbl 0805.03047
Buss, Samuel R.
11
1994
Cutting planes, connectivity, and threshold logic. Zbl 0841.03029
Buss, Samuel R.; Clote, Peter
10
1996
The deduction rule and linear and near-linear proof simulations. Zbl 0848.03028
Bonet, Maria Luisa; Buss, Samuel R.
10
1993
Intuitionistic validity in \(T\)-normal Kripke structures. Zbl 0802.03006
Buss, Samuel R.
10
1993
Bounded arithmetic and propositional proof complexity. Zbl 0882.68130
Buss, Samuel R.
10
1997
Lower bounds on Nullstellensatz proofs via designs. Zbl 0890.03029
Buss, Samuel R.
10
1998
Unprovability of consistency statements in fragments of bounded arithmetic. Zbl 0834.03022
Buss, Samuel R.; Ignjatović, Aleksandar
10
1995
The complexity of the disjunction and existential properties in intuitionistic logic. Zbl 0939.03064
Buss, Sam; Mints, Grigori
10
1999
How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542
Pudlák, Pavel; Buss, Samuel R.
10
1995
The witness function method and provably recursive functions of Peano arithmetic. Zbl 0829.03036
Buss, Samuel R.
9
1994
A conservation result concerning bounded theories and the collection axiom. Zbl 0626.03048
Buss, Samuel R.
8
1987
Characterising definable search problems in bounded arithmetic via proof notations. Zbl 1244.03163
Beckmann, Arnold; Buss, Samuel R.
8
2010
Accurate and efficient simulation of rigid-body rotations. Zbl 1035.70500
Buss, Samuel R.
8
2000
On the computational content of intuitionistic propositional proofs. Zbl 1009.03027
Buss, Samuel R.; Pudlák, Pavel
8
2001
Good degree bounds on Nullstellensatz refutations of the induction principle. Zbl 0921.68088
Buss, Samuel R.; Pitassi, Toniann
8
1998
Separation results for the size of constant-depth propositional proofs. Zbl 1089.03048
Beckmann, Arnold; Buss, Samuel R.
7
2005
Provably total function in bounded arithmetic theories \(R_ 3^ i\), \(U_ 2^ i\) and \(V_ 2^ i\). Zbl 0799.03065
Buss, Samuel R.; Krajíček, Jan; Takeuti, Gaisi
7
1993
Some remarks on lengths of propositional proofs. Zbl 0841.03030
Buss, Samuel R.
7
1995
Cut elimination in situ. Zbl 1380.03062
Buss, Sam
7
2015
On model theory for intuitionistic bounded arithmetic with applications to independence results. Zbl 0764.03021
Buss, Samuel R.
6
1990
On the predictability of coupled automata: An allegory about chaos. Zbl 0760.68031
Buss, Samuel R.; Papadimitriou, Christos H.; Tsitsiklis, John N.
6
1991
Improved separations of regular resolution from clause learning proof systems. Zbl 1361.68185
Bonet, Maria Luisa; Buss, Sam; Johannsen, Jan
6
2014
Incompleteness of behavioral logics. Zbl 0959.03506
Buss, Samuel; Roşu, Grigore
6
2000
DRAT proofs, propagation redundancy, and extended resolution. Zbl 1441.03043
Buss, Sam; Thapen, Neil
6
2019
Strong isomorphism reductions in complexity theory. Zbl 1248.03060
Buss, Sam; Chen, Yijia; Flum, Jörg; Friedman, Sy-David; Müller, Moritz
6
2011
A note on bootstrapping intuitionistic bounded arithmetic. Zbl 0792.03039
Buss, Samuel R.
5
1992
Safe recursive set functions. Zbl 1357.03075
Beckmann, Arnold; Buss, Samuel R.; Friedman, Sy-David
5
2015
An improved separation of regular resolution from pool resolution and clause learning. Zbl 1273.03048
Bonet, Maria Luisa; Buss, Sam
5
2012
Small Stone in pool. Zbl 1336.03019
Buss, Samuel R.; Kolodziejczyk, Leszek Alek
5
2014
Quasipolynomial size proofs of the propositional pigeonhole principle. Zbl 1347.03100
Buss, Sam
5
2015
The prospects for mathematical logic in the twenty-first century. Zbl 0981.03003
Buss, Samuel R.; Kechris, Alexander S.; Pillay, Anand; Shore, Richard A.
5
2001
Linear and time minimum-cost matching algorithms for quasi-convex tours. Zbl 0913.05086
Buss, Samuel R.; Yianilos, Peter N.
5
1998
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1345.03105
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
5
1999
Reordering rule makes OBDD proof systems stronger. Zbl 1441.03042
Buss, Sam; Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry
5
2018
Corrected upper bounds for free-cut elimination. Zbl 1267.03053
Beckmann, Arnold; Buss, Samuel R.
5
2011
The modal logic of pure provability. Zbl 0713.03009
Buss, Samuel R.
4
1990
Linear and \(O(n \text{log} n)\) time minimum-cost matching algorithms for quasi-convex tours. Zbl 0867.05071
Buss, Samuel R.; Yianilos, Peter N.
4
1994
Quasipolynomial size Frege proofs of Frankl’s theorem on the trace of sets. Zbl 1436.03298
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
4
2016
DRMaxSAT with MaxHS: first contact. Zbl 1441.68232
Morgado, Antonio; Ignatiev, Alexey; Bonet, Maria Luisa; Marques-Silva, Joao; Buss, Sam
4
2019
The graph of multiplication is equivalent to counting. Zbl 0748.68018
Buss, Samuel R.
3
1992
The NP search problems of Frege and extended Frege proofs. Zbl 1407.03071
Beckmann, Arnold; Buss, Sam
3
2017
Short proofs of the Kneser-Lovász coloring principle. Zbl 1443.03040
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam; Crăciun, Adrian; Istrate, Gabriel
3
2018
Injection structures specified by finite state transducers. Zbl 1485.03108
Buss, Sam; Cenzer, Douglas; Minnes, Mia; Remmel, Jeffrey B.
3
2017
Cobham recursive set functions. Zbl 1383.03050
Beckmann, Arnold; Buss, Sam; Friedman, Sy-David; Müller, Moritz; Thapen, Neil
3
2016
Resource-bounded continuity and sequentiality for type-two functionals. Zbl 1365.03029
Buss, Samuel R.; Kapron, Bruce M.
3
2002
Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies. Zbl 1094.03044
Buss, Samuel R.
3
2006
The NP-completeness of reflected fragments of justification logics. Zbl 1211.03035
Buss, Samuel R.; Kuznets, Roman
3
2009
Bounded arithmetic, proof complexity and two papers of Parikh. Zbl 0924.03106
Buss, Samuel R.
3
1999
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080
Buss, Samuel R.; Williams, Ryan
3
2015
Strategies for stable merge sorting. Zbl 1431.68021
Buss, Sam; Knop, Alexander
3
2019
Ordinal notations and well-orderings in bounded arithmetic. Zbl 1015.03055
Beckmann, Arnold; Pollett, Chris; Buss, Samuel R.
3
2003
The NP-hardness of finding a directed acyclic graph for regular resolution. Zbl 1145.03034
Buss, Samuel R.; Hoffmann, Jan
2
2008
The serial transitive closure problem for trees. Zbl 0828.68099
Bonet, Maria Luisa; Buss, Samuel R.
2
1995
Bounded arithmetic and constant depth Frege proofs. Zbl 1079.03050
Buss, Samuel R.
2
2004
On Gödel’s theorems on lengths of proofs. II: Lower bounds for recognizing \(k\) symbol provability. Zbl 0829.03034
Buss, Samuel R.
2
1995
Proof complexity of systems of (non-deterministic) decision trees and branching programs. Zbl 07650825
Buss, Sam; Das, Anupam; Knop, Alexander
2
2020
On linear resolution. Zbl 1484.03120
Buss, Sam; Johannsen, Jan
2
2017
Sub-computable boundedness randomness. Zbl 1325.03050
Buss, Sam; Cenzer, Douglas; Remmel, Jeffrey B.
2
2014
Lower complexity bounds in justification logic. Zbl 1243.03026
Buss, Samuel R.; Kuznets, Roman
2
2012
Expander construction in \(\mathsf{VNC}^1\). Zbl 1402.03081
Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal
2
2017
Short proofs of the Kneser-Lovász coloring principle. Zbl 1443.03041
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam; Crãciun, Adrian; Istrate, Gabriel
2
2015
3-D computer graphics. A mathematical introduction with OpenGL. Zbl 1044.65017
Buss, Samuel R.
2
2003
DRAT and propagation redundancy proofs without new variables. Zbl 1535.03275
Buss, Sam; Thapen, Neil
2
2021
Expander construction in \(\mathrm{VNC}^1\). Zbl 1481.03065
Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal
2
2020
On the consistency of circuit lower bounds for non-deterministic time. Zbl 07844669
Atserias, Albert; Buss, Sam; Müller, Moritz
2
2023
DRAT and propagation redundancy proofs without new variables. Zbl 1535.03275
Buss, Sam; Thapen, Neil
2
2021
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
13
2020
Proof complexity of systems of (non-deterministic) decision trees and branching programs. Zbl 07650825
Buss, Sam; Das, Anupam; Knop, Alexander
2
2020
Expander construction in \(\mathrm{VNC}^1\). Zbl 1481.03065
Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal
2
2020
DRAT proofs, propagation redundancy, and extended resolution. Zbl 1441.03043
Buss, Sam; Thapen, Neil
6
2019
DRMaxSAT with MaxHS: first contact. Zbl 1441.68232
Morgado, Antonio; Ignatiev, Alexey; Bonet, Maria Luisa; Marques-Silva, Joao; Buss, Sam
4
2019
Strategies for stable merge sorting. Zbl 1431.68021
Buss, Sam; Knop, Alexander
3
2019
Reordering rule makes OBDD proof systems stronger. Zbl 1441.03042
Buss, Sam; Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry
5
2018
Short proofs of the Kneser-Lovász coloring principle. Zbl 1443.03040
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam; Crăciun, Adrian; Istrate, Gabriel
3
2018
Cobham recursive set functions and weak set theories. Zbl 1448.03029
Beckmann, Arnold; Buss, Sam; Friedman, Sy-David; Müller, Moritz; Thapen, Neil
1
2018
The NP search problems of Frege and extended Frege proofs. Zbl 1407.03071
Beckmann, Arnold; Buss, Sam
3
2017
Injection structures specified by finite state transducers. Zbl 1485.03108
Buss, Sam; Cenzer, Douglas; Minnes, Mia; Remmel, Jeffrey B.
3
2017
On linear resolution. Zbl 1484.03120
Buss, Sam; Johannsen, Jan
2
2017
Expander construction in \(\mathsf{VNC}^1\). Zbl 1402.03081
Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal
2
2017
Uniform proofs of ACC representations. Zbl 1406.03053
Buss, Sam
1
2017
Quasipolynomial size Frege proofs of Frankl’s theorem on the trace of sets. Zbl 1436.03298
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
4
2016
Cobham recursive set functions. Zbl 1383.03050
Beckmann, Arnold; Buss, Sam; Friedman, Sy-David; Müller, Moritz; Thapen, Neil
3
2016
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs. Zbl 1353.03071
Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Zdanowski, Konrad
14
2015
Cut elimination in situ. Zbl 1380.03062
Buss, Sam
7
2015
Safe recursive set functions. Zbl 1357.03075
Beckmann, Arnold; Buss, Samuel R.; Friedman, Sy-David
5
2015
Quasipolynomial size proofs of the propositional pigeonhole principle. Zbl 1347.03100
Buss, Sam
5
2015
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080
Buss, Samuel R.; Williams, Ryan
3
2015
Short proofs of the Kneser-Lovász coloring principle. Zbl 1443.03041
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam; Crãciun, Adrian; Istrate, Gabriel
2
2015
Unshuffling a square is NP-hard. Zbl 1285.68130
Buss, Sam; Soltys, Michael
21
2014
Fragments of approximate counting. Zbl 1338.03107
Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Thapen, Neil
14
2014
Improved witnessing and local improvement principles for second-order bounded arithmetic. Zbl 1287.03105
Beckmann, Arnold; Buss, Samuel R.
13
2014
Improved separations of regular resolution from clause learning proof systems. Zbl 1361.68185
Bonet, Maria Luisa; Buss, Sam; Johannsen, Jan
6
2014
Small Stone in pool. Zbl 1336.03019
Buss, Samuel R.; Kolodziejczyk, Leszek Alek
5
2014
Sub-computable boundedness randomness. Zbl 1325.03050
Buss, Sam; Cenzer, Douglas; Remmel, Jeffrey B.
2
2014
Probabilistic algorithmic randomness. Zbl 1305.03037
Buss, Sam; Minnes, Mia
1
2013
Propositional proofs and reductions between NP search problems. Zbl 1252.03127
Buss, Samuel R.; Johnson, Alan S.
25
2012
Towards NP-P via proof complexity and search. Zbl 1257.03086
Buss, Samuel R.
23
2012
An improved separation of regular resolution from pool resolution and clause learning. Zbl 1273.03048
Bonet, Maria Luisa; Buss, Sam
5
2012
Lower complexity bounds in justification logic. Zbl 1243.03026
Buss, Samuel R.; Kuznets, Roman
2
2012
Strong isomorphism reductions in complexity theory. Zbl 1248.03060
Buss, Sam; Chen, Yijia; Flum, Jörg; Friedman, Sy-David; Müller, Moritz
6
2011
Corrected upper bounds for free-cut elimination. Zbl 1267.03053
Beckmann, Arnold; Buss, Samuel R.
5
2011
Mathematical logic: proof theory, constructive mathematics. Abstracts fro the workshop held November 6–12, 2011. Zbl 1349.00097
1
2011
Characterising definable search problems in bounded arithmetic via proof notations. Zbl 1244.03163
Beckmann, Arnold; Buss, Samuel R.
8
2010
The quantifier complexity of polynomial-size iterated definitions in first-order logic. Zbl 1209.03005
Buss, Samuel R.; Johnson, Alan S.
1
2010
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic. Zbl 1204.03056
Beckmann, Arnold; Buss, Samuel R.
12
2009
The NP-completeness of reflected fragments of justification logics. Zbl 1211.03035
Buss, Samuel R.; Kuznets, Roman
3
2009
Resolution trees with lemmas: resolution refinements that characterize DLL algorithms with clause learning. Zbl 1159.03009
Buss, Samuel R.; Hoffmann, Jan; Johannsen, Jan
17
2008
The NP-hardness of finding a directed acyclic graph for regular resolution. Zbl 1145.03034
Buss, Samuel R.; Hoffmann, Jan
2
2008
Diffusion, quantum theory, and radically elementary mathematics. Zbl 1104.81003
22
2006
Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies. Zbl 1094.03044
Buss, Samuel R.
3
2006
Separation results for the size of constant-depth propositional proofs. Zbl 1089.03048
Beckmann, Arnold; Buss, Samuel R.
7
2005
Mathematical logic: proof theory, type theory and constructive mathematics. Zbl 1066.03501
1
2005
A switching lemma for small restrictions and lower bounds for \(k\)-DNF resolution. Zbl 1059.03063
Segerlind, Nathan; Buss, Sam; Impagliazzo, Russell
29
2004
Bounded arithmetic and constant depth Frege proofs. Zbl 1079.03050
Buss, Samuel R.
2
2004
Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis. Zbl 1070.92036
Buss, Samuel R.; Clote, Peter
1
2004
Ordinal notations and well-orderings in bounded arithmetic. Zbl 1015.03055
Beckmann, Arnold; Pollett, Chris; Buss, Samuel R.
3
2003
3-D computer graphics. A mathematical introduction with OpenGL. Zbl 1044.65017
Buss, Samuel R.
2
2003
Resource-bounded continuity and sequentiality for type-two functionals. Zbl 1365.03029
Buss, Samuel R.; Kapron, Bruce M.
3
2002
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1007.03052
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
33
2001
Minimum propositional proof length is NP-hard to linearly approximate. Zbl 0977.03032
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
16
2001
On the computational content of intuitionistic propositional proofs. Zbl 1009.03027
Buss, Samuel R.; Pudlák, Pavel
8
2001
The prospects for mathematical logic in the twenty-first century. Zbl 0981.03003
Buss, Samuel R.; Kechris, Alexander S.; Pillay, Anand; Shore, Richard A.
5
2001
Accurate and efficient simulation of rigid-body rotations. Zbl 1035.70500
Buss, Samuel R.
8
2000
Incompleteness of behavioral logics. Zbl 0959.03506
Buss, Samuel; Roşu, Grigore
6
2000
Logic colloquium ’98. Proceedings of the annual European summer meeting of the Association for Symbolic Logic, Prague, Czech Republic, August 9–15, 1998. Zbl 0932.00038
1
2000
Propositional proof complexity: an introduction. Zbl 0946.68128
Buss, Samuel R.
12
1999
The complexity of the disjunction and existential properties in intuitionistic logic. Zbl 0939.03064
Buss, Sam; Mints, Grigori
10
1999
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1345.03105
Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann
5
1999
Bounded arithmetic, proof complexity and two papers of Parikh. Zbl 0924.03106
Buss, Samuel R.
3
1999
Handbook of proof theory. Zbl 0898.03001
72
1998
An introduction to proof theory. Zbl 0912.03024
Buss, Samuel R.
65
1998
First-order proof theory of arithmetic. Zbl 0911.03029
Buss, Samuel R.
32
1998
Resolution and the weak pigeonhole principle. Zbl 0910.03036
Buss, Sam; Pitassi, Toniann
19
1998
Minimum propositional proof length is NP-hard to linearly approximate (extended abstract). Zbl 0911.03028
Alekhnovich, Michael; Buss, Sam; Moran, Shlomo; Pitassi, Toniann
12
1998
Lower bounds on Nullstellensatz proofs via designs. Zbl 0890.03029
Buss, Samuel R.
10
1998
Good degree bounds on Nullstellensatz refutations of the induction principle. Zbl 0921.68088
Buss, Samuel R.; Pitassi, Toniann
8
1998
Linear and time minimum-cost matching algorithms for quasi-convex tours. Zbl 0913.05086
Buss, Samuel R.; Yianilos, Peter N.
5
1998
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
32
1997
Alogtime algorithms for tree isomorphism, comparison, and canonization. Zbl 0884.68098
Buss, Samuel R.
17
1997
Bounded arithmetic and propositional proof complexity. Zbl 0882.68130
Buss, Samuel R.
10
1997
Cutting planes, connectivity, and threshold logic. Zbl 0841.03029
Buss, Samuel R.; Clote, Peter
10
1996
Relating the bounded arithmetic and polynomial time hierarchies. Zbl 0829.03035
Buss, Samuel R.
19
1995
Are there hard examples for Frege systems? Zbl 0834.03021
Bonet, Maria Luisa; Buss, Samuel R.; Pitassi, Toniann
19
1995
On Herbrand’s theorem. Zbl 1540.03102
Buss, Samuel R.
15
1995
Unprovability of consistency statements in fragments of bounded arithmetic. Zbl 0834.03022
Buss, Samuel R.; Ignjatović, Aleksandar
10
1995
How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542
Pudlák, Pavel; Buss, Samuel R.
10
1995
Some remarks on lengths of propositional proofs. Zbl 0841.03030
Buss, Samuel R.
7
1995
The serial transitive closure problem for trees. Zbl 0828.68099
Bonet, Maria Luisa; Buss, Samuel R.
2
1995
On Gödel’s theorems on lengths of proofs. II: Lower bounds for recognizing \(k\) symbol provability. Zbl 0829.03034
Buss, Samuel R.
2
1995
An application of Boolean complexity to separation problems in bounded arithmetic. Zbl 0799.03066
Buss, Samuel R.; Krajíček, Jan
25
1994
Size-depth tradeoffs for Boolean formulae. Zbl 0802.68067
Bonet, Maria Luisa; Buss, Samuel R.
18
1994
On Gödel’s theorems on lengths of proofs. I: Number of lines and speedup for arithmetics. Zbl 0805.03047
Buss, Samuel R.
11
1994
The witness function method and provably recursive functions of Peano arithmetic. Zbl 0829.03036
Buss, Samuel R.
9
1994
Linear and \(O(n \text{log} n)\) time minimum-cost matching algorithms for quasi-convex tours. Zbl 0867.05071
Buss, Samuel R.; Yianilos, Peter N.
4
1994
Algorithms for Boolean formula evaluation and for tree contraction. Zbl 0792.68046
Buss, Samuel R.
14
1993
The deduction rule and linear and near-linear proof simulations. Zbl 0848.03028
Bonet, Maria Luisa; Buss, Samuel R.
10
1993
Intuitionistic validity in \(T\)-normal Kripke structures. Zbl 0802.03006
Buss, Samuel R.
10
1993
Provably total function in bounded arithmetic theories \(R_ 3^ i\), \(U_ 2^ i\) and \(V_ 2^ i\). Zbl 0799.03065
Buss, Samuel R.; Krajíček, Jan; Takeuti, Gaisi
7
1993
An optimal parallel algorithm for formula evaluation. Zbl 0825.68424
Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.
29
1992
A note on bootstrapping intuitionistic bounded arithmetic. Zbl 0792.03039
Buss, Samuel R.
5
1992
The graph of multiplication is equivalent to counting. Zbl 0748.68018
Buss, Samuel R.
3
1992
On truth-table reducibility to SAT. Zbl 0800.68443
Buss, Samuel R.; Hay, Louise
36
1991
The undecidability of \(k\)-provability. Zbl 0749.03039
Buss, Samuel R.
25
1991
Propositional consistency proofs. Zbl 0749.03040
Buss, Samuel R.
13
1991
...and 10 more Documents
all top 5

Cited by 897 Authors

53 Buss, Samuel R.
27 Beyersdorff, Olaf
19 Krajíček, Jan
17 Pitassi, Toniann
16 Visser, Albert
15 Beckmann, Arnold
15 Pudlák, Pavel
15 Thapen, Neil
14 Atserias, Albert
14 Jeřábek, Emil
13 Goldberg, Paul W.
12 Galesi, Nicola
11 Nordström, Jakob
11 Tzameret, Iddo
10 Razborov, Aleksandr Aleksandrovich
9 Blinkhorn, Joshua
9 Hollender, Alexandros
9 Kołodziejczyk, Leszek Aleksander
9 Lauria, Massimo
9 Mahajan, Meena
9 Subramani, Krishnan
8 Hetzl, Stefan
8 Itsykson, Dmitry M.
8 Müller, Moritz
7 Bonet, Maria Luisa
7 Eiter, Thomas
7 Grigor’ev, Dmitriĭ Yur’evich
7 Impagliazzo, Russell
7 Takeuti, Gaisi
6 Allender, Eric W.
6 Clote, Peter G.
6 Cook, Stephen Arthur
6 Filos-Ratsikas, Aris
6 Iemhoff, Rosalie
6 Kohlenbach, Ulrich Wilhelm
6 Martin, Barnaby D.
6 Pich, Ján
6 Pollett, Chris
5 Arai, Toshiyasu
5 Avigad, Jeremy
5 Dantchev, Stefan Stoyanov
5 Das, Anupam
5 Gratzl, Norbert
5 Hirsch, Edward A.
5 Johannsen, Jan
5 Köbler, Johannes
5 Limaye, Nutan
5 Lohrey, Markus
5 Meir, Or
5 Moniri, Morteza
5 Raz, Ran
5 Robere, Robert
5 Soltys, Michael
5 Straßburger, Lutz
5 Vialette, Stéphane
5 Willard, Dan E.
5 Wojciechowski, Piotr J.
4 Adamowicz, Zofia
4 Aisenberg, James
4 Baaz, Matthias
4 Beame, Paul W.
4 de Rezende, Susanna F.
4 Di Stefano, Gabriele
4 Dinur, Irit
4 Eberhard, Sebastian
4 Fearnley, John
4 Ferreira, Fernando
4 Gentilini, Paolo
4 Hinde, Luke
4 Joosten, Joost J.
4 Kolokolova, Antonina
4 Moser, Georg
4 Navarra, Alfredo
4 Nicolai, Carlo
4 Pakhomov, Fedor N.
4 Papadimitriou, Christos Harilaos
4 Roşu, Grigore
4 Sanders, Sam
4 Sorbi, Andrea
4 Strahm, Thomas
4 Sureson, Claude
4 Urquhart, Alasdair
4 Wigderson, Avi
3 Alekseev, Yaroslav
3 Arai, Noriko H.
3 Arvind, Vikraman
3 Aschieri, Federico
3 Basu, Amitabh
3 Ben-Sasson, Eli
3 Bonacina, Ilario
3 Carbone, Alessandra
3 Cenzer, Douglas
3 Chew, Leroy
3 Ciabattoni, Agata
3 Cohen, Liron
3 Dal Lago, Ugo
3 D’Aquino, Paola
3 Deligkas, Argyrios
3 Ferreira, Gilda
3 Göös, Mika
...and 797 more Authors
all top 5

Cited in 120 Serials

106 Annals of Pure and Applied Logic
71 Theoretical Computer Science
50 Archive for Mathematical Logic
40 The Journal of Symbolic Logic
29 Journal of Computer and System Sciences
27 Information and Computation
19 Computational Complexity
18 The Bulletin of Symbolic Logic
15 Studia Logica
15 Mathematical Logic Quarterly (MLQ)
15 ACM Transactions on Computational Logic
14 Theory of Computing Systems
13 Information Processing Letters
12 Journal of Philosophical Logic
11 Logical Methods in Computer Science
10 Notre Dame Journal of Formal Logic
10 SIAM Journal on Computing
10 The Review of Symbolic Logic
9 Artificial Intelligence
9 Discrete Applied Mathematics
7 Journal of Automated Reasoning
7 Annals of Mathematics and Artificial Intelligence
6 Mathematical Structures in Computer Science
5 Synthese
5 Algorithmica
5 Logica Universalis
4 Proceedings of the American Mathematical Society
4 The Journal of Artificial Intelligence Research (JAIR)
3 Transactions of the American Mathematical Society
3 Mathematical Programming. Series A. Series B
3 Journal of Applied Non-Classical Logics
3 Journal of Mathematical Sciences (New York)
3 Journal of the ACM
3 Journal of Mathematical Logic
3 Journal of Applied Logic
3 Oberwolfach Reports
3 Theory of Computing
2 Advances in Mathematics
2 Fundamenta Mathematicae
2 Mathematical Systems Theory
2 International Journal of Foundations of Computer Science
2 RAIRO. Informatique Théorique et Applications
2 Journal of Logic, Language and Information
2 The Journal of Logic and Algebraic Programming
2 Theory and Practice of Logic Programming
2 Portugaliae Mathematica. Nova Série
2 Journal of Discrete Algorithms
2 Journal of Logic and Analysis
2 Computability
1 Acta Informatica
1 American Mathematical Monthly
1 Computer Methods in Applied Mechanics and Engineering
1 Computer Physics Communications
1 Discrete Mathematics
1 Israel Journal of Mathematics
1 Journal of Computational Physics
1 Journal of the Franklin Institute
1 Mathematical Methods in the Applied Sciences
1 Automatica
1 Bulletin of the London Mathematical Society
1 International Journal for Numerical Methods in Engineering
1 Journal of Algebra
1 Journal of Combinatorial Theory. Series A
1 Journal of Computational and Applied Mathematics
1 Journal of Graph Theory
1 Journal of Pure and Applied Algebra
1 Networks
1 Proceedings of the Japan Academy. Series A
1 Rendiconti del Seminario Matemàtico e Fisico di Milano
1 Semigroup Forum
1 Bulletin of the Section of Logic
1 European Journal of Combinatorics
1 Combinatorica
1 History and Philosophy of Logic
1 Acta Applicandae Mathematicae
1 Journal of Symbolic Computation
1 Discrete & Computational Geometry
1 Mathematical and Computer Modelling
1 SIAM Journal on Discrete Mathematics
1 Formal Aspects of Computing
1 AI Communications
1 Random Structures & Algorithms
1 International Journal of Algebra and Computation
1 Discrete Event Dynamic Systems
1 Games and Economic Behavior
1 European Journal of Operational Research
1 Bulletin of the American Mathematical Society. New Series
1 Distributed Computing
1 Indagationes Mathematicae. New Series
1 Applicable Algebra in Engineering, Communication and Computing
1 Formal Methods in System Design
1 The Electronic Journal of Combinatorics
1 Advances in Computational Mathematics
1 Mathematical Communications
1 Differential Equations and Dynamical Systems
1 Journal of Combinatorial Optimization
1 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
1 Annals of Mathematics. Second Series
1 Interdisciplinary Information Sciences (IIS)
1 Erkenntnis
...and 20 more Serials
all top 5

Cited in 39 Fields

606 Mathematical logic and foundations (03-XX)
490 Computer science (68-XX)
51 Combinatorics (05-XX)
22 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
21 Operations research, mathematical programming (90-XX)
15 Information and communication theory, circuits (94-XX)
14 General and overarching topics; collections (00-XX)
11 Order, lattices, ordered algebraic structures (06-XX)
9 History and biography (01-XX)
7 Dynamical systems and ergodic theory (37-XX)
7 Mechanics of particles and systems (70-XX)
7 Quantum theory (81-XX)
6 Number theory (11-XX)
6 Commutative algebra (13-XX)
6 Numerical analysis (65-XX)
5 Group theory and generalizations (20-XX)
4 General algebraic systems (08-XX)
3 Category theory; homological algebra (18-XX)
3 Measure and integration (28-XX)
3 Probability theory and stochastic processes (60-XX)
3 Systems theory; control (93-XX)
2 Linear and multilinear algebra; matrix theory (15-XX)
2 Real functions (26-XX)
2 Algebraic topology (55-XX)
2 Manifolds and cell complexes (57-XX)
2 Global analysis, analysis on manifolds (58-XX)
2 Biology and other natural sciences (92-XX)
2 Mathematics education (97-XX)
1 Field theory and polynomials (12-XX)
1 Algebraic geometry (14-XX)
1 Nonassociative rings and algebras (17-XX)
1 Partial differential equations (35-XX)
1 Geometry (51-XX)
1 Convex and discrete geometry (52-XX)
1 Differential geometry (53-XX)
1 General topology (54-XX)
1 Mechanics of deformable solids (74-XX)
1 Fluid mechanics (76-XX)
1 Optics, electromagnetic theory (78-XX)

Citations by Year