Is Valiant-Vazirani's Isolation Probability Improvable?: Jeffrey Finkelstein, BU (Theory Seminar)

Starts:
2:00 pm on Friday, February 28, 2014
Ends:
4:00 pm on Friday, February 28, 2014
Location:
MCS 137
Abstract: The Isolation Lemma of Valiant and Vazirani [VV86] provides an efficient randomized procedure for isolating a satisfying assignment of a given satisfiable circuit: Given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables such that (i) every satisfying assignment of C' also satisfies C, and (ii) if C is satisfiable, then C' has exactly one satisfying assignment (or witness). The 2011 paper by Dell, Kabanetz, van Melkebeek and Watanabe (cited below) considers the questions of whether it is possible to have an efficient deterministic witness-isolating procedure, and whether we can improve the success probability of the randomized Valiant-Vazirani procedure. "Is Valiant-Vazirani's Isolation Probability Improvable?" http://eccc.hpi-web.de/report/2011/151/