Publications and Other Research

Sam Buss

 

This is my publication and research web page.  When possible, papers have been included in postscript and pdf format.  Warning:  These online versions may differ from the actual published versions (sometimes better, sometimes worse, than the published version). 

   You may also see my complete publication list (postscript or PDF format).   My entire CV is also available (postscript or PDF).

    For papers that are too recent to appear here, please email me, sbuss@ucsd.edu.

 

Copyright notice:  All material downloadable from this page is copyrighted by Sam Buss, his coauthors, and/or the publishers.

 

Publications.

 

Books (authored) 

  1. Samuel R. Buss, 3D Computer Graphics: A Mathematical Introduction with OpenGL, Cambridge University Press, 2003.
  2. Samuel R. Buss, Bounded Arithmetic, Bibliopolis, Naples 1986.  221+v pages. Revision of Ph.D. thesis.  

 

Books (edited) 

  1. Samuel R. Buss, Petr Hájek and Pavel Pudlák (eds), Logic Colloquium '98, Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Prague, Czech Republic, August 9-15, 1998, Lecture Notes in Logic 13, Association for Symbolic Logic, AK Peters, Natick, MA, 2000.  xvi+541 pages.
  2. Samuel R. Buss (ed.), Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics #137, Elsevier, Amsterdam, 1998, x+811 pages.
  3. Paul Beame and Samuel R. Buss (eds.), Proof Complexity and Feasible Arithmetics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science #39, American Mathematical Society, Providence, RI, 1998, xii+320 pages.
  4. Samuel R. Buss and Phillip J. Scott (eds.), Feasible Mathematics: A Mathematical Sciences Institute Workshop, Ithaca, New York June 1989, Progress in Computer Science #9, Birkhauser, Boston, 1990, viii+350 pages.

 

Patents

  1. Peter N. Yianilos and Samuel R. Buss, Associative Memory Circuit System and Method, continuation in part, U.S. Patent #4490811, December 1984.  European patent #83903352.9, January 1986.
  2. Samuel R. Buss and Peter N. Yianilos, Linear and Non-linear Time Methods for Minimum Cost Matching on Quasiconvex Tours, U.S. Patent #5841958, November 1998.

 

Software

  1. OpenGL Computer graphics software accompanying the book "3D Computer Graphics: A Mathematical Introduction with OpenGL".
  2. Raytrace software, accompanying the same book.
  3. Inverse Kinematics demos.  (with Jin-Su Kim).  Associated article and unpublished survey are also available.
  4. Spherical Averages and Spherical Splines.  Software for the Buss-Fillmore spherical averages algorithms.
  5. bussproofs.sty.  The "Buss proofs" LaTeX/TeX style file for creating proof trees.
  6. qcmatch. Quasiconvex minimum-cost matching algorithm in ANSI C.  (joint with D. Robinson, K. Kanzelberg, P. Yianilos).  Associated article and technical report also available.

 

Papers - journal articles and conference proceedings.  Click on the hyperlinked titles to reach a download page to obtain a copy of the article.

  1. (with Jan Hoffmann and Jan Johannsen). Weak Resolution Trees with Lemmas - Resolution Refinements that Characterize DLL-Algorithms with Clause Learning. In preparation.
  2. (with Jan Hoffmann). The NP-hardness of finding a directed acyclic graph for regular resolution. Theoretical Computer Science 396 (2008) 271-276.
  3. The Computational Power of Bounded Arithmetic from the Predicative Viewpoint, In New Computational Paradigms, Changing Conceptions of What is Computable, edited by S.B. Cooper, B. Löwe, A. Sorbi, Springer, New York, 2008, pp. 213-222.
  4. Nelson's Work on Logic and Foundations and Other Reflections on Foundations of Mathematics    In Diffusion, Quantum Theory, and Radically Elementary Mathematics, edited by W. Faris, Princeton University Press, 2006, pp. 183-208. Slides from a related talk also available.
  5. Bounded Arithmetic and Constant Depth Frege Proofs.   In Complexity of Computations and Proofs, edited by J. Krajicek, Quaderni di matematica, vol. 13, 2004, pp. 153-174.  Slides from a related conference presentation also available.
  6. (with A. Beckmann). Separation results for the size of constant-depth propositional proofs. Annals of Pure and Applied Logic 136, no.1-2 (2005).30-55.
  7. Collision Detection with Relative Screw Motion.  The Visual Computer 21 (2005) 41-58.
  8. (with Jin-Su Kim).  Selectively Damped Least Squares for Inverse Kinematics.  Journal of Graphics Tools, 10, no.3 (2005) 37-49..
  9. (with P. Clote) Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis.   Advances in Applied Probability 36, 4 (2004) 1175–1197.
  10. Polynomial-size Frege and Resolution Proofs of st-Connectivity and Hex Tautologies.    Theoretical Computer Science 357, no. 1-3, (2006) 35-52/
  11. (with N. Segerlind and R. Impagliazzo).  A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.    SIAM Journal on Computing 33, no 5 (2004) 1171-1200.  An earlier version appeared in the Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS'02), IEEE Computer Society, 2002, pp. 604-613.
  12. Accurate and efficient simulations of rigid body rotations.  Journal of Computational Physics 164 (2000) 377-406.    Slides from a related talk at SIAM Conference available below. 
  13. (with A.S. Kechris, A. Pillay and R.A. Shore).  Prospects for mathematical logic in the twenty-first century. Journal of Symbolic Logic 7 (2001) 169-196.
  14. (with B. Kapron). Resource-bounded continuity and sequentiality for type-two functionals, ACM Transactions on Computational Logic 3 (2002) 402-417.    Extended abstract appeared in Proceedings, 15th IEEE Symposium on Logic in Computer Science (LICS), 2000, pp. 77-83.  
  15. (with Arnold Beckmann and Chris Pollett). Ordinal notations and well-orderings in bounded arithmetic, Annals of Pure and Applied Logic 120 (2002) 197-223. Publisher's erratum: Annals of Pure and Applied Logic 123 (2003) 291.
  16. (with Pavel Pudlák). On the computational content of intuitionistic propositional proofs, Annals of Pure and Applied Logic 109 (2001) 49-64.
  17. (with Grigori Rosu). Incompleteness of behavioral logics,  Proceedings, Coalgebraic Methods in Computer Science, CMCS'2000, Electronic Notes in Theoretical Computer Science 33 (2000) 61-69.
  18. (with Peter Yianilos). Linear and O(n log n) time minimum-cost matching algorithms for quasiconvex tours, SIAM Journal on Computing 27 (1998) 170-201.  Expanded version of a paper with appeared in Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994, pp. 65-76.  See also associated software and technical report.
  19. (with D. Grigoriev, R. Impagliazzo and T. Pitassi). Linear gaps between degrees for the polynomial calculus modulo distinct primes, Journal of Computer and System Sciences 62 (2001) 267-289.   Earlier version in Proceedings, 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 547-556.  One page abstract in 14th IEEE Conference on Computational Complexity (CCC'99) p. 5-5.
  20. (with Jay Fillmore) Spherical Averages and Applications to Spherical Splines and Interpolation. ACM Transactions on Graphics 20 (2001) 95-126.  Source code for a C++ implementation available too.
  21. (with Grigori Mints) The Complexity of the Disjunction and Existence Properties in Intuitionistic Logic, Annals of Pure and Applied Logic 99 (1999) 93-104.
  22. Propositional Proof Complexity: An Introduction, in Computational Logic, edited by U. Berger and H. Schwichtenberg, Springer-Verlag, Berlin, 1999, pp. 127-178.
  23. An introduction to proof theory, in Handbook of Proof Theory, edited by S. Buss, Elsevier North-Holland, 1998, pp 1-78.
  24. First-order proof theory of arithmetic, in Handbook of Proof Theory, edited by S. Buss, Elsevier North-Holland, 1998, pp 79-147.
  25. (with M. Alekhnovich, S. Moran and T. Pitassi) Minimum Propositional Proof Length is NP-Hard to Linearly Approximate, Journal of Symbolic Logic 66 (2001) 171-191.  An extended abstract appeared earlier in Mathematical Foundations of Computer Science (MFCS'98), Lecture Notes in Computer Science #1450, Springer-Verlag, 1998, pp. 176-184.
  26. Bounded arithmetic, proof complexity and two papers of Parikh, Annals of Pure and Applied Logic 96 (1999) 43-55.
  27. Alogtime algorithms for tree isomorphism, comparison and canonization, In Computational Logic and Proof Theory, Proceedings 5th Gödel Colloquium '97.   Lecture Notes in Computer Science #1289, Springer-Verlag, Berlin, 1997, pp. 18-33.
  28. (with Toniann Pitassi) Resolution and the weak pigeonhole principle, Proceedings, Computer Science Logic (CSL'97), Lecture Notes in Computer Science #1414, Springer-Verlag, 1998, pp.149-156.
  29. Bounded arithmetic and propositional proof complexity, in Logic of Computation, edited by H. Schwichtenberg, Springer-Verlag, Berlin, 1997, pp. 67-122.
  30. Lower bounds on Nullstellensatz proofs via designs, in Proof Complexity and Feasible Arithmetics, edited by S. Buss and P. Beame, American Mathematical Society, Providence, RI, 1998, pp. 59-71.
  31. Bounded arithmetic, cryptography and complexity, Theoria 63 (1997)147-167.
  32. (with Peter Clote) Cutting planes, connectivity and threshold logic, Archive for Mathematical Logic 35 (1996) 33-62.
  33. (with R. Impagliazzo, J. Krajicek, P. Pudlak, A. Razborov and J. Sgall)  Proof Complexity in Algebraic Systems and Constant Depth Frege Systems with Modular Counting, Computational Complexity 6 (1995/1996) 256-298.
  34. (with Toniann Pitassi) Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle, Journal of Computer and System Sciences 57 (1998) 162-171. Earlier version appeared in Complexity '96, Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, 1996, pp 233-242.
  35. (with Aleksandar Ignjatovic) Unprovability of Consistency Statements in Fragments of Bounded Arithmetic, Annals of Pure and Applied Logic 74 (1995) 221-244.
  36. On Herbrand's Theorem, In Logic and Computational Complexity, Lecture Notes in Computer Science #960, 1995, Springer-Verlag, pp. 195-209.
  37. (with Pavel Pudlák)  How To Lie Without Being (Easily) Convicted and Lengths of Proofs in Propositional Calculus. In Eighth Workshop on Computer Science Logic (CSL'94), Lecture Notes in Computer Science #933, Springer-Verlag, 1995, pp. 151-162.
  38. (with Maria Luisa Bonet and Toniann Pitassi)   Are There Hard Examples for Frege Systems?.  In Feasible Mathematics II, Birkhauser, 1995, pp. 31-56.
  39. Relating the Bounded Arithmetic and Polynomial-Time Hierarchies, Annals of Pure and Applied Logic, 75 (1995) 67-77.
  40. (with Maria Luisa Bonet)  Size-Depth Tradeoff for Boolean Formulae.   Information Processing Letters, 11 (1994) 151-155.
  41. Some remarks on the lengths of propositional proofs. Archive for Mathematical Logic 34 (1995) 377-394.
  42. On Gödel's theorems on lengths of proofs I: Number of lines and speedups for arithmetic. Journal of Symbolic Logic 39 (1994) 737-756.
  43. On Gödel's theorems on lengths of proofs II: Lower bounds for recognizing k symbol provability. In Feasible Mathematics II, P. Clote and J. Remmel (eds), Birkhauser, 1995, pp. 57-90.
  44. (with Maria Luisa Bonet)   On the serial transitive closure problem.  SIAM Journal on Computing 24 (1995) 109-122.  See also next two items.
  45. (with Maria Luisa Bonet)  The deduction rule and linear and near-linear proof simulations. Journal of Symbolic Logic 58 (1993) 688-709.   See also previous item and next item.
  46. (with Maria Luisa Bonet)  On the deduction rule and the number of proof lines.  In Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science. (LICS'91).  IEEE Computer Society Press, 1991, pp. 286-297.  Subsumed by the previous two journal articles.
  47. The witness function method and provably recursive functions of Peano arithmetic.   In Proceedings of Ninth International Congress on Logic, Methodology and Philosophy of Science, D. Prawitz, B. Skyrms and D. Westerstahl (eds), Elsevier Science North-Holland, 1994, pp. 29-68.
  48. Algorithms for Boolean formula evaluation and for tree-contraction.   In Proof Theory, Complexity, and Arithmetic, P. Clote and J. Krajicek (eds), Oxford University Press, 1993, pp. 95-115.
  49. (with Jan Krajicek)  An application of Boolean complexity to separation problems in bounded arithmetic.  Proceedings of the London Mathematical Society 69 (1994) 1-21.
  50. (with Jan Krajicek and Gaisi Takeuti).  Provably total functions in the bounded arithmetic theories Ri3, Ui2, and Vi2.  In Proof Theory, Arithmetic, and Complexity, P. Clote and J. Krajicek (eds), Oxford University Press, 1993, pp. 116-161.
  51. The graph of multiplication is equivalent to counting.  Information Processing Letters 41 (1992) 199-201.
  52. (with Christos Papadimitriou and John Tsitsiklis).  On the predictability of coupled automata: an allegory about chaos.  Complex Systems 5 (1991) 525-539.  Earlier draft appeared in Proceedings of the 31st Annual Symposium on Foundations of Computer Science, volume II (FOCS' 1990), IEEE Computer Society Press, 1990, pp. 788-793.
  53. Intuitionistic validity in T-normal Kripke structures.  Annals of Pure and Applied Logic 59 (1993) 159-173.
  54. On model theory for intuitionstic bounded arithmetic with applications to independence.  In Feasible Mathematics: A Mathematical Sciences Institute Workshop held in Ithaca, New York, June 1989.  S. Buss and P. Scott (eds).   Birkhauser,  1990, pp. 27-47.
  55. A note on bootstrapping intuitionistic bounded arithmetic.   In Proof Theory: a selection of papers from the Leeds Theory Programme 1990.   P. Aczel, H. Simmons, S. Wainer (eds).  Cambridge University Press, 1992, pp. 142-169.
  56. Propositional consistency proofs.  Annals of Pure and Applied Logic 52 (1991) 3-29.
  57. The undecidability of k-provability.  Annals of Pure and Applied Logic 53 (1991) 75-102
  58. (with Louise Hay).   On truth-table reducibility to SAT.  Information and Computation 91 (1991) 86-102.
  59. (with Louise Hay.) On truth-table reducibility to SAT and the difference hierarchy over NP."  In Proceedings of the the IEEE Structure in Complexity Conference, IEEE Computer Society Press, 1988, pp. 224-233.
  60. The modal logic of pure provability. Notre Dame Journal of Formal Logic 31 (1990) 225-231.
  61. (with Stephen A. Cook and Arvind Gupta and Vijaya Ramachandran).  An optimal parallel algorithm for formula evaluation. SIAM Journal on Computing 21 (1992 755-780.
  62. (with Gyorgy Turan).  Resolution proofs of generalized pigeonhole principles.  Theoretical Computer Science 62 (1988) 311-317.
  63. Axiomatizations and conservation results for fragments of bounded arithmetic.   In Logic and Computation, Proceedings of a Workshop held at Carnegie Mellon University, June 30-July 2, 1987. AMS Contemporary Mathematics 106 (1990) 57-84.
  64. The Boolean formula value problem is in ALOGTIME.  In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), 1987, pp. 123-131.
  65. Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic 52 (1987) 916-927.
  66. The polynomial hierarchy and intuitionistic Bounded Arithmetic.   In  Structure in Complexity, Lecture Notes in Computer Science #223, Springer Verlag, 1986, pp. 77-103.
  67. A conservation result concerning bounded theories and the collection axiom.  Proceedings of the American Mathematic Society 100 (1987) 709-716.
  68. The polynomial hierarchy and fragments of bounded arithmetic.  In Proceedings of the 17-th Annual ACM Symposium on Theory of Computing (STOC'85), 1985, pp. 285-290.
  69. (with P.N. Yianilos and R.A. Harbort),  The application of a pattern matching algorithm to searching medical record text.  In IEEE Symposium on Computer Applications in Medical Care, 1978, pp. 308-313.

 

Ph.D./Honors theses:

  1. Samuel R. Buss, Bounded Arithmetic, Ph.D. thesis, Department of Mathematics, Princeton University, 1985. 188+v pages.
  2. Samuel R. Buss, The Word Problem for Groups, Undergraduate Honors Thesis, Department of Mathematics, Emory University, 1979,  79 pages.

 

Reviews, unpublished articles, unpublished surveys, course lecture notes, and miscellaneous items.

  1. Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares methods.  Unpublished survey article, 2004.
  2. (with R. Iemhoff).  The Depth of Intuitionistic Cut Free Proofs.  Unpublished manuscript 2003.
  3. Student-written notes of my Math 267 - Propositional Proof Complexity course in Winter 2002.
  4. (with P. Yianilos).  A Bipartite Matching Approach to Approximate String Comparison and Seach. Unpublished manuscript.
  5. (with P. Yianilos). Secure Short-Key Cryptosystems: Forty Bits is Enough.   Unpublished manuscript.
  6. Lectures on Proof Theory, Technical Report number SOCS-96.1, School of Computer Science, McGill University, 1996, 117 pages.
  7. A review of the biography of K. Godel, Logical Dilemmas, by John Dawson.  SIAM Review 40 (1998) 397-400.
  8. Student-written notes of my Math 267 - Mathematical Foundations of Cryptography course in Winter 1997.
  9. (with Peter Clote).  Threshold logic proof systems.  Unpublished manuscript.  May 1995.
  10. (with D. Robinson, K. Kanzelberg, P. Yianilos).  Solving the Minimum-Cost Matching Principle for Quasi-Convex Tours: An Efficient ANSI C Implementation. Technical report #370, Dept. of Computer Science Engineering, UCSD, April 1994, 69 pages.  Associated software and journal article also available.
  11. A review of Exponential lower bounds for the pigeonhole principle by P. Beame, R. Impagliazzo, J Krajícek, T. Pitassi, P. Pudlák and A. Woods, in Computing Reviews 34 (May 1993) 261-261.   Reprinted in SIGACT News 24 (1993) 41-41.
  12. Student-written notes of my Math 267 - Circuit Complexity course in Winter-Spring 1992.
  13. A review of three papers of Neil Immerman, Journal of Symbolic Logic 54 (1989) 287-288.
  14. (with S.A. Cook, P.W. Dymond and L. Hay), The log space oracle hierarchy collapses.   Technical report #CS87-103,  Computer Science Engineering Department, Univ. of California, San Diego, 1987.
  15. Student-written notes for Math 260A-C on Introduction to Mathematical Logic, Fall 1988-Spring 1989.
  16. Student-written notes of my Math 271 (Berkeley) topics course on Weak Formal Systems and Connections to Computational Complexity, Winter-Spring 1988.
  17. Neighborhood metrics on n-dimension blocks of characters.  Technical report #00218-86, Mathematical Sciences Research Institute, Berkeley, California, September 1985. 

 

Some selected recent talks with computer generated slides. 

  1. Large Numbers, Busy Beavers, Noncomputability and Incompleteness, Food for Thought seminar, UCSD, November 2007.
  2. The Computational Power of Bounded Arithmetic from the Predicative Viewpoint, ASL Winter Meeting, special session. January 2007.
  3. Propositional Proof Systems and Search, Connections II: Fundamentals of Network Science, Caltech, August 2006.
  4. Proof Complexity and Computational Hardness, Computability in Europe (CiE), July 2006, Swansea, Wales.  Three tutotial lectures.
  5. Bounded Arithmetic, Constant-Depth Proofs and st-Connectivity.  UCLA Logic Meeting (VIG), February 2004.  Contains st-Connectivity and Hex tautology work.
  6. Ed Nelson's Work on Logic and Foundations: Radical Constructivism.  Presentation at Workshop on Analysis, Probability and Logic, Pacific Institute of Mathematical Studies, UBC, Vancouver, June 2004.  A related paper is also available.
  7. Is it easier to "Discover" than to "Verify"?  UCSD Math Circle presentation to high school students, May 22, 2004.
  8. Bounded arithmetic and bounded depth propositional proofs. Takeuti Symposium on Mathematical Logic, Kobe, Japan, December, 2003.
  9. Polynomial-size Frege and Resolution Proofs of st-Connectivity and Hex Tautologies.  Workshop on Proof Theory, Muenster, October 2003; and 12th Latin American Symposium on Mathematical Logic (SLALM), Costa Rica, January 2004.
  10. Spherical Splines and Applications to Spherical Splines and Interpolation.  Pixel Cafe, UCSD, December 2002.
  11. Taylor series methods for rigid body simulation and extensions to Lie groups.  Seventh SIAM Conference on Geometric Design and Computing. Sacramento, November 2001. 
  12. Bounded arithmetic and propositional proofs.  NATO International Summer School on Logic of Computation.  Marktoberdorf, Germany.   July-August 1995.  Five hours of lectures.

Acknowledgement: The bulk of the above work on this page was performed with partial financial support under various NSF grants.  Some parts of the work were funded in part by grants from the Czech Academy of Sciences.

Other: Computer games with algorithms or code by Buss are listed at http://www.mobygames.com/developer/sheet/view/developerId,42330/.