All reports by Author Osamu Watanabe:

__
TR19-091
| 7th July 2019
__

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

__
TR19-025
| 28th February 2019
__

Shuichi Hirahara, Osamu Watanabe#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

__
TR17-140
| 11th September 2017
__

Tong Qin, Osamu Watanabe#### An improvement of the algorithm of Hertli for the unique 3SAT problem

__
TR15-198
| 30th November 2015
__

Shuichi Hirahara, Osamu Watanabe#### Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

__
TR14-071
| 7th May 2014
__

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

__
TR13-176
| 8th December 2013
__

Daniel Kane, Osamu Watanabe#### A Short Implicant of CNFs with Relatively Many Satisfying Assignments

Revisions: 1
,
Comments: 1

__
TR12-032
| 4th April 2012
__

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe#### Interval graph representation with given interval and intersection lengths

__
TR12-002
| 4th January 2012
__

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

Revisions: 3

__
TR11-151
| 9th November 2011
__

Valentine Kabanets, Osamu Watanabe#### Is the Valiant-Vazirani Isolation Lemma Improvable?

Revisions: 2

__
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

__
TR09-019
| 10th March 2009
__

Agrawal Manindra, Osamu Watanabe#### One-Way Functions and the Isomorphism Conjecture

__
TR00-081
| 5th September 2000
__

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe#### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

Shuichi Hirahara, Osamu Watanabe

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

Tong Qin, Osamu Watanabe

We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem.

more >>>Shuichi Hirahara, Osamu Watanabe

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>

Daniel Kane, Osamu Watanabe

Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order ... more >>>

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

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 >>>

Valentine Kabanets, Osamu Watanabe

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... 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 >>>

Agrawal Manindra, Osamu Watanabe

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.

It states that all sets complete for NP under polynomial-time many-one

reductions are P-isomorphic to each other. From previous research

it has been widely believed that all NP-complete sets are reducible

each other by one-to-one and length-increasing polynomial-time

reductions, but ...
more >>>

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

In this paper we separate many-one reducibility from truth-table

reducibility for distributional problems in DistNP under the

hypothesis that P neq NP. As a first example we consider the

3-Satisfiability problem (3SAT) with two different distributions

on 3CNF formulas. We show that 3SAT using a version of the

standard distribution ...
more >>>