3 papers
cs.CC2026
Consequences of Polylogarithmic Membership Comparability for SAT
Sebastian Ben Daniel
We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every pol…
cs.CC2026
Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors
Sebastian Ben Daniel
Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator mere…
cs.CC2026
Constant-Probability Witness Isolation Implies
Sebastian Ben Daniel
Valiant and Vazirani isolate a satisfying assignment of a circuit with probability . Dell, Kabanets, van Melkebeek, and Watanabe showed that success above implies $\m…