
The Query Complexity of Witness Finding
We study the following information-theoretic witness finding problem: for a hidden nonempty subset W of {0,1}n, how many non-adaptive randomized queries (yes/no questions about W) are needed to guess an element x∈{0,1}n such that x∈W with probability >1/2? Motivated by questions in complexity theory, we prove tight lower bounds with respect to a few different classes of queries: •We show that the monotone query complexity of witness finding is Ω(n2). This matches an O(n2) upper bound from the Valiant-Vazirani Isolation Lemma [8].•We also prove a tight Ω(n2) lower bound for the class of NP queries (queries defined by an NP machine with an oracle to W). This shows that the classic search-to-decision reduction of Ben-David, Chor, Goldreich and Luby [3] is optimal in a certain black-box model.•Finally, we consider the setting where W is an affine subspace of {0,1}n and prove an Ω(n2) lower bound for the class of intersection queries (queries of the form “W∩ S≠ ∅?” where S is a fixed subset of {0,1}n). Along the way, we show that every monotone property defined by an intersection query has an exponentially sharp threshold in the lattice of affine subspaces of {0,1}n.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4606 Distributed computing and systems software
- 0805 Distributed Computing
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics
Citation

Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4606 Distributed computing and systems software
- 0805 Distributed Computing
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics