# The query complexity of witness finding

Published

Conference Paper

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 Ω(n 2). This matches an O(n 2) upper bound from the Valiant-Vazirani Isolation Lemma [8]. We also prove a tight Ω(n 2) 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 Ω(n 2) 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 . © 2014 Springer International Publishing Switzerland.

### Full Text

### Duke Authors

### Cited Authors

- Kawachi, A; Rossman, B; Watanabe, O

### Published Date

- January 1, 2014

### Published In

### Volume / Issue

- 8476 LNCS /

### Start / End Page

- 218 - 231

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 13 (ISBN-13)

- 9783319066851

### Digital Object Identifier (DOI)

- 10.1007/978-3-319-06686-8_17

### Citation Source

- Scopus