Sebastian Ben Daniel

Obfuscation and the Limits of Witness Isolation: Affine Tests and Membership-Query Bounds

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

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 merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. O...

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

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $\Omega(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ and asked about the range in between. We show that every positive constant already implies the colla...