Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Spencer, J.: The Probablistic Method, 3rd edn. Wiley (2008)
Bellare, M., Goldwasser, S.: The complexity of decision versus search. SIAM Journal on Computing 23, 97–119 (1994)
Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average-case complexity. Journal of Computer and System Sciences 44(2), 193–219 (1992)
Bollobás, B., Thomason, A.G.: Threshold functions. Combinatorica 7(1), 35–38 (1987)
Chowdhury, A., Patkos, B.: Shadows and intersections in vector spaces. J. of Combinatorial Theory, Ser. A 117, 1095–1106 (2010)
Cover, T., Thomas, J.: Elements of Information Theory. Wiley Interscience, New York (1991)
Dell, H., Kabanets, V., van Melkebeek, D., Watanabe, O.: Is the Valiant-Vazirani isolation lemma improvable? In: Proc. 27th Conference on Computational Complexity, pp. 10–20 (2012)
Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. Theoretical Computer Science 47, 85–93 (1986)
Yao, A.C.: Probabilistic computations: toward a unified measure of complexity. In: Proc. of the 18th IEEE Sympos. on Foundations of Comput. Sci., pp. 222–227. IEEE (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Kawachi, A., Rossman, B., Watanabe, O. (2014). The Query Complexity of Witness Finding. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)