Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Samuel R. Buss
@article{DBLP:journals/corr/abs-2402-15871,
author = {Sam Buss and
Emre Yolcu},
title = {Regular resolution effectively simulates resolution},
journal = {CoRR},
volume = {abs/2402.15871},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.15871},
doi = {10.48550/ARXIV.2402.15871},
eprinttype = {arXiv},
eprint = {2402.15871},
timestamp = {Mon, 25 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-15871.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BonacinaBBL24,
author = {Ilario Bonacina and
Maria Luisa Bonet and
Sam Buss and
Massimo Lauria},
title = {Redundancy for MaxSAT},
journal = {Electron. Colloquium Comput. Complex.},
pages = {TR24--045},
year = {2024},
url = {https://eccc.weizmann.ac.il/report/2024/045},
timestamp = {Tue, 02 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BonacinaBBL24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussT24,
author = {Sam Buss and
Neil Thapen},
title = {A Simple Supercritical Tradeoff between Size and Height in Resolution},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR24-001}},
year = {2024},
url = {https://eccc.weizmann.ac.il/report/2024/001},
eprinttype = {ECCC},
eprint = {TR24-001},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BussT24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussY24,
author = {Sam Buss and
Emre Yolcu},
title = {Regular resolution effectively simulates resolution},
journal = {Electron. Colloquium Comput. Complex.},
pages = {TR24--033},
year = {2024},
url = {https://eccc.weizmann.ac.il/report/2024/033},
timestamp = {Tue, 05 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BussY24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BussFI23,
author = {Sam Buss and
Noah Fleming and
Russell Impagliazzo},
editor = {Yael Tauman Kalai},
title = {{TFNP} Characterizations of Proof Systems and Monotone Circuits},
booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
series = {LIPIcs},
volume = {251},
pages = {30:1--30:40},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.30},
doi = {10.4230/LIPICS.ITCS.2023.30},
timestamp = {Thu, 02 Feb 2023 12:50:42 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BussFI23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AtseriasBM23,
author = {Albert Atserias and
Sam Buss and
Moritz M{\"{u}}ller},
editor = {Barna Saha and
Rocco A. Servedio},
title = {On the Consistency of Circuit Lower Bounds for Non-deterministic Time},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {1257--1270},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585253},
doi = {10.1145/3564246.3585253},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/AtseriasBM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:books/acm/23/Buss23,
author = {Sam Buss},
editor = {Bruce M. Kapron},
title = {Polynomially Verifiable Arithmetic},
booktitle = {Logic, Automata, and Computational Complexity: The Works of Stephen
A. Cook},
series = {{ACM} Books},
volume = {43},
pages = {95--106},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3588287.3588294},
doi = {10.1145/3588287.3588294},
timestamp = {Thu, 21 Sep 2023 14:31:10 +0200},
biburl = {https://dblp.org/rec/books/acm/23/Buss23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2303-01016,
author = {Albert Atserias and
Sam Buss and
Moritz M{\"{u}}ller},
title = {On the Consistency of Circuit Lower Bounds for Non-Deterministic Time},
journal = {CoRR},
volume = {abs/2303.01016},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2303.01016},
doi = {10.48550/ARXIV.2303.01016},
eprinttype = {arXiv},
eprint = {2303.01016},
timestamp = {Mon, 06 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2303-01016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussFI22,
author = {Sam Buss and
Noah Fleming and
Russell Impagliazzo},
title = {{TFNP} Characterizations of Proof Systems and Monotone Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-141}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/141},
eprinttype = {ECCC},
eprint = {TR22-141},
timestamp = {Fri, 10 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/BussFI22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ai/BonetBIMM21,
author = {Maria Luisa Bonet and
Sam Buss and
Alexey Ignatiev and
Ant{\'{o}}nio Morgado and
Jo{\~{a}}o Marques{-}Silva},
title = {Propositional proof systems based on maximum satisfiability},
journal = {Artif. Intell.},
volume = {300},
pages = {103552},
year = {2021},
url = {https://doi.org/10.1016/j.artint.2021.103552},
doi = {10.1016/J.ARTINT.2021.103552},
timestamp = {Sun, 12 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ai/BonetBIMM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/lmcs/BussT21,
author = {Sam Buss and
Neil Thapen},
title = {{DRAT} and Propagation Redundancy Proofs Without New Variables},
journal = {Log. Methods Comput. Sci.},
volume = {17},
number = {2},
year = {2021},
url = {https://lmcs.episciences.org/7400},
timestamp = {Tue, 01 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/lmcs/BussT21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/BussIKRS21,
author = {Sam Buss and
Dmitry Itsykson and
Alexander Knop and
Artur Riazanov and
Dmitry Sokolov},
title = {Lower Bounds on {OBDD} Proofs with Several Orders},
journal = {{ACM} Trans. Comput. Log.},
volume = {22},
number = {4},
pages = {26:1--26:30},
year = {2021},
url = {https://doi.org/10.1145/3468855},
doi = {10.1145/3468855},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tocl/BussIKRS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:series/faia/BussN21,
author = {Sam Buss and
Jakob Nordstr{\"{o}}m},
editor = {Armin Biere and
Marijn Heule and
Hans van Maaren and
Toby Walsh},
title = {Proof Complexity and {SAT} Solving},
booktitle = {Handbook of Satisfiability - Second Edition},
series = {Frontiers in Artificial Intelligence and Applications},
volume = {336},
pages = {233--350},
publisher = {{IOS} Press},
year = {2021},
url = {https://doi.org/10.3233/FAIA200990},
doi = {10.3233/FAIA200990},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/series/faia/BussN21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussKKK20,
author = {Sam Buss and
Valentine Kabanets and
Antonina Kolokolova and
Michal Kouck{\'{y}}},
title = {Expander construction in VNC\({}^{\mbox{1}}\)},
journal = {Ann. Pure Appl. Log.},
volume = {171},
number = {7},
pages = {102796},
year = {2020},
url = {https://doi.org/10.1016/j.apal.2020.102796},
doi = {10.1016/J.APAL.2020.102796},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussKKK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AisenbergBB20,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss},
title = {2-D Tucker is {PPA} complete},
journal = {J. Comput. Syst. Sci.},
volume = {108},
pages = {92--103},
year = {2020},
url = {https://doi.org/10.1016/j.jcss.2019.09.002},
doi = {10.1016/J.JCSS.2019.09.002},
timestamp = {Thu, 19 Dec 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/AisenbergBB20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csl/Buss0K20,
author = {Sam Buss and
Anupam Das and
Alexander Knop},
editor = {Maribel Fern{\'{a}}ndez and
Anca Muscholl},
title = {Proof Complexity of Systems of (Non-Deterministic) Decision Trees
and Branching Programs},
booktitle = {28th {EACSL} Annual Conference on Computer Science Logic, {CSL} 2020,
January 13-16, 2020, Barcelona, Spain},
series = {LIPIcs},
volume = {152},
pages = {12:1--12:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CSL.2020.12},
doi = {10.4230/LIPICS.CSL.2020.12},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csl/Buss0K20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussIKRS20,
author = {Sam Buss and
Dmitry Itsykson and
Alexander Knop and
Artur Riazanov and
Dmitry Sokolov},
title = {Lower Bounds on {OBDD} Proofs with Several Orders},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-073}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/073},
eprinttype = {ECCC},
eprint = {TR20-073},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BussIKRS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BeckmannB19,
author = {Arnold Beckmann and
Sam Buss},
title = {On transformations of constant depth propositional proofs},
journal = {Ann. Pure Appl. Log.},
volume = {170},
number = {10},
pages = {1176--1187},
year = {2019},
url = {https://doi.org/10.1016/j.apal.2019.05.002},
doi = {10.1016/J.APAL.2019.05.002},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/apal/BeckmannB19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/computability/BeckmannBFMT19,
author = {Arnold Beckmann and
Sam Buss and
Sy{-}David Friedman and
Moritz M{\"{u}}ller and
Neil Thapen},
title = {Feasible set functions have small circuits},
journal = {Comput.},
volume = {8},
number = {1},
pages = {67--98},
year = {2019},
url = {https://doi.org/10.3233/COM-180096},
doi = {10.3233/COM-180096},
timestamp = {Thu, 24 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/computability/BeckmannBFMT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sat/BussT19,
author = {Sam Buss and
Neil Thapen},
editor = {Mikol{\'{a}}s Janota and
In{\^{e}}s Lynce},
title = {{DRAT} Proofs, Propagation Redundancy, and Extended Resolution},
booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2019 - 22nd
International Conference, {SAT} 2019, Lisbon, Portugal, July 9-12,
2019, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {11628},
pages = {71--89},
publisher = {Springer},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-24258-9\_5},
doi = {10.1007/978-3-030-24258-9\_5},
timestamp = {Mon, 01 Jul 2019 14:16:33 +0200},
biburl = {https://dblp.org/rec/conf/sat/BussT19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sat/MorgadoIBMB19,
author = {Ant{\'{o}}nio Morgado and
Alexey Ignatiev and
Maria Luisa Bonet and
Jo{\~{a}}o Marques{-}Silva and
Sam Buss},
editor = {Mikol{\'{a}}s Janota and
In{\^{e}}s Lynce},
title = {DRMaxSAT with MaxHS: First Contact},
booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2019 - 22nd
International Conference, {SAT} 2019, Lisbon, Portugal, July 9-12,
2019, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {11628},
pages = {239--249},
publisher = {Springer},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-24258-9\_17},
doi = {10.1007/978-3-030-24258-9\_17},
timestamp = {Sun, 12 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/sat/MorgadoIBMB19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BussK19,
author = {Sam Buss and
Alexander Knop},
editor = {Timothy M. Chan},
title = {Strategies for Stable Merge Sorting},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {1272--1290},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.78},
doi = {10.1137/1.9781611975482.78},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/BussK19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1909-00520,
author = {Sam Buss and
Neil Thapen},
title = {{DRAT} and Propagation Redundancy Proofs Without New Variables},
journal = {CoRR},
volume = {abs/1909.00520},
year = {2019},
url = {http://arxiv.org/abs/1909.00520},
eprinttype = {arXiv},
eprint = {1909.00520},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1909-00520.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1910-08503,
author = {Sam Buss and
Anupam Das and
Alexander Knop},
title = {Proof complexity of systems of (non-deterministic) decision trees
and branching programs},
journal = {CoRR},
volume = {abs/1910.08503},
year = {2019},
url = {http://arxiv.org/abs/1910.08503},
eprinttype = {arXiv},
eprint = {1910.08503},
timestamp = {Fri, 25 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1910-08503.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/AisenbergBBCI18,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss and
Adrian Craciun and
Gabriel Istrate},
title = {Short proofs of the Kneser-Lov{\'{a}}sz coloring principle},
journal = {Inf. Comput.},
volume = {261},
pages = {296--310},
year = {2018},
url = {https://doi.org/10.1016/j.ic.2018.02.010},
doi = {10.1016/J.IC.2018.02.010},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iandc/AisenbergBBCI18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mlq/BussR18,
author = {Sam Buss and
Ramyaa Ramyaa},
title = {Short refutations for an equivalence-chain principle for constant-depth
formulas},
journal = {Math. Log. Q.},
volume = {64},
number = {6},
pages = {505--513},
year = {2018},
url = {https://doi.org/10.1002/malq.201700034},
doi = {10.1002/MALQ.201700034},
timestamp = {Mon, 03 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mlq/BussR18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaai/BonetBIMM18,
author = {Maria Luisa Bonet and
Sam Buss and
Alexey Ignatiev and
Jo{\~{a}}o Marques{-}Silva and
Ant{\'{o}}nio Morgado},
editor = {Sheila A. McIlraith and
Kilian Q. Weinberger},
title = {MaxSAT Resolution With the Dual Rail Encoding},
booktitle = {Proceedings of the Thirty-Second {AAAI} Conference on Artificial Intelligence,
(AAAI-18), the 30th innovative Applications of Artificial Intelligence
(IAAI-18), and the 8th {AAAI} Symposium on Educational Advances in
Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February
2-7, 2018},
pages = {6565--6572},
publisher = {{AAAI} Press},
year = {2018},
url = {https://doi.org/10.1609/aaai.v32i1.12204},
doi = {10.1609/AAAI.V32I1.12204},
timestamp = {Mon, 04 Sep 2023 12:29:24 +0200},
biburl = {https://dblp.org/rec/conf/aaai/BonetBIMM18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BussIKS18,
author = {Sam Buss and
Dmitry Itsykson and
Alexander Knop and
Dmitry Sokolov},
editor = {Rocco A. Servedio},
title = {Reordering Rule Makes {OBDD} Proof Systems Stronger},
booktitle = {33rd Computational Complexity Conference, {CCC} 2018, June 22-24,
2018, San Diego, CA, {USA}},
series = {LIPIcs},
volume = {102},
pages = {16:1--16:24},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.CCC.2018.16},
doi = {10.4230/LIPICS.CCC.2018.16},
timestamp = {Thu, 02 Feb 2023 13:27:04 +0100},
biburl = {https://dblp.org/rec/conf/coco/BussIKS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1801-04641,
author = {Sam Buss and
Alexander Knop},
title = {Strategies for Stable Merge Sorting},
journal = {CoRR},
volume = {abs/1801.04641},
year = {2018},
url = {http://arxiv.org/abs/1801.04641},
eprinttype = {arXiv},
eprint = {1801.04641},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1801-04641.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussIKS18,
author = {Sam Buss and
Dmitry Itsykson and
Alexander Knop and
Dmitry Sokolov},
title = {Reordering Rule Makes {OBDD} Proof Systems Stronger},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-041}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/041},
eprinttype = {ECCC},
eprint = {TR18-041},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BussIKS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/aml/Buss17,
author = {Sam Buss},
title = {Uniform proofs of {ACC} representations},
journal = {Arch. Math. Log.},
volume = {56},
number = {5-6},
pages = {639--669},
year = {2017},
url = {https://doi.org/10.1007/s00153-017-0560-9},
doi = {10.1007/S00153-017-0560-9},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/aml/Buss17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/BeckmannB17,
author = {Arnold Beckmann and
Sam Buss},
title = {The {NP} Search Problems of Frege and Extended Frege Proofs},
journal = {{ACM} Trans. Comput. Log.},
volume = {18},
number = {2},
pages = {11:1--11:19},
year = {2017},
url = {https://doi.org/10.1145/3060145},
doi = {10.1145/3060145},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tocl/BeckmannB17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birthday/BussCMR17,
author = {Sam Buss and
Douglas Cenzer and
Mia Minnes and
Jeffrey B. Remmel},
editor = {Adam R. Day and
Michael R. Fellows and
Noam Greenberg and
Bakhadyr Khoussainov and
Alexander G. Melnikov and
Frances A. Rosamond},
title = {Injection Structures Specified by Finite State Transducers},
booktitle = {Computability and Complexity - Essays Dedicated to Rodney G. Downey
on the Occasion of His 60th Birthday},
series = {Lecture Notes in Computer Science},
volume = {10010},
pages = {394--417},
publisher = {Springer},
year = {2017},
url = {https://doi.org/10.1007/978-3-319-50062-1\_24},
doi = {10.1007/978-3-319-50062-1\_24},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/birthday/BussCMR17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BussKKK17,
author = {Sam Buss and
Valentine Kabanets and
Antonina Kolokolova and
Michal Kouck{\'{y}}},
editor = {Christos H. Papadimitriou},
title = {Expander Construction in {VNC1}},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {31:1--31:26},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.31},
doi = {10.4230/LIPICS.ITCS.2017.31},
timestamp = {Wed, 07 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BussKKK17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BeckmannBFMT16,
author = {Arnold Beckmann and
Sam Buss and
Sy{-}David Friedman and
Moritz M{\"{u}}ller and
Neil Thapen},
title = {Cobham recursive set functions},
journal = {Ann. Pure Appl. Log.},
volume = {167},
number = {3},
pages = {335--369},
year = {2016},
url = {https://doi.org/10.1016/j.apal.2015.12.005},
doi = {10.1016/J.APAL.2015.12.005},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BeckmannBFMT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsat/BussJ16,
author = {Sam Buss and
Jan Johannsen},
title = {On Linear Resolution},
journal = {J. Satisf. Boolean Model. Comput.},
volume = {10},
number = {1},
pages = {23--35},
year = {2016},
url = {https://doi.org/10.3233/sat190112},
doi = {10.3233/SAT190112},
timestamp = {Mon, 17 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsat/BussJ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/AisenbergBB16,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss},
title = {Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace
of Sets},
journal = {J. Symb. Log.},
volume = {81},
number = {2},
pages = {687--710},
year = {2016},
url = {https://doi.org/10.1017/jsl.2015.17},
doi = {10.1017/JSL.2015.17},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/AisenbergBB16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussKKK16,
author = {Sam Buss and
Valentine Kabanets and
Antonina Kolokolova and
Michal Kouck{\'{y}}},
title = {Expander Construction in VNC\({}^{\mbox{1}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-144}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/144},
eprinttype = {ECCC},
eprint = {TR16-144},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BussKKK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BussW15,
author = {Samuel R. Buss and
Ryan Williams},
title = {Limits on Alternation Trading Proofs for Time-Space Lower Bounds},
journal = {Comput. Complex.},
volume = {24},
number = {3},
pages = {533--600},
year = {2015},
url = {https://doi.org/10.1007/s00037-015-0104-9},
doi = {10.1007/S00037-015-0104-9},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/BussW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/BeckmannBF15,
author = {Arnold Beckmann and
Samuel R. Buss and
Sy{-}David Friedman},
title = {Safe Recursive Set Functions},
journal = {J. Symb. Log.},
volume = {80},
number = {3},
pages = {730--762},
year = {2015},
url = {https://doi.org/10.1017/jsl.2015.26},
doi = {10.1017/JSL.2015.26},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/BeckmannBF15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sLogica/Buss15,
author = {Sam Buss},
title = {Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination},
journal = {Stud Logica},
volume = {103},
number = {3},
pages = {663--667},
year = {2015},
url = {https://doi.org/10.1007/s11225-015-9618-z},
doi = {10.1007/S11225-015-9618-Z},
timestamp = {Tue, 01 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sLogica/Buss15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Buss15,
author = {Sam Buss},
title = {Quasipolynomial size proofs of the propositional pigeonhole principle},
journal = {Theor. Comput. Sci.},
volume = {576},
pages = {77--84},
year = {2015},
url = {https://doi.org/10.1016/j.tcs.2015.02.005},
doi = {10.1016/J.TCS.2015.02.005},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/Buss15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Buss15,
author = {Sam Buss},
editor = {Lev D. Beklemishev and
Daniil V. Musatov},
title = {Propositional Proofs in Frege and Extended Frege Systems (Abstract)},
booktitle = {Computer Science - Theory and Applications - 10th International Computer
Science Symposium in Russia, {CSR} 2015, Listvyanka, Russia, July
13-17, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9139},
pages = {1--6},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-319-20297-6\_1},
doi = {10.1007/978-3-319-20297-6\_1},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/csr/Buss15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/AisenbergBBCI15,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss and
Adrian Craciun and
Gabriel Istrate},
editor = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Kazuo Iwama and
Naoki Kobayashi and
Bettina Speckmann},
title = {Short Proofs of the Kneser-Lov{\'{a}}sz Coloring Principle},
booktitle = {Automata, Languages, and Programming - 42nd International Colloquium,
{ICALP} 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part {II}},
series = {Lecture Notes in Computer Science},
volume = {9135},
pages = {44--55},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-47666-6\_4},
doi = {10.1007/978-3-662-47666-6\_4},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/AisenbergBBCI15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AisenbergBBCI15,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss and
Adrian Craciun and
Gabriel Istrate},
title = {Short Proofs of the Kneser-Lov{\'{a}}sz Coloring Principle},
journal = {CoRR},
volume = {abs/1505.05531},
year = {2015},
url = {http://arxiv.org/abs/1505.05531},
eprinttype = {arXiv},
eprint = {1505.05531},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AisenbergBBCI15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AisenbergBB15,
author = {James Aisenberg and
Maria Luisa Bonet and
Sam Buss},
title = {2-D Tucker is {PPA} complete},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-163}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/163},
eprinttype = {ECCC},
eprint = {TR15-163},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AisenbergBB15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BussK14,
author = {Samuel R. Buss and
Leszek Aleksander Kolodziejczyk},
title = {Small Stone in Pool},
journal = {Log. Methods Comput. Sci.},
volume = {10},
number = {2},
year = {2014},
url = {https://doi.org/10.2168/LMCS-10(2:16)2014},
doi = {10.2168/LMCS-10(2:16)2014},
timestamp = {Thu, 25 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BussK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BussCR14,
author = {Sam Buss and
Douglas Cenzer and
Jeffrey B. Remmel},
title = {Sub-computable Boundedness Randomness},
journal = {Log. Methods Comput. Sci.},
volume = {10},
number = {4},
year = {2014},
url = {https://doi.org/10.2168/LMCS-10(4:15)2014},
doi = {10.2168/LMCS-10(4:15)2014},
timestamp = {Thu, 25 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BussCR14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jair/BonetBJ14,
author = {Maria Luisa Bonet and
Sam Buss and
Jan Johannsen},
title = {Improved Separations of Regular Resolution from Clause Learning Proof
Systems},
journal = {J. Artif. Intell. Res.},
volume = {49},
pages = {669--703},
year = {2014},
url = {https://doi.org/10.1613/jair.4260},
doi = {10.1613/JAIR.4260},
timestamp = {Mon, 21 Jan 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jair/BonetBJ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BussS14,
author = {Sam Buss and
Michael Soltys},
title = {Unshuffling a square is NP-hard},
journal = {J. Comput. Syst. Sci.},
volume = {80},
number = {4},
pages = {766--776},
year = {2014},
url = {https://doi.org/10.1016/j.jcss.2013.11.002},
doi = {10.1016/J.JCSS.2013.11.002},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BussS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/BussKT14,
author = {Samuel R. Buss and
Leszek Aleksander Kolodziejczyk and
Neil Thapen},
title = {Fragments of Approximate Counting},
journal = {J. Symb. Log.},
volume = {79},
number = {2},
pages = {496--525},
year = {2014},
url = {https://doi.org/10.1017/jsl.2013.37},
doi = {10.1017/JSL.2013.37},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/BussKT14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/BeckmannB14,
author = {Arnold Beckmann and
Samuel R. Buss},
title = {Improved witnessing and local improvement principles for second-order
bounded arithmetic},
journal = {{ACM} Trans. Comput. Log.},
volume = {15},
number = {1},
pages = {2:1--2:35},
year = {2014},
url = {https://doi.org/10.1145/2559950},
doi = {10.1145/2559950},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tocl/BeckmannB14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/daglib/0033748,
author = {Samuel R. Buss},
title = {3-D Computer Graphics},
publisher = {Cambridge University Press},
year = {2013},
isbn = {978-0-521-82103-2},
timestamp = {Mon, 01 Sep 2014 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/daglib/0033748.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussLNS13,
author = {Sam Buss and
Benedikt L{\"{o}}we and
Dag Normann and
Ivan N. Soskov},
title = {Computability in Europe 2011},
journal = {Ann. Pure Appl. Log.},
volume = {164},
number = {5},
pages = {509--510},
year = {2013},
url = {https://doi.org/10.1016/j.apal.2013.02.001},
doi = {10.1016/J.APAL.2013.02.001},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussLNS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/BussM13,
author = {Sam Buss and
Mia Minnes},
title = {Probabilistic algorithmic randomness},
journal = {J. Symb. Log.},
volume = {78},
number = {2},
pages = {579--601},
year = {2013},
url = {https://doi.org/10.2178/jsl.7802130},
doi = {10.2178/JSL.7802130},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/BussM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ijcai/BonetB13,
author = {Maria Luisa Bonet and
Sam Buss},
editor = {Francesca Rossi},
title = {An Improved Separation of Regular Resolution from Pool Resolution
and Clause Learning (Extended Abstract)},
booktitle = {{IJCAI} 2013, Proceedings of the 23rd International Joint Conference
on Artificial Intelligence, Beijing, China, August 3-9, 2013},
pages = {2972--2976},
publisher = {{IJCAI/AAAI}},
year = {2013},
url = {http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6768},
timestamp = {Tue, 23 Jan 2024 13:25:46 +0100},
biburl = {https://dblp.org/rec/conf/ijcai/BonetB13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/Buss13,
author = {Sam Buss},
editor = {Krishnendu Chatterjee and
Jir{\'{\i}} Sgall},
title = {Alternation Trading Proofs and Their Limitations},
booktitle = {Mathematical Foundations of Computer Science 2013 - 38th International
Symposium, {MFCS} 2013, Klosterneuburg, Austria, August 26-30, 2013.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8087},
pages = {1--7},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40313-2\_1},
doi = {10.1007/978-3-642-40313-2\_1},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/Buss13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Ambos-SpiesBBL12,
author = {Klaus Ambos{-}Spies and
Arnold Beckmann and
Samuel R. Buss and
Benedikt L{\"{o}}we},
title = {Computability in Europe 2009},
journal = {Ann. Pure Appl. Log.},
volume = {163},
number = {5},
pages = {483--484},
year = {2012},
url = {https://doi.org/10.1016/j.apal.2011.06.006},
doi = {10.1016/J.APAL.2011.06.006},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Ambos-SpiesBBL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussK12,
author = {Samuel R. Buss and
Roman Kuznets},
title = {Lower complexity bounds in justification logic},
journal = {Ann. Pure Appl. Log.},
volume = {163},
number = {7},
pages = {888--905},
year = {2012},
url = {https://doi.org/10.1016/j.apal.2011.09.010},
doi = {10.1016/J.APAL.2011.09.010},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss12,
author = {Samuel R. Buss},
title = {Towards {NP-P} via proof complexity and search},
journal = {Ann. Pure Appl. Log.},
volume = {163},
number = {7},
pages = {906--917},
year = {2012},
url = {https://doi.org/10.1016/j.apal.2011.09.009},
doi = {10.1016/J.APAL.2011.09.009},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussJ12,
author = {Samuel R. Buss and
Alan S. Johnson},
title = {Propositional proofs and reductions between {NP} search problems},
journal = {Ann. Pure Appl. Log.},
volume = {163},
number = {9},
pages = {1163--1182},
year = {2012},
url = {https://doi.org/10.1016/j.apal.2012.01.015},
doi = {10.1016/J.APAL.2012.01.015},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussJ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/Buss12,
author = {Samuel R. Buss},
title = {Sharpened lower bounds for cut elimination},
journal = {J. Symb. Log.},
volume = {77},
number = {2},
pages = {656--668},
year = {2012},
url = {https://doi.org/10.2178/jsl/1333566644},
doi = {10.2178/JSL/1333566644},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/Buss12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BussW12,
author = {Samuel R. Buss and
Ryan Williams},
title = {Limits on Alternation-Trading Proofs for Time-Space Lower Bounds},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {181--191},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.30},
doi = {10.1109/CCC.2012.30},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BussW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sat/BonetB12,
author = {Maria Luisa Bonet and
Samuel R. Buss},
editor = {Alessandro Cimatti and
Roberto Sebastiani},
title = {An Improved Separation of Regular Resolution from Pool Resolution
and Clause Learning},
booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2012 - 15th
International Conference, Trento, Italy, June 17-20, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7317},
pages = {44--57},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31612-8\_5},
doi = {10.1007/978-3-642-31612-8\_5},
timestamp = {Sun, 02 Jun 2019 21:24:00 +0200},
biburl = {https://dblp.org/rec/conf/sat/BonetB12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1202-2296,
author = {Maria Luisa Bonet and
Samuel R. Buss},
title = {An Improved Separation of Regular Resolution from Pool Resolution
and Clause Learning},
journal = {CoRR},
volume = {abs/1202.2296},
year = {2012},
url = {http://arxiv.org/abs/1202.2296},
eprinttype = {arXiv},
eprint = {1202.2296},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1202-2296.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1208-2469,
author = {Maria Luisa Bonet and
Sam Buss and
Jan Johannsen},
title = {Improved Separations of Regular Resolution from Clause Learning Proof
Systems},
journal = {CoRR},
volume = {abs/1208.2469},
year = {2012},
url = {http://arxiv.org/abs/1208.2469},
eprinttype = {arXiv},
eprint = {1208.2469},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1208-2469.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BussS12,
author = {Sam Buss and
Michael Soltys},
title = {Unshuffling a Square is NP-Hard},
journal = {CoRR},
volume = {abs/1211.7161},
year = {2012},
url = {http://arxiv.org/abs/1211.7161},
eprinttype = {arXiv},
eprint = {1211.7161},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BussS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/BussCFFM11,
author = {Sam Buss and
Yijia Chen and
J{\"{o}}rg Flum and
Sy{-}David Friedman and
Moritz M{\"{u}}ller},
title = {Strong isomorphism reductions in complexity theory},
journal = {J. Symb. Log.},
volume = {76},
number = {4},
pages = {1381--1402},
year = {2011},
url = {https://doi.org/10.2178/jsl/1318338855},
doi = {10.2178/JSL/1318338855},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/BussCFFM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BeckmannB11,
author = {Arnold Beckmann and
Samuel R. Buss},
title = {Corrected upper bounds for free-cut elimination},
journal = {Theor. Comput. Sci.},
volume = {412},
number = {39},
pages = {5433--5445},
year = {2011},
url = {https://doi.org/10.1016/j.tcs.2011.05.053},
doi = {10.1016/J.TCS.2011.05.053},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/BeckmannB11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BussW11,
author = {Sam Buss and
Ryan Williams},
title = {Limits on Alternation-Trading Proofs for Time-Space Lower Bounds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-031}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/031},
eprinttype = {ECCC},
eprint = {TR11-031},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BussW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mlq/BussJ10,
author = {Samuel R. Buss and
Alan S. Johnson},
title = {The quantifier complexity of polynomial-size iterated definitions
in first-order logic},
journal = {Math. Log. Q.},
volume = {56},
number = {6},
pages = {573--590},
year = {2010},
url = {https://doi.org/10.1002/malq.200910111},
doi = {10.1002/MALQ.200910111},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mlq/BussJ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/aml/Buss09,
author = {Samuel R. Buss},
title = {Pool resolution is NP-hard to recognize},
journal = {Arch. Math. Log.},
volume = {48},
number = {8},
pages = {793--798},
year = {2009},
url = {https://doi.org/10.1007/s00153-009-0152-4},
doi = {10.1007/S00153-009-0152-4},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/aml/Buss09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussCLS09,
author = {Samuel R. Buss and
S. Barry Cooper and
Benedikt L{\"{o}}we and
Andrea Sorbi},
title = {Preface},
journal = {Ann. Pure Appl. Log.},
volume = {160},
number = {3},
pages = {229--230},
year = {2009},
url = {https://doi.org/10.1016/j.apal.2009.01.011},
doi = {10.1016/J.APAL.2009.01.011},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussCLS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jml/BeckmannB09,
author = {Arnold Beckmann and
Samuel R. Buss},
title = {Polynomial Local Search in the Polynomial Hierarchy and Witnessing
in Fragments of Bounded Arithmetic},
journal = {J. Math. Log.},
volume = {9},
number = {1},
year = {2009},
url = {https://doi.org/10.1142/S0219061309000847},
doi = {10.1142/S0219061309000847},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jml/BeckmannB09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lfcs/BussK09,
author = {Samuel R. Buss and
Roman Kuznets},
editor = {Sergei N. Art{\"{e}}mov and
Anil Nerode},
title = {The NP-Completeness of Reflected Fragments of Justification Logics},
booktitle = {Logical Foundations of Computer Science, International Symposium,
{LFCS} 2009, Deerfield Beach, FL, USA, January 3-6, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5407},
pages = {122--136},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-540-92687-0\_9},
doi = {10.1007/978-3-540-92687-0\_9},
timestamp = {Tue, 14 May 2019 10:00:54 +0200},
biburl = {https://dblp.org/rec/conf/lfcs/BussK09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/vr/TracyBW09,
author = {Daniel J. Tracy and
Samuel R. Buss and
Bryan M. Woods},
title = {Efficient Large-Scale Sweep and Prune Methods with {AABB} Insertion
and Removal},
booktitle = {{IEEE} Virtual Reality Conference 2009 {(VR} 2009), 14-18 March 2009,
Lafayette, Louisiana, USA, Proceedings},
pages = {191--198},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/VR.2009.4811022},
doi = {10.1109/VR.2009.4811022},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/vr/TracyBW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/lmcs/BussHJ08,
author = {Samuel R. Buss and
Jan Hoffmann and
Jan Johannsen},
title = {Resolution Trees with Lemmas: Resolution Refinements that Characterize
{DLL} Algorithms with Clause Learning},
journal = {Log. Methods Comput. Sci.},
volume = {4},
number = {4},
year = {2008},
url = {https://doi.org/10.2168/LMCS-4(4:13)2008},
doi = {10.2168/LMCS-4(4:13)2008},
timestamp = {Thu, 25 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/lmcs/BussHJ08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BussH08,
author = {Samuel R. Buss and
Jan Hoffmann},
title = {The NP-hardness of finding a directed acyclic graph for regular resolution},
journal = {Theor. Comput. Sci.},
volume = {396},
number = {1-3},
pages = {271--276},
year = {2008},
url = {https://doi.org/10.1016/j.tcs.2008.01.039},
doi = {10.1016/J.TCS.2008.01.039},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/BussH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0811-1075,
author = {Samuel R. Buss and
Jan Hoffmann and
Jan Johannsen},
title = {Resolution Trees with Lemmas: Resolution Refinements that Characterize
{DLL} Algorithms with Clause Learning},
journal = {CoRR},
volume = {abs/0811.1075},
year = {2008},
url = {http://arxiv.org/abs/0811.1075},
eprinttype = {arXiv},
eprint = {0811.1075},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0811-1075.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Buss06,
author = {Samuel R. Buss},
title = {Polynomial-size Frege and resolution proofs of \emph{st}-connectivity
and Hex tautologies},
journal = {Theor. Comput. Sci.},
volume = {357},
number = {1-3},
pages = {35--52},
year = {2006},
url = {https://doi.org/10.1016/j.tcs.2006.03.011},
doi = {10.1016/J.TCS.2006.03.011},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Buss06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BeckmannB05,
author = {Arnold Beckmann and
Samuel R. Buss},
title = {Separation results for the size of constant-depth propositional proofs},
journal = {Ann. Pure Appl. Log.},
volume = {136},
number = {1-2},
pages = {30--55},
year = {2005},
url = {https://doi.org/10.1016/j.apal.2005.05.002},
doi = {10.1016/J.APAL.2005.05.002},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BeckmannB05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jgtools/BussK05,
author = {Samuel R. Buss and
Jin{-}Su Kim},
title = {Selectively Damped Least Squares for Inverse Kinematics},
journal = {J. Graph. Tools},
volume = {10},
number = {3},
pages = {37--49},
year = {2005},
url = {https://doi.org/10.1080/2151237X.2005.10129202},
doi = {10.1080/2151237X.2005.10129202},
timestamp = {Thu, 18 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jgtools/BussK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/vc/Buss05,
author = {Samuel R. Buss},
title = {Collision detection with relative screw motion},
journal = {Vis. Comput.},
volume = {21},
number = {1-2},
pages = {41--58},
year = {2005},
url = {https://doi.org/10.1007/s00371-004-0269-8},
doi = {10.1007/S00371-004-0269-8},
timestamp = {Thu, 04 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/vc/Buss05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/SegerlindBI04,
author = {Nathan Segerlind and
Samuel R. Buss and
Russell Impagliazzo},
title = {A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF
Resolution},
journal = {{SIAM} J. Comput.},
volume = {33},
number = {5},
pages = {1171--1200},
year = {2004},
url = {https://doi.org/10.1137/S0097539703428555},
doi = {10.1137/S0097539703428555},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/SegerlindBI04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BeckmannPB03,
author = {Arnold Beckmann and
Chris Pollett and
Samuel R. Buss},
title = {Ordinal notations and well-orderings in bounded arithmetic},
journal = {Ann. Pure Appl. Log.},
volume = {120},
number = {1-3},
pages = {197--223},
year = {2003},
url = {https://doi.org/10.1016/S0168-0072(02)00066-0},
doi = {10.1016/S0168-0072(02)00066-0},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BeckmannPB03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BeckmannBP03,
author = {Arnold Beckmann and
Samuel R. Buss and
Chris Pollett},
title = {Erratum to "Ordinal notations and well-orderings in bounded arithmetic"
[Annals of Pure and Applied Logic 120 {(2003)} 197-223]},
journal = {Ann. Pure Appl. Log.},
volume = {123},
number = {1-3},
pages = {291},
year = {2003},
url = {https://doi.org/10.1016/S0168-0072(03)00039-3},
doi = {10.1016/S0168-0072(03)00039-3},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BeckmannBP03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/BussK02,
author = {Samuel R. Buss and
Bruce M. Kapron},
title = {Resource-bounded continuity and sequentiality for type-two functionals},
journal = {{ACM} Trans. Comput. Log.},
volume = {3},
number = {3},
pages = {402--417},
year = {2002},
url = {https://doi.org/10.1145/507382.507387},
doi = {10.1145/507382.507387},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tocl/BussK02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SegerlindBI02,
author = {Nathan Segerlind and
Samuel R. Buss and
Russell Impagliazzo},
title = {A Switching Lemma for Small Restrictions and Lower Bounds for k -
{DNF} Resolution},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {604},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1181984},
doi = {10.1109/SFCS.2002.1181984},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SegerlindBI02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-LO-0205003,
author = {Samuel R. Buss and
Alexander S. Kechris and
Anand Pillay and
Richard A. Shore},
title = {The prospects for mathematical logic in the twenty-first century},
journal = {CoRR},
volume = {cs.LO/0205003},
year = {2002},
url = {https://arxiv.org/abs/cs/0205003},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-LO-0205003.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussP01,
author = {Samuel R. Buss and
Pavel Pudl{\'{a}}k},
title = {On the computational content of intuitionistic propositional proofs},
journal = {Ann. Pure Appl. Log.},
volume = {109},
number = {1-2},
pages = {49--63},
year = {2001},
url = {https://doi.org/10.1016/S0168-0072(01)00040-9},
doi = {10.1016/S0168-0072(01)00040-9},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussP01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/bsl/BussKPS01,
author = {Samuel R. Buss and
Alexander S. Kechris and
Anand Pillay and
Richard A. Shore},
title = {The prospects for mathematical logic in the twenty-first century},
journal = {Bull. Symb. Log.},
volume = {7},
number = {2},
pages = {169--196},
year = {2001},
url = {https://doi.org/10.2307/2687773},
doi = {10.2307/2687773},
timestamp = {Fri, 03 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/bsl/BussKPS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BussGIP01,
author = {Samuel R. Buss and
Dima Grigoriev and
Russell Impagliazzo and
Toniann Pitassi},
title = {Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct
Primes},
journal = {J. Comput. Syst. Sci.},
volume = {62},
number = {2},
pages = {267--289},
year = {2001},
url = {https://doi.org/10.1006/jcss.2000.1726},
doi = {10.1006/JCSS.2000.1726},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BussGIP01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/AlekhnovichBMP01,
author = {Michael Alekhnovich and
Samuel R. Buss and
Shlomo Moran and
Toniann Pitassi},
title = {Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate},
journal = {J. Symb. Log.},
volume = {66},
number = {1},
pages = {171--191},
year = {2001},
url = {https://doi.org/10.2307/2694916},
doi = {10.2307/2694916},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/AlekhnovichBMP01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tog/BussF01,
author = {Samuel R. Buss and
Jay P. Fillmore},
title = {Spherical averages and applications to spherical splines and interpolation},
journal = {{ACM} Trans. Graph.},
volume = {20},
number = {2},
pages = {95--126},
year = {2001},
url = {https://doi.org/10.1145/502122.502124},
doi = {10.1145/502122.502124},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tog/BussF01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lics/BussK00,
author = {Samuel R. Buss and
Bruce M. Kapron},
title = {Resource-Bounded Continuity and Sequentiality for Type-Two Functionals},
booktitle = {15th Annual {IEEE} Symposium on Logic in Computer Science, Santa Barbara,
California, USA, June 26-29, 2000},
pages = {77--83},
publisher = {{IEEE} Computer Society},
year = {2000},
url = {https://doi.org/10.1109/LICS.2000.855757},
doi = {10.1109/LICS.2000.855757},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/lics/BussK00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:journals/entcs/BussR00,
author = {Samuel R. Buss and
Grigore Rosu},
editor = {Horst Reichel},
title = {Incompleteness of Behavioral Logics},
booktitle = {Coalgebraic Methods in Computer Science, {CMCS} 2000, Berlin, Germany,
March 25-26, 2000},
series = {Electronic Notes in Theoretical Computer Science},
volume = {33},
pages = {61--79},
publisher = {Elsevier},
year = {2000},
url = {https://doi.org/10.1016/S1571-0661(05)80756-X},
doi = {10.1016/S1571-0661(05)80756-X},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/entcs/BussR00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss99,
author = {Samuel R. Buss},
title = {Bounded Arithmetic, Proof Complexity and Two Papers of Parikh},
journal = {Ann. Pure Appl. Log.},
volume = {96},
number = {1-3},
pages = {43--55},
year = {1999},
url = {https://doi.org/10.1016/S0168-0072(98)00030-X},
doi = {10.1016/S0168-0072(98)00030-X},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussM99,
author = {Samuel R. Buss and
Grigori Mints},
title = {The Complexity of the Disjunction and Existential Properties in Intuitionistic
Logic},
journal = {Ann. Pure Appl. Log.},
volume = {99},
number = {1-3},
pages = {93--104},
year = {1999},
url = {https://doi.org/10.1016/S0168-0072(99)00002-0},
doi = {10.1016/S0168-0072(99)00002-0},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussM99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BussGIP99,
author = {Samuel R. Buss and
Dima Grigoriev and
Russell Impagliazzo and
Toniann Pitassi},
title = {Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct
Primes (Abstract)},
booktitle = {Proceedings of the 14th Annual {IEEE} Conference on Computational
Complexity, Atlanta, Georgia, USA, May 4-6, 1999},
pages = {5},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/CCC.1999.766254},
doi = {10.1109/CCC.1999.766254},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BussGIP99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BussGIP99,
author = {Samuel R. Buss and
Dima Grigoriev and
Russell Impagliazzo and
Toniann Pitassi},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct
Primes},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {547--556},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301399},
doi = {10.1145/301250.301399},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BussGIP99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BussP98,
author = {Samuel R. Buss and
Toniann Pitassi},
title = {Good Degree Bounds on Nullstellensatz Refutations of the Induction
Principle},
journal = {J. Comput. Syst. Sci.},
volume = {57},
number = {2},
pages = {162--171},
year = {1998},
url = {https://doi.org/10.1006/jcss.1998.1585},
doi = {10.1006/JCSS.1998.1585},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/BussP98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BussY98,
author = {Samuel R. Buss and
Peter N. Yianilos},
title = {Linear and \emph{O}(\emph{n} log \emph{n}) Time Minimum-Cost Matching
Algorithms for Quasi-Convex Tours},
journal = {{SIAM} J. Comput.},
volume = {27},
number = {1},
pages = {170--201},
year = {1998},
url = {https://doi.org/10.1137/S0097539794267243},
doi = {10.1137/S0097539794267243},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BussY98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/AlekhnovichBMP98,
author = {Michael Alekhnovich and
Samuel R. Buss and
Shlomo Moran and
Toniann Pitassi},
editor = {Lubos Brim and
Jozef Gruska and
Jir{\'{\i}} Zlatuska},
title = {Minimum Propositional Proof Length is NP-Hard to Linearly Approximate},
booktitle = {Mathematical Foundations of Computer Science 1998, 23rd International
Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1450},
pages = {176--184},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/BFb0055766},
doi = {10.1007/BFB0055766},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/AlekhnovichBMP98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/dimacs/dimacs39,
editor = {Paul Beame and
Samuel R. Buss},
title = {Proof Complexity and Feasible Arithmetics, Proceedings of a {DIMACS}
Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {39},
publisher = {{DIMACS/AMS}},
year = {1998},
url = {https://doi.org/10.1090/dimacs/039},
doi = {10.1090/DIMACS/039},
isbn = {978-0-8218-0577-0},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs39.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BussIPRS97,
author = {Samuel R. Buss and
Russell Impagliazzo and
Jan Kraj{\'{\i}}cek and
Pavel Pudl{\'{a}}k and
Alexander A. Razborov and
Jir{\'{\i}} Sgall},
title = {Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems
with Modular Counting},
journal = {Comput. Complex.},
volume = {6},
number = {3},
pages = {256--298},
year = {1997},
url = {https://doi.org/10.1007/BF01294258},
doi = {10.1007/BF01294258},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/BussIPRS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csl/BussP97,
author = {Samuel R. Buss and
Toniann Pitassi},
editor = {Mogens Nielsen and
Wolfgang Thomas},
title = {Resolution and the Weak Pigeonhole Principle},
booktitle = {Computer Science Logic, 11th International Workshop, {CSL} '97, Annual
Conference of the EACSL, Aarhus, Denmark, August 23-29, 1997, Selected
Papers},
series = {Lecture Notes in Computer Science},
volume = {1414},
pages = {149--156},
publisher = {Springer},
year = {1997},
url = {https://doi.org/10.1007/BFb0028012},
doi = {10.1007/BFB0028012},
timestamp = {Tue, 14 May 2019 10:00:42 +0200},
biburl = {https://dblp.org/rec/conf/csl/BussP97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kgc/Buss97,
author = {Samuel R. Buss},
editor = {Georg Gottlob and
Alexander Leitsch and
Daniele Mundici},
title = {Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization},
booktitle = {Computational Logic and Proof Theory, 5th Kurt G{\"{o}}del Colloquium,
KGC'97, Vienna, Austria, August 25-29, 1997, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1289},
pages = {18--33},
publisher = {Springer},
year = {1997},
url = {https://doi.org/10.1007/3-540-63385-5\_30},
doi = {10.1007/3-540-63385-5\_30},
timestamp = {Tue, 14 May 2019 10:00:52 +0200},
biburl = {https://dblp.org/rec/conf/kgc/Buss97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/aml/BussC96,
author = {Samuel R. Buss and
Peter Clote},
title = {Cutting planes, connectivity, and threshold logic},
journal = {Arch. Math. Log.},
volume = {35},
number = {1},
pages = {33--62},
year = {1996},
url = {https://doi.org/10.1007/BF01845704},
doi = {10.1007/BF01845704},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/aml/BussC96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BussP96,
author = {Samuel R. Buss and
Toniann Pitassi},
editor = {Steven Homer and
Jin{-}Yi Cai},
title = {Good Degree Bounds on Nullstellensatz Refutations of the Induction
Principle},
booktitle = {Proceedings of the Eleveth Annual {IEEE} Conference on Computational
Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996},
pages = {233--242},
publisher = {{IEEE} Computer Society},
year = {1996},
url = {https://doi.org/10.1109/CCC.1996.507685},
doi = {10.1109/CCC.1996.507685},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BussP96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/Buss96,
author = {Samuel R. Buss},
editor = {Paul Beame and
Samuel R. Buss},
title = {Lower bounds on Nullstellensatz proofs via designs},
booktitle = {Proof Complexity and Feasible Arithmetics, Proceedings of a {DIMACS}
Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {39},
pages = {59--71},
publisher = {{DIMACS/AMS}},
year = {1996},
url = {https://doi.org/10.1090/dimacs/039/04},
doi = {10.1090/DIMACS/039/04},
timestamp = {Sat, 30 Sep 2023 09:38:58 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/Buss96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/aml/Buss95,
author = {Samuel R. Buss},
title = {Some remarks on lengths of propositional proofs},
journal = {Arch. Math. Log.},
volume = {34},
number = {6},
pages = {377--394},
year = {1995},
url = {https://doi.org/10.1007/BF02391554},
doi = {10.1007/BF02391554},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/aml/Buss95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/BussI95,
author = {Samuel R. Buss and
Aleksandar Ignjatovic},
title = {Unprovability of Consistency Statements in Fragments of Bounded Arithmetic},
journal = {Ann. Pure Appl. Log.},
volume = {74},
number = {3},
pages = {221--244},
year = {1995},
url = {https://doi.org/10.1016/0168-0072(94)00049-9},
doi = {10.1016/0168-0072(94)00049-9},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/BussI95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss95,
author = {Samuel R. Buss},
title = {Relating the Bounded Arithmetic and Polynomial Time Hierarchies},
journal = {Ann. Pure Appl. Log.},
volume = {75},
number = {1-2},
pages = {67--77},
year = {1995},
url = {https://doi.org/10.1016/0168-0072(94)00057-A},
doi = {10.1016/0168-0072(94)00057-A},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BonetB95,
author = {Maria Luisa Bonet and
Samuel R. Buss},
title = {The Serial Transitive Closure Problem for Trees},
journal = {{SIAM} J. Comput.},
volume = {24},
number = {1},
pages = {109--122},
year = {1995},
url = {https://doi.org/10.1137/S0097539792225303},
doi = {10.1137/S0097539792225303},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BonetB95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/BonetB94,
author = {Maria Luisa Bonet and
Samuel R. Buss},
title = {Size-Depth Tradeoffs for Boolean Fomulae},
journal = {Inf. Process. Lett.},
volume = {49},
number = {3},
pages = {151--155},
year = {1994},
url = {https://doi.org/10.1016/0020-0190(94)90093-0},
doi = {10.1016/0020-0190(94)90093-0},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/BonetB94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/Buss94,
author = {Samuel R. Buss},
title = {On G{\"{o}}del's Theorems on Lenghts of Proofs {I:} Number of
Lines and Speedup for Arithmetics},
journal = {J. Symb. Log.},
volume = {59},
number = {3},
pages = {737--756},
year = {1994},
url = {https://doi.org/10.2307/2275906},
doi = {10.2307/2275906},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/Buss94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csl/PudlakB94,
author = {Pavel Pudl{\'{a}}k and
Samuel R. Buss},
editor = {Leszek Pacholski and
Jerzy Tiuryn},
title = {How to Lie Without Being (Easily) Convicted and the Length of Proofs
in Propositional Calculus},
booktitle = {Computer Science Logic, 8th International Workshop, {CSL} '94, Kazimierz,
Poland, September 25-30, 1994, Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {933},
pages = {151--162},
publisher = {Springer},
year = {1994},
url = {https://doi.org/10.1007/BFb0022253},
doi = {10.1007/BFB0022253},
timestamp = {Tue, 14 May 2019 10:00:42 +0200},
biburl = {https://dblp.org/rec/conf/csl/PudlakB94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lcc/Buss94,
author = {Samuel R. Buss},
editor = {Daniel Leivant},
title = {On Herbrand's Theorem},
booktitle = {Logical and Computational Complexity. Selected Papers. Logic and Computational
Complexity, International Workshop {LCC} '94, Indianapolis, Indiana,
USA, 13-16 October 1994},
series = {Lecture Notes in Computer Science},
volume = {960},
pages = {195--209},
publisher = {Springer},
year = {1994},
url = {https://doi.org/10.1007/3-540-60178-3\_85},
doi = {10.1007/3-540-60178-3\_85},
timestamp = {Tue, 14 May 2019 10:00:54 +0200},
biburl = {https://dblp.org/rec/conf/lcc/Buss94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BussY94,
author = {Samuel R. Buss and
Peter N. Yianilos},
editor = {Daniel Dominic Sleator},
title = {Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex
Tours},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {65--76},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314480},
timestamp = {Thu, 05 Jul 2018 07:29:19 +0200},
biburl = {https://dblp.org/rec/conf/soda/BussY94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss93,
author = {Samuel R. Buss},
title = {Intuitionistic Validity in T-Normal Kripke Structures},
journal = {Ann. Pure Appl. Log.},
volume = {59},
number = {3},
pages = {159--173},
year = {1993},
url = {https://doi.org/10.1016/0168-0072(93)90091-Q},
doi = {10.1016/0168-0072(93)90091-Q},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/BonetB93,
author = {Maria Luisa Bonet and
Samuel R. Buss},
title = {The Deduction Rule and Linear and Near-Linear Proof Simulations},
journal = {J. Symb. Log.},
volume = {58},
number = {2},
pages = {688--709},
year = {1993},
url = {https://doi.org/10.2307/2275228},
doi = {10.2307/2275228},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/BonetB93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Buss92,
author = {Samuel R. Buss},
title = {The Graph of Multiplication is Equivalent to Counting},
journal = {Inf. Process. Lett.},
volume = {41},
number = {4},
pages = {199--201},
year = {1992},
url = {https://doi.org/10.1016/0020-0190(92)90180-4},
doi = {10.1016/0020-0190(92)90180-4},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Buss92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BussCGR92,
author = {Samuel R. Buss and
Stephen A. Cook and
A. Gupta and
V. Ramachandran},
title = {An Optimal Parallel Algorithm for Formula Evaluation},
journal = {{SIAM} J. Comput.},
volume = {21},
number = {4},
pages = {755--780},
year = {1992},
url = {https://doi.org/10.1137/0221046},
doi = {10.1137/0221046},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BussCGR92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss91,
author = {Samuel R. Buss},
title = {Propositional Consistency Proofs},
journal = {Ann. Pure Appl. Log.},
volume = {52},
number = {1-2},
pages = {3--29},
year = {1991},
url = {https://doi.org/10.1016/0168-0072(91)90036-L},
doi = {10.1016/0168-0072(91)90036-L},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/apal/Buss91a,
author = {Samuel R. Buss},
title = {The Undecidability of k-Provability},
journal = {Ann. Pure Appl. Log.},
volume = {53},
number = {1},
pages = {75--102},
year = {1991},
url = {https://doi.org/10.1016/0168-0072(91)90059-U},
doi = {10.1016/0168-0072(91)90059-U},
timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/apal/Buss91a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/compsys/BussPT91,
author = {Samuel R. Buss and
Christos H. Papadimitriou and
John N. Tsitsiklis},
title = {On the Predictability of Coupled Automata: An Allegory about Chaos},
journal = {Complex Syst.},
volume = {5},
number = {5},
year = {1991},
url = {http://www.complex-systems.com/abstracts/v05\_i05\_a07.html},
timestamp = {Fri, 11 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/compsys/BussPT91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/BussH91,
author = {Samuel R. Buss and
Louise Hay},
title = {On Truth-Table Reducibility to {SAT}},
journal = {Inf. Comput.},
volume = {91},
number = {1},
pages = {86--102},
year = {1991},
url = {https://doi.org/10.1016/0890-5401(91)90075-D},
doi = {10.1016/0890-5401(91)90075-D},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/BussH91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lics/BonetB91,
author = {Maria Luisa Bonet and
Samuel R. Buss},
title = {On the Deduction Rule and the Number of Proof Lines},
booktitle = {Proceedings of the Sixth Annual Symposium on Logic in Computer Science
{(LICS} '91), Amsterdam, The Netherlands, July 15-18, 1991},
pages = {286--297},
publisher = {{IEEE} Computer Society},
year = {1991},
url = {https://doi.org/10.1109/LICS.1991.151653},
doi = {10.1109/LICS.1991.151653},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/lics/BonetB91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ndjfl/Buss90,
author = {Samuel R. Buss},
title = {The Modal Logic of Pure Provability},
journal = {Notre Dame J. Formal Log.},
volume = {31},
number = {2},
pages = {225--231},
year = {1990},
url = {https://doi.org/10.1305/ndjfl/1093635417},
doi = {10.1305/NDJFL/1093635417},
timestamp = {Thu, 21 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ndjfl/Buss90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BussPT90,
author = {Samuel R. Buss and
Christos H. Papadimitriou and
John N. Tsitsiklis},
title = {On the Predictability of Coupled Automata: An Allegory about Chaos},
booktitle = {31st Annual Symposium on Foundations of Computer Science, St. Louis,
Missouri, USA, October 22-24, 1990, Volume {II}},
pages = {788--793},
publisher = {{IEEE} Computer Society},
year = {1990},
url = {https://doi.org/10.1109/FSCS.1990.89601},
doi = {10.1109/FSCS.1990.89601},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BussPT90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BussT88,
author = {Samuel R. Buss and
Gy{\"{o}}rgy Tur{\'{a}}n},
title = {Resolution Proofs of Generalized Pigeonhole Principles},
journal = {Theor. Comput. Sci.},
volume = {62},
number = {3},
pages = {311--317},
year = {1988},
url = {https://doi.org/10.1016/0304-3975(88)90072-2},
doi = {10.1016/0304-3975(88)90072-2},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/BussT88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BussH88,
author = {Samuel R. Buss and
Louise Hay},
title = {On truth-table reducibility to {SAT} and the difference hierarchy
over {NP}},
booktitle = {Proceedings: Third Annual Structure in Complexity Theory Conference,
Georgetown University, Washington, D. C., USA, June 14-17, 1988},
pages = {224--233},
publisher = {{IEEE} Computer Society},
year = {1988},
url = {https://doi.org/10.1109/SCT.1988.5282},
doi = {10.1109/SCT.1988.5282},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BussH88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jsyml/Buss87,
author = {Samuel R. Buss},
title = {Polynomial Size Proofs of the Propositional Pigeonhole Principle},
journal = {J. Symb. Log.},
volume = {52},
number = {4},
pages = {916--927},
year = {1987},
url = {https://doi.org/10.2307/2273826},
doi = {10.2307/2273826},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jsyml/Buss87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Buss87,
author = {Samuel R. Buss},
editor = {Alfred V. Aho},
title = {The Boolean Formula Value Problem Is in {ALOGTIME}},
booktitle = {Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing,
1987, New York, New York, {USA}},
pages = {123--131},
publisher = {{ACM}},
year = {1987},
url = {https://doi.org/10.1145/28395.28409},
doi = {10.1145/28395.28409},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Buss87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Buss86a,
author = {Samuel R. Buss},
editor = {Alan L. Selman},
title = {The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic},
booktitle = {Structure in Complexity Theory, Proceedings of the Conference hold
at the University of California, Berkeley, California, USA, June 2-5,
1986},
series = {Lecture Notes in Computer Science},
volume = {223},
pages = {77--103},
publisher = {Springer},
year = {1986},
url = {https://doi.org/10.1007/3-540-16486-3\_91},
doi = {10.1007/3-540-16486-3\_91},
timestamp = {Thu, 02 Feb 2023 13:27:01 +0100},
biburl = {https://dblp.org/rec/conf/coco/Buss86a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Buss85,
author = {Samuel R. Buss},
editor = {Robert Sedgewick},
title = {The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended
Abstract)},
booktitle = {Proceedings of the 17th Annual {ACM} Symposium on Theory of Computing,
May 6-8, 1985, Providence, Rhode Island, {USA}},
pages = {285--290},
publisher = {{ACM}},
year = {1985},
url = {https://doi.org/10.1145/22145.22177},
doi = {10.1145/22145.22177},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Buss85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-21 17:57 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
