Samuel R. Buss - Author Profile

Edit Profile

Buss, Samuel R.

Author ID:	buss.samuel-r
Published as:	Buss, Samuel R.; Buss, Sam; Buss, Samuel; Buss, S.; Buss, S. R. more...less
Homepage:	https://mathweb.ucsd.edu/~sbuss/
External Links:	MGP · ORCID · dblp

Documents Indexed:	120 Publications since 1986, including 2 Books
	15 Contributions as Editor · 1 Further Contribution
Co-Authors:	78 Co-Authors with 91 Joint Publications
	2,479 Co-Co-Authors

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 Kumar
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

all top 5

Serials

19	Annals of Pure and Applied Logic
10	The Journal of Symbolic Logic
7	Oberwolfach Reports
5	Theoretical Computer Science
4	Journal of Computer and System Sciences
4	SIAM Journal on Computing
4	Archive for Mathematical Logic
4	ACM Transactions on Computational Logic
4	Logical Methods in Computer Science
3	Information Processing Letters
2	Information and Computation
2	Computational Complexity
2	Mathematical Logic Quarterly (MLQ)
2	The Bulletin of Symbolic Logic
1	Advances in Applied Probability
1	Artificial Intelligence
1	Journal of Computational Physics
1	Kiberneticheskiĭ Sbornik. Novaya Seriya
1	Notre Dame Journal of Formal Logic
1	Proceedings of the American Mathematical Society
1	Proceedings of the London Mathematical Society. Third Series
1	Studia Logica
1	Transactions of the American Mathematical Society
1	Complex Systems
1	The Journal of Artificial Intelligence Research (JAIR)
1	Journal of Mathematical Logic
1	DIMACS. Series in Discrete Mathematics and Theoretical Computer Science
1	Lecture Notes in Logic
1	Mathematical Notes (Princeton)
1	Progress in Computer Science and Applied Logic
1	Studies in Logic and the Foundations of Mathematics
1	Studies in Proof Theory. Lecture Notes
1	Journal of Satisfiability, Boolean Modeling and Computation
1	Computability

all top 5

Fields

115	Mathematical logic and foundations (03-XX)
71	Computer science (68-XX)
16	General and overarching topics; collections (00-XX)
7	Combinatorics (05-XX)
2	Probability theory and stochastic processes (60-XX)
2	Operations research, mathematical programming (90-XX)
2	Information and communication theory, circuits (94-XX)
1	History and biography (01-XX)
1	Convex and discrete geometry (52-XX)
1	Numerical analysis (65-XX)
1	Mechanics of particles and systems (70-XX)
1	Quantum theory (81-XX)
1	Biology and other natural sciences (92-XX)

Publications by Year

all cited Publications top 5 cited Publications

Citations contained in zbMATH Open

110 Publications have been cited 1,350 times in 866 Documents	Cited by ▼	Year ▼
Bounded arithmetic. Zbl 0649.03042 Buss, Samuel R.	153	1986
Handbook of proof theory. Zbl 0898.03001	72	1998
An introduction to proof theory. Zbl 0912.03024 Buss, Samuel R.	64	1998
Polynomial size proofs of the propositional pigeonhole principle. Zbl 0636.03053 Buss, Samuel R.	58	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
First-order proof theory of arithmetic. Zbl 0911.03029 Buss, Samuel R.	32	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.	31	1997
A switching lemma for small restrictions and lower bounds for \(k\)-DNF resolution. Zbl 1059.03063 Segerlind, Nathan; Buss, Sam; Impagliazzo, Russell	29	2004
An optimal parallel algorithm for formula evaluation. Zbl 0825.68424 Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.	29	1992
The undecidability of \(k\)-provability. Zbl 0749.03039 Buss, Samuel R.	25	1991
Propositional proofs and reductions between NP search problems. Zbl 1252.03127 Buss, Samuel R.; Johnson, Alan S.	25	2012
An application of Boolean complexity to separation problems in bounded arithmetic. Zbl 0799.03066 Buss, Samuel R.; Krajíček, Jan	25	1994
Towards NP-P via proof complexity and search. Zbl 1257.03086 Buss, Samuel R.	23	2012
Resolution proofs of generalized pigeonhole principles. Zbl 0709.03006 Buss, Samuel R.; Turán, György	23	1988
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
Are there hard examples for Frege systems? Zbl 0834.03021 Bonet, Maria Luisa; Buss, Samuel R.; Pitassi, Toniann	19	1995
Relating the bounded arithmetic and polynomial time hierarchies. Zbl 0829.03035 Buss, Samuel R.	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
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
Alogtime algorithms for tree isomorphism, comparison, and canonization. Zbl 0884.68098 Buss, Samuel R.	16	1997
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
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
Fragments of approximate counting. Zbl 1338.03107 Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Thapen, Neil	14	2014
Algorithms for Boolean formula evaluation and for tree contraction. Zbl 0792.68046 Buss, Samuel R.	14	1993
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
Propositional consistency proofs. Zbl 0749.03040 Buss, Samuel R.	13	1991
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
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic. Zbl 1204.03056 Beckmann, Arnold; Buss, Samuel R.	12	2009
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 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
Cutting planes, connectivity, and threshold logic. Zbl 0841.03029 Buss, Samuel R.; Clote, Peter	10	1996
Unprovability of consistency statements in fragments of bounded arithmetic. Zbl 0834.03022 Buss, Samuel R.; Ignjatović, Aleksandar	10	1995
Bounded arithmetic and propositional proof complexity. Zbl 0882.68130 Buss, Samuel R.	10	1997
Intuitionistic validity in \(T\)-normal Kripke structures. Zbl 0802.03006 Buss, Samuel R.	10	1993
The deduction rule and linear and near-linear proof simulations. Zbl 0848.03028 Bonet, Maria Luisa; Buss, Samuel R.	10	1993
The witness function method and provably recursive functions of Peano arithmetic. Zbl 0829.03036 Buss, Samuel R.	9	1994
Lower bounds on Nullstellensatz proofs via designs. Zbl 0890.03029 Buss, Samuel R.	9	1998
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
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
Separation results for the size of constant-depth propositional proofs. Zbl 1089.03048 Beckmann, Arnold; Buss, Samuel R.	7	2005
Some remarks on lengths of propositional proofs. Zbl 0841.03030 Buss, Samuel R.	7	1995
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
Cut elimination in situ. Zbl 1380.03062 Buss, Sam	7	2015
Improved separations of regular resolution from clause learning proof systems. Zbl 1361.68185 Bonet, Maria Luisa; Buss, Sam; Johannsen, Jan	6	2014
Strong isomorphism reductions in complexity theory. Zbl 1248.03060 Buss, Sam; Chen, Yijia; Flum, Jörg; Friedman, Sy-David; Müller, Moritz	6	2011
DRAT proofs, propagation redundancy, and extended resolution. Zbl 1441.03043 Buss, Sam; Thapen, Neil	6	2019
Incompleteness of behavioral logics. Zbl 0959.03506 Buss, Samuel; Roşu, Grigore	6	2000
On the predictability of coupled automata: An allegory about chaos. Zbl 0760.68031 Buss, Samuel R.; Papadimitriou, Christos H.; Tsitsiklis, John N.	6	1991
On model theory for intuitionistic bounded arithmetic with applications to independence results. Zbl 0764.03021 Buss, Samuel R.	6	1990
Linear gaps between degrees for the polynomial calculus modulo distinct primes. Zbl 1345.03105 Buss, Sam; Grigoriev, Dima; Impagliazzo, Russell; Pitassi, Toniann	5	1999
Quasipolynomial size proofs of the propositional pigeonhole principle. Zbl 1347.03100 Buss, Sam	5	2015
Small Stone in pool. Zbl 1336.03019 Buss, Samuel R.; Kolodziejczyk, Leszek Alek	5	2014
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
Linear and time minimum-cost matching algorithms for quasi-convex tours. Zbl 0913.05086 Buss, Samuel R.; Yianilos, Peter N.	5	1998
A note on bootstrapping intuitionistic bounded arithmetic. Zbl 0792.03039 Buss, Samuel R.	5	1992
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
Corrected upper bounds for free-cut elimination. Zbl 1267.03053 Beckmann, Arnold; Buss, Samuel R.	5	2011
Reordering rule makes OBDD proof systems stronger. Zbl 1441.03042 Buss, Sam; Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry	5	2018
DRMaxSAT with MaxHS: first contact. Zbl 1441.68232 Morgado, Antonio; Ignatiev, Alexey; Bonet, Maria Luisa; Marques-Silva, Joao; Buss, Sam	4	2019
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
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
The modal logic of pure provability. Zbl 0713.03009 Buss, Samuel R.	4	1990
Cobham recursive set functions. Zbl 1383.03050 Beckmann, Arnold; Buss, Sam; Friedman, Sy-David; Müller, Moritz; Thapen, Neil	3	2016
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080 Buss, Samuel R.; Williams, Ryan	3	2015
The NP-completeness of reflected fragments of justification logics. Zbl 1211.03035 Buss, Samuel R.; Kuznets, Roman	3	2009
Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies. Zbl 1094.03044 Buss, Samuel R.	3	2006
Bounded arithmetic, proof complexity and two papers of Parikh. Zbl 0924.03106 Buss, Samuel R.	3	1999
The graph of multiplication is equivalent to counting. Zbl 0748.68018 Buss, Samuel R.	3	1992
Ordinal notations and well-orderings in bounded arithmetic. Zbl 1015.03055 Beckmann, Arnold; Pollett, Chris; Buss, Samuel R.	3	2003
The NP search problems of Frege and extended Frege proofs. Zbl 1407.03071 Beckmann, Arnold; Buss, Sam	3	2017
Resource-bounded continuity and sequentiality for type-two functionals. Zbl 1365.03029 Buss, Samuel R.; Kapron, Bruce M.	3	2002
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
Strategies for stable merge sorting. Zbl 1431.68021 Buss, Sam; Knop, Alexander	3	2019
Injection structures specified by finite state transducers. Zbl 1485.03108 Buss, Sam; Cenzer, Douglas; Minnes, Mia; Remmel, Jeffrey B.	3	2017
Sub-computable boundedness randomness. Zbl 1325.03050 Buss, Sam; Cenzer, Douglas; Remmel, Jeffrey B.	2	2014
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
Bounded arithmetic and constant depth Frege proofs. Zbl 1079.03050 Buss, Samuel R.	2	2004
Lower complexity bounds in justification logic. Zbl 1243.03026 Buss, Samuel R.; Kuznets, Roman	2	2012
Expander construction in \(\mathrm{VNC}^1\). Zbl 1481.03065 Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal	2	2020
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
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
DRAT and propagation redundancy proofs without new variables. Zbl 1535.03275 Buss, Sam; Thapen, Neil	2	2021
On the consistency of circuit lower bounds for non-deterministic time. Zbl 07844669 Atserias, Albert; Buss, Sam; Müller, Moritz	2	2023
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
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
Expander construction in \(\mathrm{VNC}^1\). Zbl 1481.03065 Buss, Sam; Kabanets, Valentine; Kolokolova, Antonina; Koucký, Michal	2	2020
Proof complexity of systems of (non-deterministic) decision trees and branching programs. Zbl 07650825 Buss, Sam; Das, Anupam; Knop, Alexander	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
Quasipolynomial size proofs of the propositional pigeonhole principle. Zbl 1347.03100 Buss, Sam	5	2015
Safe recursive set functions. Zbl 1357.03075 Beckmann, Arnold; Buss, Samuel R.; Friedman, Sy-David	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.	64	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.	9	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.	31	1997
Alogtime algorithms for tree isomorphism, comparison, and canonization. Zbl 0884.68098 Buss, Samuel R.	16	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
Are there hard examples for Frege systems? Zbl 0834.03021 Bonet, Maria Luisa; Buss, Samuel R.; Pitassi, Toniann	19	1995
Relating the bounded arithmetic and polynomial time hierarchies. Zbl 0829.03035 Buss, Samuel R.	19	1995
On Herbrand’s theorem. Zbl 1540.03102 Buss, Samuel R.	15	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
Unprovability of consistency statements in fragments of bounded arithmetic. Zbl 0834.03022 Buss, Samuel R.; Ignjatović, Aleksandar	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
Intuitionistic validity in \(T\)-normal Kripke structures. Zbl 0802.03006 Buss, Samuel R.	10	1993
The deduction rule and linear and near-linear proof simulations. Zbl 0848.03028 Bonet, Maria Luisa; 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 cited Publications top 5 cited Publications

all top 5

Cited by 891 Authors

53	Buss, Samuel R.
27	Beyersdorff, Olaf
18	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	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	Pich, Ján
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 791 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
18	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
4	The Journal of Artificial Intelligence Research (JAIR)
4	Logica Universalis
3	Proceedings of the American Mathematical Society
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

598	Mathematical logic and foundations (03-XX)
488	Computer science (68-XX)
51	Combinatorics (05-XX)
22	Game theory, economics, finance, and other social and behavioral sciences (91-XX)
20	Operations research, mathematical programming (90-XX)
15	Information and communication theory, circuits (94-XX)
14	General and overarching topics; collections (00-XX)
10	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	Group theory and generalizations (20-XX)
6	Numerical analysis (65-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)

Buss, Samuel R.

Co-Authors

Serials

Fields

Publications by Year

Citations contained in zbMATH Open

Cited by 891 Authors

Cited in 120 Serials

Cited in 39 Fields

Citations by Year