Samuel R. Buss

dblp:b/SamuelRBuss · also Sam Buss · DBLP profile ↗
← Back
4ranked-venue papers in the field
3as first author
2since 2021 · last 2026
0000-0003-3837-334XORCID · verified

Domains — venue-derived; a paper can count in several

Other / Interdisciplinary · 4 (3 first)
YearPublicationVenuePosition
2026 A simple supercritical tradeoff between size and height in resolution
Samuel R. Buss, Neil Thapen
Inf. Process. Lett.1
2024 Regular resolution effectively simulates resolution
abstract
Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist sequences of formulas that require exponential-size proofs in regular resolution while admitting polynomial-size proofs in resolution. Thus, with respect to the usual notion of simulation, regular resolution is separated from resolution. An alternative, and weaker, notion for comparing proof systems is that of an “effective simulation,” which allows the translation of the formula along with the proof when moving between proof systems. We prove that regular resolution is equivalent to resolution under effective simulations. As a corollary, we recover in a black-box fashion a recent result on the hardness of automating regular resolution.
Samuel R. Buss, Emre Yolcu
Inf. Process. Lett.1
1994 Size-Depth Tradeoffs for Boolean Fomulae
Maria Luisa Bonet, Samuel R. Buss
Inf. Process. Lett.2
1992 The Graph of Multiplication is Equivalent to Counting
Samuel R. Buss
Inf. Process. Lett.1