All reports by Author Mitsunori Ogihara:

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR02-016
| 30th January 2002
__

Alina Beygelzimer, Mitsunori Ogihara#### On the Enumerability of the Determinant and the Rank

__
TR01-061
| 13th July 2001
__

Mitsunori Ogihara, Seinosuke Toda#### The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

__
TR96-027
| 20th February 1996
__

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

__
TR96-024
| 21st March 1996
__

Eric Allender, Robert Beals, Mitsunori Ogihara#### The complexity of matrix rank and feasible systems of linear equations

__
TR96-014
| 14th February 1996
__

Mitsunori Ogihara#### Sparse Hard Sets for P Yields Space-Efficient Algorithms

__
TR96-013
| 14th February 1996
__

Mitsunori Ogihara#### The PL Hierarchy Collapses

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>Alina Beygelzimer, Mitsunori Ogihara

We investigate the complexity of enumerative approximation of

two elementary problems in linear algebra, computing the rank

and the determinant of a matrix. In particular, we show that

if there exists an enumerator that, given a matrix, outputs a

list of constantly many numbers, one of which is guaranteed to

more >>>

Mitsunori Ogihara, Seinosuke Toda

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the

roblem of counting the number of s-t paths in graphs (both in the case

of directed graphs and in the case of undirected graphs) is complete

for #P under polynomial-time one-Turing reductions (namely, some

post-computation is needed to ...
more >>>

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Is there an NP function that, when given a satisfiable formula

as input, outputs one satisfying assignment uniquely? That is, can a

nondeterministic function cull just one satisfying assignment from a

possibly exponentially large collection of assignments? We show that if

there is such a nondeterministic function, then the polynomial ...
more >>>

Eric Allender, Robert Beals, Mitsunori Ogihara

We characterize the complexity of some natural and important

problems in linear algebra. In particular, we identify natural

complexity classes for which the problems of (a) determining if a

system of linear equations is feasible and (b) computing the rank of

an integer matrix, ...
more >>>

Mitsunori Ogihara

In 1978, Hartmanis conjectured that there exist no sparse complete sets

for P under logspace many-one reductions. In this paper, in support of

the conjecture, it is shown that if P has sparse hard sets under logspace

many-one reductions, then P is included in DPSPACE[log^2 n].

Mitsunori Ogihara

It is shown that the PL hierarchy defined in terms of the

standard Ruzzo-Simon-Tompa relativization collapses to PL.