All Stories

  1. On the Consistency of Circuit Lower Bounds for Non-deterministic Time

    Article • June 2023, ACM (Association for Computing Machinery)

    Samuel R Buss

  2. Lower Bounds on OBDD Proofs with Several Orders

    Article • ACM Transactions on Computational Logic, October 2021, ACM (Association for Computing Machinery)

    Samuel R Buss

  3. Feasible set functions have small circuits

    Article • Computability, December 2018, IOS Press

    Arnold Beckmann, Samuel R Buss

  4. The NP Search Problems of Frege and Extended Frege Proofs

    Article • ACM Transactions on Computational Logic, April 2017, ACM (Association for Computing Machinery)

    Arnold Beckmann, Samuel R Buss

  5. SAFE RECURSIVE SET FUNCTIONS

    Article • Journal of Symbolic Logic, July 2015, Cambridge University Press

    Samuel R Buss, Arnold Beckmann

  6. Limits on Alternation Trading Proofs for Time–Space Lower Bounds

    Article • Computational Complexity, May 2015, Springer Science + Business Media

    Samuel R Buss

  7. Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination

    Article • Studia Logica, May 2015, Springer Science + Business Media

    Samuel R Buss

  8. Quasipolynomial size proofs of the propositional pigeonhole principle

    Article • Theoretical Computer Science, April 2015, Elsevier

    Samuel R Buss

  9. Collapsing modular counting in bounded arithmetic and constant depth propositional proofs

    Article • Transactions of the American Mathematical Society, February 2015, American Mathematical Society (AMS)

    Samuel R Buss

  10. Propositional Proofs in Frege and Extended Frege Systems (Abstract)

    Article • January 2015, Springer Science + Business Media

    Samuel R Buss

  11. Short Proofs of the Kneser-Lovász Coloring Principle

    Article • January 2015, Springer Science + Business Media

    Samuel R Buss

  12. Sub-computable Boundedness Randomness

    Article • Logical Methods in Computer Science, December 2014, Logical Methods in Computer Science

    Samuel R Buss

  13. Small Stone in Pool

    Article • Logical Methods in Computer Science, June 2014, Logical Methods in Computer Science

    Samuel R Buss

  14. FRAGMENTS OF APPROXIMATE COUNTING

    Article • Journal of Symbolic Logic, June 2014, Cambridge University Press

    Samuel R Buss

  15. Unshuffling a square is NP-hard

    Article • Journal of Computer and System Sciences, June 2014, Elsevier

    Samuel R Buss

  16. Improved witnessing and local improvement principles for second-order bounded arithmetic

    Article • ACM Transactions on Computational Logic, February 2014, ACM (Association for Computing Machinery)

    Samuel R Buss

  17. Probabilistic Algorithmic Randomness

    Article • Journal of Symbolic Logic, June 2013, Cambridge University Press

    Samuel R Buss

  18. Alternation Trading Proofs and Their Limitations

    Article • January 2013, Springer Science + Business Media

    Samuel R Buss

  19. Towards

    Article • Annals of Pure and Applied Logic, July 2012, Elsevier

    Samuel R Buss

  20. Lower complexity bounds in justification logic

    Article • Annals of Pure and Applied Logic, July 2012, Elsevier

    Samuel R Buss

  21. Sharpened lower bounds for cut elimination

    Article • Journal of Symbolic Logic, June 2012, Cambridge University Press

    Samuel R Buss

  22. Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

    Article • June 2012, Institute of Electrical & Electronics Engineers (IEEE)

    Samuel R Buss

  23. An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning

    Article • January 2012, Springer Science + Business Media

    Samuel R Buss

  24. Strong isomorphism reductions in complexity theory

    Article • Journal of Symbolic Logic, December 2011, Cambridge University Press

    Samuel R Buss

  25. Corrected upper bounds for free-cut elimination

    Article • Theoretical Computer Science, September 2011, Elsevier

    Samuel R Buss

  26. The quantifier complexity of polynomial-size iterated definitions in first-order logic

    Article • November 2010, Wiley

    Samuel R Buss

  27. Pool resolution is NP-hard to recognize

    Article • Archive for Mathematical Logic, September 2009, Springer Science + Business Media

    Samuel R Buss

  28. POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC

    Article • Journal of Mathematical Logic, June 2009, World Scientific Pub Co Pte Lt

    Samuel R Buss

  29. Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning

    Article • Logical Methods in Computer Science, December 2008, Logical Methods in Computer Science

    Samuel R Buss

  30. The NP-hardness of finding a directed acyclic graph for regular resolution

    Article • Theoretical Computer Science, May 2008, Elsevier

    Samuel R Buss

  31. Bounded Arithmetic, Cryptography and Complexity

    Article • Theoria, February 2008, Wiley

    Samuel R Buss

  32. The Computational Power of Bounded Arithmetic from the Predicative Viewpoint

    Article • January 2008, Springer Science + Business Media

    Samuel R Buss

  33. The NP-Completeness of Reflected Fragments of Justification Logics

    Article • January 2008, Springer Science + Business Media

    Samuel R Buss

  34. Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies

    Article • Theoretical Computer Science, July 2006, Elsevier

    Samuel R Buss

  35. Separation results for the size of constant-depth propositional proofs

    Article • Annals of Pure and Applied Logic, October 2005, Elsevier

    Samuel R Buss

  36. Collision detection with relative screw motion

    Article • The Visual Computer, February 2005, Springer Science + Business Media

    Samuel R Buss

  37. Selectively Damped Least Squares for Inverse Kinematics

    Article • Journal of Graphics Tools, January 2005, Taylor & Francis

    Samuel R Buss

  38. Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis

    Article • Advances in Applied Probability, December 2004, Cambridge University Press

    Samuel R Buss

  39. A Switching Lemma for Small Restrictions and Lower Bounds for k -DNF Resolution

    Article • SIAM Journal on Computing, January 2004, Society for Industrial & Applied Mathematics (SIAM)

    Samuel R Buss

  40. Erratum to “Ordinal notations and well-orderings in bounded arithmetic” [Annals of Pure and Applied Logic 120 (2003) 197–223]

    Article • Annals of Pure and Applied Logic, October 2003, Elsevier

    Samuel R Buss

  41. Ordinal notations and well-orderings in bounded arithmetic

    Article • Annals of Pure and Applied Logic, April 2003, Elsevier

    Samuel R Buss

  42. 3-D Computer Graphics

    Article • January 2003, Cambridge University Press

    Samuel R Buss

  43. Resource-bounded continuity and sequentiality for type-two functionals

    Article • ACM Transactions on Computational Logic, July 2002, ACM (Association for Computing Machinery)

    Samuel R Buss

  44. Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate

    Article • Bulletin of Symbolic Logic, June 2002, Cambridge University Press

    Samuel R Buss

  45. Michael Alekhnovich, Sam Buss, Shlomo Moran, and Toniann Pitassi. Minimum propositional proof length is NP-hard to linearly approximate. The journal of symbolic logic, vol. 66 (2001), pp. 171–191.

    Article • Bulletin of Symbolic Logic, June 2002, Cambridge University Press

    Samuel R Buss

  46. The Prospects for Mathematical Logic in the Twenty-First Century

    Article • Bulletin of Symbolic Logic, June 2001, Cambridge University Press

    Samuel R Buss

  47. On the computational content of intuitionistic propositional proofs

    Article • Annals of Pure and Applied Logic, May 2001, Elsevier

    Samuel R Buss

  48. Spherical averages and applications to spherical splines and interpolation

    Article • ACM Transactions on Graphics, April 2001, ACM (Association for Computing Machinery)

    Samuel R Buss

  49. Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes

    Article • Journal of Computer and System Sciences, March 2001, Elsevier

    Samuel R Buss

  50. Minimum propositional proof length is NP-hard to linearly approximate

    Article • Journal of Symbolic Logic, March 2001, Cambridge University Press

    Samuel R Buss

  51. Samuel R. Buss. An introduction to proof theory. Handbook of proof theory, edited by Samuel R. Buss, Studies in logic and the foundations of mathematics, vol. 137, Elsevier, Amsterdam etc. 1998, p. v., pp. 1–78.

    Article • Bulletin of Symbolic Logic, December 2000, Cambridge University Press

    Samuel R Buss

  52. Samuel R. Buss. First-order proof theory of arithmetic. Handbook of proof theory, edited by Samuel R. Buss, Studies in logic and the foundations of mathematics, vol. 137, Elsevier, Amsterdam etc. 1998, pp. 79–147.

    Article • Bulletin of Symbolic Logic, December 2000, Cambridge University Press

    Samuel R Buss

  53. Accurate and Efficient Simulation of Rigid-Body Rotations

    Article • Journal of Computational Physics, November 2000, Elsevier

    Samuel R Buss

  54. Incompleteness of Behavioral Logics

    Article • Electronic Notes in Theoretical Computer Science, January 2000, Elsevier

    Samuel R Buss

  55. The complexity of the disjunction and existential properties in intuitionistic logic

    Article • Annals of Pure and Applied Logic, August 1999, Elsevier

    Samuel R Buss

  56. Bounded arithmetic, proof complexity and two papers of Parikh

    Article • Annals of Pure and Applied Logic, March 1999, Elsevier

    Samuel R Buss

  57. Propositional Proof Complexity an Introduction

    Article • January 1999, Springer Science + Business Media

    Samuel R Buss

  58. Linear gaps between degrees for the polynomial calculus modulo distinct primes

    Article • January 1999, ACM (Association for Computing Machinery)

    Samuel R Buss

  59. Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle

    Article • Journal of Computer and System Sciences, October 1998, Elsevier

    Samuel R Buss

  60. Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours

    Article • SIAM Journal on Computing, February 1998, Society for Industrial & Applied Mathematics (SIAM)

    Samuel R Buss

  61. An Introduction to Proof Theory

    Article • January 1998, Elsevier

    Samuel R Buss

  62. First-Order Proof Theory of Arithmetic

    Article • January 1998, Elsevier

    Samuel R Buss

  63. Resolution and the weak pigeonhole principle

    Article • January 1998, Springer Science + Business Media

    Samuel R Buss

  64. Minimum propositional proof length is NP-hard to linearly approximate

    Article • January 1998, Springer Science + Business Media

    Samuel R Buss

  65. Samuel R. Buss. The undecidability of k-provability. Annals of pure and applied logic, vol. 53 (1991), pp. 75–102.

    Article • Journal of Symbolic Logic, December 1997, Cambridge University Press

    Samuel R Buss

  66. Bounded Arithmetic and Propositional Proof Complexity

    Article • January 1997, Springer Science + Business Media

    Samuel R Buss

  67. Alogtime algorithms for tree isomorphism, comparison, and canonization

    Article • January 1997, Springer Science + Business Media

    Samuel R Buss

  68. Cutting planes, connectivity, and threshold logic

    Article • Archive for Mathematical Logic, January 1996, Springer Science + Business Media

    Samuel R Buss

  69. Cutting planes, connectivity, and threshold logic

    Article • Archive for Mathematical Logic, January 1996, Springer Science + Business Media

    Samuel R Buss

  70. Some remarks on lengths of propositional proofs

    Article • Archive for Mathematical Logic, December 1995, Springer Science + Business Media

    Samuel R Buss

  71. Relating the bounded arithmetic and polynomial time hierarchies

    Article • Annals of Pure and Applied Logic, September 1995, Elsevier

    Samuel R Buss

  72. Unprovability of consistency statements in fragments of bounded arithmetic

    Article • Annals of Pure and Applied Logic, August 1995, Elsevier

    Samuel R Buss

  73. The Serial Transitive Closure Problem for Trees

    Article • SIAM Journal on Computing, February 1995, Society for Industrial & Applied Mathematics (SIAM)

    Samuel R Buss

  74. On Herbrand's theorem

    Article • January 1995, Springer Science + Business Media

    Samuel R Buss

  75. Are there Hard Examples for Frege Systems?

    Article • January 1995, Springer Science + Business Media

    Samuel R Buss

  76. On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability

    Article • January 1995, Springer Science + Business Media

    Samuel R Buss

  77. How to lie without being (easily) convicted and the lengths of proofs in propositional calculus

    Article • January 1995, Springer Science + Business Media

    Samuel R Buss

  78. The witness function method and provably recursive functions of peano arithmetic

    Article • January 1995, Elsevier

    Samuel R Buss

  79. On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics

    Article • Journal of Symbolic Logic, September 1994, Cambridge University Press

    Samuel R Buss

  80. Size-depth tradeoffs for Boolean formulae

    Article • Information Processing Letters, February 1994, Elsevier

    Samuel R Buss

  81. The deduction rule and linear and near-linear proof simulations

    Article • Journal of Symbolic Logic, June 1993, Cambridge University Press

    Samuel R Buss

  82. Intuitionistic validity in T-normal Kripke structures

    Article • Annals of Pure and Applied Logic, February 1993, Elsevier

    Samuel R Buss

  83. The graph of multiplication is equivalent to counting

    Article • Information Processing Letters, March 1992, Elsevier

    Samuel R Buss

  84. The undecidability of k-provability

    Article • Annals of Pure and Applied Logic, July 1991, Elsevier

    Samuel R Buss

  85. Samuel R. Buss. Bounded arithmetic. Studies in proof theory. Lecture notes, no. 3. Bibliopolis, Naples1986, v + 221 pp.

    Article • Journal of Symbolic Logic, June 1991, Cambridge University Press

    Samuel R Buss

  86. Propositional consistency proofs

    Article • Annals of Pure and Applied Logic, April 1991, Elsevier

    Samuel R Buss

  87. On truth-table reducibility to SAT

    Article • Information and Computation, March 1991, Elsevier

    Samuel R Buss

  88. The modal logic of pure provability.

    Article • Notre Dame Journal of Formal Logic, March 1990, Duke University Press

    Samuel R Buss

  89. Feasible Mathematics

    Article • January 1990, Springer Science + Business Media

    Samuel R Buss

  90. Axiomatizations and conservation results for fragments of bounded arithmetic

    Article • January 1990, American Mathematical Society (AMS)

    Samuel R Buss

  91. On Model Theory for Intuitionistic Bounded Arithmetic with Applications to Independence Results

    Article • January 1990, Springer Science + Business Media

    Samuel R Buss

  92. Resolution proofs of generalized pigeonhole principles

    Article • Theoretical Computer Science, December 1988, Elsevier

    Samuel R Buss

  93. Polynomial size proofs of the propositional pigeonhole principle

    Article • Journal of Symbolic Logic, December 1987, Cambridge University Press

    Samuel R Buss

  94. A Conservation Result Concerning Bounded Theories and the Collection Axiom

    Article • Proceedings of the American Mathematical Society, August 1987, JSTOR

    Samuel R Buss

  95. A conservation result concerning bounded theories and the collection axiom

    Article • Proceedings of the American Mathematical Society, April 1987, American Mathematical Society (AMS)

    Samuel R Buss

  96. The polynomial hierarchy and intuitionistic Bounded Arithmetic

    Article • January 1986, Springer Science + Business Media

    Samuel R Buss

  97. Characterising Definable Search Problems in Bounded Arithmetic via Proof Notations

    Article • De Gruyter

    Samuel R Buss

  98. Chapter Eight. Nelson's Work on Logic and Foundations and Other Reflections on the Foundations of Mathematics

    Article • De Gruyter

    Samuel R Buss

  99. A note on bootstrapping intuitionistic bounded arithmetic

    Article • Cambridge University Press

    Samuel R Buss