ECCC-Report TR12-002https://eccc.weizmann.ac.il/report/2012/002Comments and Revisions published for TR12-002en-usMon, 30 Apr 2012 03:34:11 +0300
Revision 3
| Query Complexity and Error Tolerance of Witness Finding Algorithms |
Akinori Kawachi,
Benjamin Rossman,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2012/002#revision3We 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\}$, 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\}$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.
Our results show that the witness finding problem requires $\Omega(n^2)$ non-adaptive queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new witness finding algorithm that achieves an improved error tolerance of $O(1/n)$ with $O(n^2)$ non-adaptive queries. Further, we investigate a list-decoding version of the witness finding problem, where a witness is unique, i.e., $|W|=1$, and answers from the oracle may contain some errors. For this setting, it has been known that an improved version of the Goldreich-Levin algorithm with $O(n/\varepsilon^2)$ non-adaptive queries and $O(1/\varepsilon^2)$ list size solves the problem with any $(1/2-\varepsilon)$-error bounded oracle. We show that this query complexity is optimal up to a constant factor (if we want to keep the list size polynomially bounded) even if queries are adaptive.Mon, 30 Apr 2012 03:34:11 +0300https://eccc.weizmann.ac.il/report/2012/002#revision3
Revision 2
| Query Complexity and Error Tolerance of Witness Finding Algorithms |
Akinori Kawachi,
Benjamin Rossman,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2012/002#revision2We 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$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.
Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.Mon, 23 Apr 2012 02:55:26 +0300https://eccc.weizmann.ac.il/report/2012/002#revision2
Revision 1
| Query Complexity and Error Tolerance of Witness Finding Algorithms |
Akinori Kawachi,
Benjamin Rossman,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2012/002#revision1We 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$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.
Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.Mon, 23 Apr 2012 00:42:38 +0300https://eccc.weizmann.ac.il/report/2012/002#revision1
Paper TR12-002
| Query Complexity and Error Tolerance of Witness Finding Algorithms |
Akinori Kawachi,
Benjamin Rossman,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2012/002We 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$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.
Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.Fri, 06 Jan 2012 05:11:35 +0200https://eccc.weizmann.ac.il/report/2012/002