Edit Profile (opens in new tab) Buss, Samuel R. Co-Author Distance 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,451 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 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,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 cited Publications top 5 cited Publications 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