I completed my Ph.D. degree in December 2004, and I currently reside in
Japan. I work at
the Systems Development Laboratory of
and I am currently working in software engineering.
My new email addresses are:
My fields of interest include:
But my interests are not limited to these areas. I'm most interested in
using techniques in mathematical logic to prove complexity-theoretic
- complexity theory
- propositional proof complexity
- proof theory
- relationship among complexity classes, proof systems, and
first-order theories of Bounded Arithmetic.
My adviser was
Prof. Stephen A. Cook .
My personal page
Logical Approaches to the Complexity of Search Problems:
Proof Complexity, Quantified Propositional Calculus, and
Ph.D Thesis, University of Toronto, 2005.
Quantified Propositional Calculus and a Second-Order Theory
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
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 (
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
Pec p. Snezkou, the Czech Republic. September 2002.
Joint work with
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.
ECCC report TR01-82.
Parts of the M.Sc work were presented in the following workshops: