Tsuyoshi Morioka
I completed my Ph.D. degree in December 2004, and I currently reside in
Japan. I work at
the Systems Development Laboratory of
Hitachi, Ltd.,
and I am currently working in software engineering.
My new email addresses are:
(i) ts.morioka-AT-world-DOT-ocn-DOT-ne-DOT-jp
(private address)
(ii)morioka-AT-sdl-DOT-hitachi-DOT-co-DOT-jp
(work address)
My fields of interest include:
- complexity theory
- propositional proof complexity
- proof theory
- relationship among complexity classes, proof systems, and
first-order theories of Bounded Arithmetic.
But my interests are not limited to these areas. I'm most interested in
using techniques in mathematical logic to prove complexity-theoretic
results.
My adviser was
Prof. Stephen A. Cook .
Research Activities
Logical Approaches to the Complexity of Search Problems:
Proof Complexity, Quantified Propositional Calculus, and
Bounded Arithmetic.
Ph.D Thesis, University of Toronto, 2005.
Quantified Propositional Calculus and a Second-Order Theory
for NC1.
Submitted. 36 page manuscript.
Jointly with Stephen Cook.
Preliminary results have been reported in my presentation at SML'03 (below).
Quantified Propositional Calculus and ALOGTIME.
A contributed talk at the Symposium on Mathematical Logic (SML'03),
Kobe, Japan. Jointly with
Stephen Cook.
click here for a one-page abstract in PDF.
- Relativized NP Search Problems
and Propositional Proof Systems. Accepted for the Nineteenth
IEEE Conference on Computational Complexity (CCC'04).
Jointly with J. Buresh-Oppenheim
. Also available as
ECCC report TR03-084.
- The Relative Complexity of Local Search Heuristics and the
Iteration Principle. Presented at the International Workshop on
Implicit Computational Complexity (
ICC'03).
Also available as
ECCC report TR03-051.
- Bounded and Ordered Satisfiability: Connecting Recognition
with Lambek-style Calculi to Classical Satisfiability Testing.
Proceedings of the Eighth Meeting on the Mathematics of Language
(MOL 8), 2003. Jointly with: Michail Flouris, Lap Chi Lau,
Periklis Papakonstantinou, and Gerald Penn.
- Iteration and the Parity.
A presentation at the Fall School of the
Logic Seminar,
Pec p. Snezkou, the Czech Republic. September 2002.
Joint work with
Joshua Buresh-Oppenheim
on the relative separation of
the complexity classes PPA and PLS via degree
lower bounds for the Nullstellensatz proof system.
- Classification of Search Problems and Their Definability
in Bounded Arithmetic. M.Sc thesis. University of Toronto, 2001.
Available as
ECCC report TR01-82.
Parts of the M.Sc work were presented in the following workshops:
My personal page