Mitsunori Ogiwara

University of Electro-Communications — Japan

Computer Science · Physical Sciences

14h-index729citations27works0.02yr avg
OpenAlex↗Google Scholar↗Lab page↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Complexity and Algorithms in Graphs(17), Advanced Graph Theory Research(9), Cryptography and Data Security(6), semigroups and automata theory(6), Computability, Logic, AI Algorithms(6)

Publications27 total

How hard are sparse sets?
2003· 52 cited
P-selective sets, and reducing search to decision vs. self-reducibility
2002· 20 cited
On closure properties of Hash P in the context of PF (omicron) Hash P
2002
Counting classes are at least as hard as the polynomial-time hierarchy
2002· 16 cited
A complexity theory for feasible closure properties
2002· 18 cited
On one query, self-reducible sets
2002· 26 citedOpen Access
Relating equivalence and reducibility to sparse sets
2002· 9 cited
On polynomial time bounded truth-table reducibility of NP sets to sparse sets
2002· 3 cited
Random Polynomial Time Computable Functions
2000
Generalized theorems on relationships among reducibility notions to certain complexity classes
Theory of Computing Systems·1994· 10 cited
NCk(NP)=AC k−1(NP)
Lecture notes in computer science·1994· 4 cited
A relationship between difference hierarchies and relativized polynomial hierarchies
Theory of Computing Systems·1993· 53 cited
Selectivity: Reductions, Nondeterminism, and Function Classes
1993· 5 cited
A complexity theory for feasible closure properties
Journal of Computer and System Sciences·1993· 80 cited
Is #P Closed Under Subtraction?
WORLD SCIENTIFIC eBooks·1993· 8 cited
On sparse hard sets for counting classes
Theoretical Computer Science·1993· 17 cited
On Using Oracles That Compute Values
1993
On closure properties of #P in the context of PF ○ #P
Structure in Complexity Theory Annual Conference·1993· 1 cited
On using oracles that compute values
Lecture notes in computer science·1993· 27 cited
Relating Equivalence and Reducibility to Sparse Sets
SIAM Journal on Computing·1992· 29 cited
page 1 of 2Next →

Frequent Co-authors

Osamu Watanabe(9), Lane A. Hemachandra(9), Thomas Thierauf(5), Seinosuke Toda(4), Antoni Lozano(4), Alan L. Selman(3), Yenjo Han(2), Johannes Köbler(2), M. Mundhenk(2), Uwe Schöning(2), Riccardo Silvestri(2), Eric Allender(2), Steve Homer(2), Ashish V. Naik(2), Richard Beigel(1), Richard Chang(1), V. Arvind(1), V. Arvind(1), Stephen Fenner(1), Lane A. Hemaspaandra(1)