All reports by Author Akinori Kawachi:

__
TR12-002
| 4th January 2012
__

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe#### Query Complexity and Error Tolerance of Witness Finding Algorithms

Revisions: 3

__
TR09-146
| 29th December 2009
__

Dan Gutfreund, Akinori Kawachi#### Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

__
TR09-023
| 12th March 2009
__

Akinori Kawachi, Osamu Watanabe#### Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems

__
TR06-020
| 10th February 2006
__

Akinori Kawachi, Tomoyuki Yamakami#### Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

We 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$. ... more >>>

Dan Gutfreund, Akinori Kawachi

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

Akinori Kawachi, Osamu Watanabe

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

Akinori Kawachi, Tomoyuki Yamakami

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.

Our technical tool is ...
more >>>