Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Benjamin Rossman:

TR12-002 | 4th January 2012
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Query Complexity and Error Tolerance of Witness Finding Algorithms

Revisions: 3

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. ... more >>>

ISSN 1433-8092 | Imprint