| Year |
Citation |
Score |
| 2020 |
Buss S, Kabanets V, Kolokolova A, Koucký M. Expander construction in VNC1 Annals of Pure and Applied Logic. 171: 102796. DOI: 10.1016/J.Apal.2020.102796 |
0.406 |
|
| 2019 |
Beckmann A, Buss S. On transformations of constant depth propositional proofs Annals of Pure and Applied Logic. 170: 1176-1187. DOI: 10.1016/J.Apal.2019.05.002 |
0.365 |
|
| 2018 |
Buss S, Itsykson D, Knop A, Sokolov D. Reordering rule makes OBDD proof systems stronger Electronic Colloquium On Computational Complexity. 25: 41. DOI: 10.4230/Lipics.Ccc.2018.16 |
0.377 |
|
| 2018 |
Aisenberg J, Bonet ML, Buss S, Crăciun A, Istrate G. Short proofs of the Kneser-Lovasz coloring principle Information & Computation. 261: 296-310. DOI: 10.1016/J.Ic.2018.02.010 |
0.4 |
|
| 2017 |
Beckmann A, Buss S. The NP Search Problems of Frege and Extended Frege Proofs Acm Transactions On Computational Logic. 18: 11. DOI: 10.1145/3060145 |
0.353 |
|
| 2017 |
Buss S. Uniform proofs of ACC representations Archive For Mathematical Logic. 56: 639-669. DOI: 10.1007/S00153-017-0560-9 |
0.399 |
|
| 2016 |
Aisenberg J, Bonet ML, Buss S. Quasipolynomial size frege proofs of Frankl’s Theorem on the trace of sets Journal of Symbolic Logic. 81: 687-710. DOI: 10.1017/Jsl.2015.17 |
0.395 |
|
| 2016 |
Beckmann A, Buss S, Friedman SD, Müller M, Thapen N. Cobham recursive set functions Annals of Pure and Applied Logic. 167: 335-369. DOI: 10.1016/J.Apal.2015.12.005 |
0.39 |
|
| 2015 |
Buss SR, Kołodziejczyk LA, Zdanowski K. Collapsing modular counting in bounded arithmetic and constant depth propositional proofs Transactions of the American Mathematical Society. 367: 7517-7563. DOI: 10.1090/S0002-9947-2015-06233-3 |
0.427 |
|
| 2015 |
Beckmann A, Buss SR, Friedman SD. Safe recursive set functions Journal of Symbolic Logic. 80: 730-762. DOI: 10.1017/Jsl.2015.26 |
0.367 |
|
| 2015 |
Buss S. Quasipolynomial size proofs of the propositional pigeonhole principle Theoretical Computer Science. 576: 77-84. DOI: 10.1016/J.Tcs.2015.02.005 |
0.393 |
|
| 2015 |
Buss SR, Williams R. Limits on Alternation Trading Proofs for Time–Space Lower Bounds Computational Complexity. DOI: 10.1007/S00037-015-0104-9 |
0.336 |
|
| 2014 |
Buss S, Cenzer D, Remmel JB. Sub-computable bounded randomness Logical Methods in Computer Science. 10. DOI: 10.2168/Lmcs-10(4:15)2014 |
0.402 |
|
| 2014 |
Buss SR, Kołodziejczyk LA. Small stone in pool Logical Methods in Computer Science. 10. DOI: 10.2168/Lmcs-10(2:16)2014 |
0.337 |
|
| 2014 |
Bonet ML, Buss S, Johannsen J. Improved separations of regular resolution from clause learning proof systems Journal of Artificial Intelligence Research. 49: 669-703. DOI: 10.1613/Jair.4260 |
0.326 |
|
| 2014 |
Beckmann A, Buss SR. Improved witnessing and local improvement principles for second-order bounded arithmetic Acm Transactions On Computational Logic. 15. DOI: 10.1145/2559950 |
0.396 |
|
| 2014 |
Buss SR, Kołodziejczyk LA, Thapen N. Fragments of approximate counting Journal of Symbolic Logic. 79: 496-525. DOI: 10.1017/Jsl.2013.37 |
0.4 |
|
| 2014 |
Buss S, Soltys M. Unshuffling a square is NP-hard Journal of Computer and System Sciences. 80: 766-776. DOI: 10.1016/J.Jcss.2013.11.002 |
0.376 |
|
| 2013 |
Buss S, Minnes M. Probabilistic algorithmic randomness Journal of Symbolic Logic. 78: 579-601. DOI: 10.2178/Jsl.7802130 |
0.316 |
|
| 2012 |
Buss SR. Sharpened lower bounds for cut elimination Journal of Symbolic Logic. 77: 656-668. DOI: 10.2178/Jsl/1333566644 |
0.399 |
|
| 2012 |
Buss SR, Johnson AS. Propositional proofs and reductions between NP search problems Annals of Pure and Applied Logic. 163: 1163-1182. DOI: 10.1016/J.Apal.2012.01.015 |
0.386 |
|
| 2012 |
Buss SR, Kuznets R. Lower complexity bounds in justification logic Annals of Pure and Applied Logic. 163: 888-905. DOI: 10.1016/J.Apal.2011.09.010 |
0.402 |
|
| 2012 |
Buss SR. Towards NP-P via proof complexity and search Annals of Pure and Applied Logic. 163: 906-917. DOI: 10.1016/J.Apal.2011.09.009 |
0.317 |
|
| 2011 |
Buss S, Chen Y, Flum J, Friedman SD, Müller M. Strong isomorphism reductions in complexity theory Journal of Symbolic Logic. 76: 1381-1402. DOI: 10.2178/Jsl/1318338855 |
0.39 |
|
| 2011 |
Beckmann A, Buss SR. Corrected upper bounds for free-cut elimination Theoretical Computer Science. 412: 5433-5445. DOI: 10.1016/J.Tcs.2011.05.053 |
0.39 |
|
| 2010 |
Buss SR, Johnson AS. The quantifier complexity of polynomial-size iterated definitions in first-order logic Mathematical Logic Quarterly. 56: 573-590. DOI: 10.1002/Malq.200910111 |
0.419 |
|
| 2009 |
Beckmann A, Buss SR. Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic Journal of Mathematical Logic. 9: 103-138. DOI: 10.1142/S0219061309000847 |
0.411 |
|
| 2009 |
Buss SR. Pool resolution is NP-hard to recognize Archive For Mathematical Logic. 48: 793-798. DOI: 10.1007/S00153-009-0152-4 |
0.314 |
|
| 2008 |
Buss SR, Kohlenbach U, Rathjen M. Mathematical Logic: Proof Theory, Constructive Mathematics Oberwolfach Reports. 8: 2963-3002. DOI: 10.4171/Owr/2008/18 |
0.354 |
|
| 2006 |
Buss SR. Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies Theoretical Computer Science. 357: 35-52. DOI: 10.1016/J.Tcs.2006.03.011 |
0.411 |
|
| 2005 |
Buss SR, Keilis-Borok V, Schwichtenberg H. Mathematical Logic: Proof Theory, Type Theory and Constructive Mathematics Oberwolfach Reports. 2: 779-813. DOI: 10.4171/Owr/2005/14 |
0.317 |
|
| 2004 |
Buss SR, Clote P. Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis Advances in Applied Probability. 36: 1175-1197. DOI: 10.1239/Aap/1103662962 |
0.303 |
|
| 2003 |
Beckmann A, Buss SR, Pollett C. Erratum to “Ordinal notations and well-orderings in bounded arithmetic” [Annals of Pure and Applied Logic 120 (2003) 197–223] Annals of Pure and Applied Logic. 123: 291. DOI: 10.1016/S0168-0072(03)00039-3 |
0.363 |
|
| 2003 |
Beckmann A, Pollett C, Buss SR. Ordinal notations and well-orderings in bounded arithmetic Annals of Pure and Applied Logic. 120: 197-223. DOI: 10.1016/S0168-0072(02)00066-0 |
0.381 |
|
| 2002 |
Razborov A, Alekhnovich M, Buss S, Moran S, Pitassi T. Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate The Bulletin of Symbolic Logic. 8: 301. DOI: 10.2307/2693969 |
0.3 |
|
| 2002 |
Buss SR, Kapron BM. Resource-bounded continuity and sequentiality for type-two functionals Acm Transactions On Computational Logic. 3: 402-417. DOI: 10.1145/507382.507387 |
0.317 |
|
| 2002 |
Segerlind N, Buss S, Impagliazzo R. A switching lemma for small restrictions and lower bounds for k-DNF resolution Annual Symposium On Foundations of Computer Science - Proceedings. 604-613. DOI: 10.1137/S0097539703428555 |
0.3 |
|
| 2001 |
Alekhnovich M, Buss SR, Moran S, Pitassi T. Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate Journal of Symbolic Logic. 66: 171-191. DOI: 10.2307/2694916 |
0.408 |
|
| 2001 |
Buss SR, Kechris AS, Pillay A, Shore RA. The Prospects for Mathematical Logic in the Twenty-First Century The Bulletin of Symbolic Logic. 7: 169-196. DOI: 10.2307/2687773 |
0.329 |
|
| 2001 |
Buss SR, Fillmore JP. Spherical averages and applications to spherical splines and interpolation Acm Transactions On Graphics. 20: 96-126. DOI: 10.1145/502122.502124 |
0.318 |
|
| 2001 |
Buss SR, Pudlák P. On the computational content of intuitionistic propositional proofs Annals of Pure and Applied Logic. 109: 49-64. DOI: 10.1016/S0168-0072(01)00040-9 |
0.445 |
|
| 1999 |
Buss S, Mints G. The complexity of the disjunction and existential properties in intuitionistic logic Annals of Pure and Applied Logic. 99: 93-104. DOI: 10.1016/S0168-0072(99)00002-0 |
0.38 |
|
| 1999 |
Buss SR. Bounded arithmetic, proof complexity and two papers of Parikh Annals of Pure and Applied Logic. 96: 43-55. DOI: 10.1016/S0168-0072(98)00030-X |
0.332 |
|
| 1998 |
Buss SR, Yianilos PN. Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours Siam Journal On Computing. 27: 170-201. DOI: 10.1137/S0097539794267243 |
0.336 |
|
| 1998 |
Buss SR, Pitassi T. Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle Journal of Computer and System Sciences. 57: 162-171. DOI: 10.1006/Jcss.1998.1585 |
0.356 |
|
| 1996 |
Buss SR, Clote P. Cutting planes, connectivity, and threshold logic Archive For Mathematical Logic. 35: 33-62. DOI: 10.1007/Bf01845704 |
0.364 |
|
| 1996 |
Buss SR, Krajíček J, Pudlák P, Sgall J, Impagliazzo R, Razborov AA. Proof complexity in algebraic systems and bounded depth frege systems with modular counting Computational Complexity. 6: 256-298. DOI: 10.1007/Bf01294258 |
0.42 |
|
| 1995 |
Bonet ML, Buss SR. The Serial Transitive Closure Problem for Trees Siam Journal On Computing. 24: 109-122. DOI: 10.1137/S0097539792225303 |
0.332 |
|
| 1995 |
Buss SR. The witness function method and provably recursive functions of peano arithmetic Studies in Logic and the Foundations of Mathematics. 134: 29-68. DOI: 10.1016/S0049-237X(06)80038-8 |
0.308 |
|
| 1995 |
Buss SR. Relating the bounded arithmetic and polynomial time hierarchies Annals of Pure and Applied Logic. 75: 67-77. DOI: 10.1016/0168-0072(94)00057-A |
0.368 |
|
| 1995 |
Buss SR, Ignjatović A. Unprovability of consistency statements in fragments of bounded arithmetic Annals of Pure and Applied Logic. 74: 221-244. DOI: 10.1016/0168-0072(94)00049-9 |
0.331 |
|
| 1995 |
Buss SR. Some remarks on lengths of propositional proofs Archive For Mathematical Logic. 34: 377-394. DOI: 10.1007/Bf02391554 |
0.393 |
|
| 1994 |
Buss SR. On Go¨del's theorems on lengths of proofs I: number of lines and speedup for arithmetics Journal of Symbolic Logic. 59: 737-756. DOI: 10.2307/2275906 |
0.384 |
|
| 1994 |
Buss SR, Krajíček J. An application of boolean complexity to separation problems in bounded arithmetic Proceedings of the London Mathematical Society. 1-21. DOI: 10.1112/Plms/S3-69.1.1 |
0.304 |
|
| 1994 |
Bonet ML, Buss SR. Size-depth tradeoffs for Boolean formulae Information Processing Letters. 49: 151-155. DOI: 10.1016/0020-0190(94)90093-0 |
0.334 |
|
| 1993 |
Bonet ML, Buss SR. The deduction rule and linear and near-linear proof simulations Journal of Symbolic Logic. 58: 688-709. DOI: 10.2307/2275228 |
0.326 |
|
| 1992 |
Buss S, Cook S, Gupta A, Ramachandran V. An optimal parallel algorithm for formula evaluation Siam Journal On Computing. 21: 755-780. DOI: 10.1137/0221046 |
0.343 |
|
| 1991 |
Buss SR, Hay L. On truth-table reducibility to SAT Information and Computation. 91: 86-102. DOI: 10.1016/0890-5401(91)90075-D |
0.384 |
|
| 1991 |
Buss SR. Propositional consistency proofs Annals of Pure and Applied Logic. 52: 3-29. DOI: 10.1016/0168-0072(91)90036-L |
0.407 |
|
| 1990 |
Buss SR. The modal logic of pure provability Notre Dame Journal of Formal Logic. 31: 225-231. DOI: 10.1305/Ndjfl/1093635417 |
0.335 |
|
| 1989 |
Buss S. Immerman Neil. Upper and lower bounds for first order expressibility. Journal of computer and system sciences, vol. 25 (1982), pp. 76–98.Immerman Neil. Relational queries computable in polynomial time. Information and control, vol. 68 (1986), pp. 86–104.Immerman Neil. Languages that capture complexity classes. SIAM journal on computing, vol. 16 (1987), pp. 760–778. Journal of Symbolic Logic. 54: 287-288. DOI: 10.2307/2275034 |
0.345 |
|
| 1988 |
Buss SR, Turán Ga#. Resolution proofs of generalized pigeonhole principles Theoretical Computer Science. 62: 311-317. DOI: 10.1016/0304-3975(88)90072-2 |
0.359 |
|
| 1987 |
Buss SR. Polynomial Size Proofs of the Propositional Pigeonhole Principle Journal of Symbolic Logic. 52: 916-927. DOI: 10.2307/2273826 |
0.438 |
|
| Show low-probability matches. |