| 2009 |
|---|
| 53 | EE | Samuel R. Buss,
Roman Kuznets:
The NP-Completeness of Reflected Fragments of Justification Logics.
LFCS 2009: 122-136 |
| 2008 |
|---|
| 52 | EE | Samuel R. Buss,
Jan Hoffmann,
Jan Johannsen:
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
CoRR abs/0811.1075: (2008) |
| 51 | EE | Samuel R. Buss,
Jan Hoffmann:
The NP-hardness of finding a directed acyclic graph for regular resolution.
Theor. Comput. Sci. 396(1-3): 271-276 (2008) |
| 2006 |
|---|
| 50 | EE | Samuel R. Buss:
Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies.
Theor. Comput. Sci. 357(1-3): 35-52 (2006) |
| 2005 |
|---|
| 49 | EE | Arnold Beckmann,
Samuel R. Buss:
Separation results for the size of constant-depth propositional proofs.
Ann. Pure Appl. Logic 136(1-2): 30-55 (2005) |
| 48 | EE | Samuel R. Buss:
Collision detection with relative screw motion.
The Visual Computer 21(1-2): 41-58 (2005) |
| 2004 |
|---|
| 47 | EE | Nathan Segerlind,
Samuel R. Buss,
Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.
SIAM J. Comput. 33(5): 1171-1200 (2004) |
| 2003 |
|---|
| 46 | | Arnold Beckmann,
Chris Pollett,
Samuel R. Buss:
Ordinal notations and well-orderings in bounded arithmetic.
Ann. Pure Appl. Logic 120(1-3): 197-223 (2003) |
| 45 | EE | Arnold Beckmann,
Samuel R. Buss,
Chris Pollett:
Erratum to "Ordinal notations and well-orderings in bounded arithmetic" [Annals of Pure and Applied Logic 120 (2003) 197-223].
Ann. Pure Appl. Logic 123(1-3): 291- (2003) |
| 2002 |
|---|
| 44 | EE | Nathan Segerlind,
Samuel R. Buss,
Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
FOCS 2002: 604- |
| 43 | EE | Samuel R. Buss,
Bruce M. Kapron:
Resource-bounded continuity and sequentiality for type-two functionals.
ACM Trans. Comput. Log. 3(3): 402-417 (2002) |
| 42 | EE | Samuel R. Buss,
Alexander S. Kechris,
Anand Pillay,
Richard A. Shore:
The prospects for mathematical logic in the twenty-first century
CoRR cs.LO/0205003: (2002) |
| 2001 |
|---|
| 41 | EE | Samuel R. Buss,
Jay P. Fillmore:
Spherical averages and applications to spherical splines and interpolation.
ACM Trans. Graph. 20(2): 95-126 (2001) |
| 40 | | Samuel R. Buss,
Pavel Pudlák:
On the computational content of intuitionistic propositional proofs.
Ann. Pure Appl. Logic 109(1-2): 49-63 (2001) |
| 39 | EE | Samuel R. Buss,
Alexander S. Kechris,
Anand Pillay,
Richard A. Shore:
The prospects for mathematical logic in the twenty-first century.
Bulletin of Symbolic Logic 7(2): 169-196 (2001) |
| 38 | | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.
J. Comput. Syst. Sci. 62(2): 267-289 (2001) |
| 37 | | Michael Alekhnovich,
Samuel R. Buss,
Shlomo Moran,
Toniann Pitassi:
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log. 66(1): 171-191 (2001) |
| 2000 |
|---|
| 36 | EE | Samuel R. Buss,
Bruce M. Kapron:
Resource-Bounded Continuity and Sequentiality for Type-Two Functionals.
LICS 2000: 77-83 |
| 35 | EE | Samuel R. Buss,
Grigore Rosu:
Incompleteness of Behavioral Logics.
Electr. Notes Theor. Comput. Sci. 33: (2000) |
| 1999 |
|---|
| 34 | EE | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).
IEEE Conference on Computational Complexity 1999: 5 |
| 33 | EE | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
STOC 1999: 547-556 |
| 32 | | Samuel R. Buss:
Bounded Arithmetic, Proof Complexity and Two Papers of Parikh.
Ann. Pure Appl. Logic 96(1-3): 43-55 (1999) |
| 31 | | Samuel R. Buss,
Grigori Mints:
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic.
Ann. Pure Appl. Logic 99(1-3): 93-104 (1999) |
| 1998 |
|---|
| 30 | EE | Michael Alekhnovich,
Samuel R. Buss,
Shlomo Moran,
Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.
MFCS 1998: 176-184 |
| 29 | | Samuel R. Buss,
Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
J. Comput. Syst. Sci. 57(2): 162-171 (1998) |
| 28 | | Samuel R. Buss,
Peter N. Yianilos:
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
SIAM J. Comput. 27(1): 170-201 (1998) |
| 1997 |
|---|
| 27 | | Samuel R. Buss,
Toniann Pitassi:
Resolution and the Weak Pigeonhole Principle.
CSL 1997: 149-156 |
| 26 | | Samuel R. Buss:
Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization.
Kurt Gödel Colloquium 1997: 18-33 |
| 25 | | Samuel R. Buss,
Russell Impagliazzo,
Jan Krajícek,
Pavel Pudlák,
Alexander A. Razborov,
Jiri Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Computational Complexity 6(3): 256-298 (1997) |
| 1996 |
|---|
| 24 | EE | Samuel R. Buss,
Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
IEEE Conference on Computational Complexity 1996: 233-242 |
| 1995 |
|---|
| 23 | | Samuel R. Buss,
Aleksandar Ignjatovic:
Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.
Ann. Pure Appl. Logic 74(3): 221-244 (1995) |
| 22 | | Samuel R. Buss:
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.
Ann. Pure Appl. Logic 75(1-2): 67-77 (1995) |
| 21 | | Maria Luisa Bonet,
Samuel R. Buss:
The Serial Transitive Closure Problem for Trees.
SIAM J. Comput. 24(1): 109-122 (1995) |
| 1994 |
|---|
| 20 | | Pavel Pudlák,
Samuel R. Buss:
How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus.
CSL 1994: 151-162 |
| 19 | | Samuel R. Buss:
On Herbrand's Theorem.
LCC 1994: 195-209 |
| 18 | | Samuel R. Buss,
Peter N. Yianilos:
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
SODA 1994: 65-76 |
| 17 | | Maria Luisa Bonet,
Samuel R. Buss:
Size-Depth Tradeoffs for Boolean Fomulae.
Inf. Process. Lett. 49(3): 151-155 (1994) |
| 16 | | Samuel R. Buss:
On Gödel's Theorems on Lenghts of Proofs I: Number of Lines and Speedup for Arithmetics.
J. Symb. Log. 59(3): 737-756 (1994) |
| 1993 |
|---|
| 15 | | Samuel R. Buss:
Intuitionistic Validity in T-Normal Kripke Structures.
Ann. Pure Appl. Logic 59(3): 159-173 (1993) |
| 14 | | Maria Luisa Bonet,
Samuel R. Buss:
The Deduction Rule and Linear and Near-Linear Proof Simulations.
J. Symb. Log. 58(2): 688-709 (1993) |
| 1992 |
|---|
| 13 | | Samuel R. Buss:
The Graph of Multiplication is Equivalent to Counting.
Inf. Process. Lett. 41(4): 199-201 (1992) |
| 12 | | Samuel R. Buss,
S. Cook,
A. Gupta,
V. Ramachandran:
An Optimal Parallel Algorithm for Formula Evaluation.
SIAM J. Comput. 21(4): 755-780 (1992) |
| 1991 |
|---|
| 11 | | Maria Luisa Bonet,
Samuel R. Buss:
On the Deduction Rule and the Number of Proof Lines
LICS 1991: 286-297 |
| 10 | | Samuel R. Buss:
Propositional Consistency Proofs.
Ann. Pure Appl. Logic 52(1-2): 3-29 (1991) |
| 9 | | Samuel R. Buss:
The Undecidability of k-Provability.
Ann. Pure Appl. Logic 53(1): 75-102 (1991) |
| 8 | | Samuel R. Buss,
Louise Hay:
On Truth-Table Reducibility to SAT
Inf. Comput. 91(1): 86-102 (1991) |
| 1990 |
|---|
| 7 | | Samuel R. Buss,
Christos H. Papadimitriou,
John N. Tsitsiklis:
On the Predictability of Coupled Automata: An Allegory about Chaos
FOCS 1990: 788-793 |
| 6 | | Samuel R. Buss:
The Modal Logic of Pure Provability.
Notre Dame Journal of Formal Logic 31(2): 225-231 (1990) |
| 1988 |
|---|
| 5 | | Samuel R. Buss,
György Turán:
Resolution Proofs of Generalized Pigeonhole Principles.
Theor. Comput. Sci. 62(3): 311-317 (1988) |
| 1987 |
|---|
| 4 | | Samuel R. Buss:
The Boolean Formula Value Problem Is in ALOGTIME
STOC 1987: 123-131 |
| 3 | | Samuel R. Buss:
Polynomial Size Proofs of the Propositional Pigeonhole Principle.
J. Symb. Log. 52(4): 916-927 (1987) |
| 1986 |
|---|
| 2 | | Samuel R. Buss:
The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.
Structure in Complexity Theory Conference 1986: 77-103 |
| 1985 |
|---|
| 1 | | Samuel R. Buss:
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract)
STOC 1985: 285-290 |
