National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku
Tokyo 101-8430, Japan
[last name] at nii.ac.jp
I am an assistant professor by special appointment within the Kawarabayashi Large Graph Project at the National Institute of Informatics in Tokyo, Japan.
I completed my PhD at MIT in 2010 under the supervision of Madhu Sudan.
From 2010 to 2012 I was a postdoc in the lab of Osamu Watanabe at the Tokyo Institute of Technology.
I spent the 2014-2015 academic year as a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley.
My research interests lie in complexity theory and logic, specifically the areas of circuit complexity and finite model theory.
I am excited to be joining the University of Toronto as an assistant professor of Mathematics and Computer Science in July 2016!
Together with Rahul Santhanam, I am co-organizing a Workshop on Low-Depth Complexity in May 2016, part of a Special Semester on Computational and Proof Complexity at the Chebyshev Laboratory at St. Petersburg State University.
The Average Sensitivity of Bounded-Depth Formulas
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
(with Rocco Servedio and Li-Yang Tan)
FOCS 2015 (Best Paper Award)
Correlation Bounds Against Monotone NC1
CCC 2015 (Best Paper Award)
Formulas vs. Circuits for Small Distance Connectivity
On the AC0 Complexity of Subgraph Isomorphism
(with Yuan Li and Alexander Razborov)
The Query Complexity of Witness Finding
(with Akinori Kawachi and Osamu Watanabe)
CSR 2014 (Best Paper Award)
The Homomorphism Domination Exponent
(with Swastik Kopparty)
European Journal of Combinatorics, Volume 32, Issue 7: 1097-1114, 2011
Homomorphism Preservation Theorems
Journal of the ACM, Volume 55, Issue 3: 1-53, 2008
Successor-Invariant First-Order Logic on Finite Structures
Journal of Symbolic Logic, Volume 72, Issue 2: 601-619, 2007
Average-Case Complexity of Detecting Cliques
PhD thesis, 2010