Sebastian Ben Daniel

collaborators

Showing cs.CCShow all

3 papers · 1 filter

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 $NP \subseteq P/poly$

Sebastian Ben Daniel

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $Ω (1/ n)$ . Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\m…

Consequences of Polylogarithmic Membership Comparability for SAT

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

Constant-Probability Witness Isolation Implies NP⊆P/poly

Constant-Probability Witness Isolation Implies $NP \subseteq P/poly$