Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SEBASTIAN BEN DANIEL:
All reports by Author Sebastian Ben Daniel:

TR26-246 | 11th October 2026
Sebastian Ben Daniel

Constant-Probability Witness Isolation Implies NP in P/poly

A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, ... more >>>


TR26-201 | 10th September 2026
Sebastian Ben Daniel

Obfuscation and the Limits of Witness Isolation

Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and ... more >>>




ISSN 1433-8092 | Imprint