Skip to main content
Journal cover image

The query complexity of witness finding

Publication ,  Conference
Kawachi, A; Rossman, B; Watanabe, O
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2014

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.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783319066851

Publication Date

January 1, 2014

Volume

8476 LNCS

Start / End Page

218 / 231

Related Subject Headings

  • Artificial Intelligence & Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kawachi, A., Rossman, B., & Watanabe, O. (2014). The query complexity of witness finding. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8476 LNCS, pp. 218–231). https://doi.org/10.1007/978-3-319-06686-8_17
Kawachi, A., B. Rossman, and O. Watanabe. “The query complexity of witness finding.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8476 LNCS:218–31, 2014. https://doi.org/10.1007/978-3-319-06686-8_17.
Kawachi A, Rossman B, Watanabe O. The query complexity of witness finding. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. p. 218–31.
Kawachi, A., et al. “The query complexity of witness finding.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8476 LNCS, 2014, pp. 218–31. Scopus, doi:10.1007/978-3-319-06686-8_17.
Kawachi A, Rossman B, Watanabe O. The query complexity of witness finding. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. p. 218–231.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783319066851

Publication Date

January 1, 2014

Volume

8476 LNCS

Start / End Page

218 / 231

Related Subject Headings

  • Artificial Intelligence & Image Processing