Akitoshi Kawamura

Ph.D. (Computer Science), University of Toronto, 2011

Research interests and projects

• Computable Analysis
  • Computational Complexity in Analysis (Kakenhi 23700009)
• Randomness and Complexity
• Quantum Graph Theory and Computation (Hiroshi Imai's project)
• Logical aspects of computational complexity
• Computational and discrete geometry

Workshops etc.

• ETH-Japan Workshop on Science and Computing (March 2012)
• IEICE-COMP: Theoretical Foundation of Computing
• Tokyo DMTCS Seminars

Papers

• Complexity of Smooth Ordinary Differential Equations (with Hiroyuki Ota, Martin Ziegler, Carsten Rösnick, in Japanese)
  Presented at the 10th EATCS/LA Workshop on Theoretical Computer Science, January 2012
• On function space representations and polynomial-time computability (PDF, ongoing work)
  Presented at Dagstuhl Seminar 11411, October 2011
• Complexity theory for operators in analysis (with S. Cook)
  STOC 2010
  ACM Transactions on Computation Theory (to appear)
• Zone diagrams in Euclidean spaces and in other normed spaces (with J. Matoušek and T. Tokuyama)
  SoCG 2010
  Mathematische Annalen (in press)
• Generalized semimagic squares for digital halftoning
  Theory of Computing Systems 49 (2011)
• Distance k-sectors exist (with K. Imai, J. Matoušek, D. Reem and T. Tokuyama)
  SoCG 2010
  Computational Geometry 43 (2010)
• Lipschitz continuous ordinary differential equations are polynomial-space complete
  CCC 2009, Best Student Paper
  Computational Complexity 19 (2010)
• VC dimensions of principal component analysis (with Y. Akama, K. Irie and Y. Uwano)
  (contains a simple proof of Warren's bounds on the number of sign patterns of real polynomials)
  Discrete and Computational Geometry 44 (2010)
• Complexity of initial value problems
  Fifth International Workshop on Taylor Model Methods (May 2008)
  Fields Institute Communications (to appear)
• Differential recursion
  ACM Transactions on Computational Logic 10 (2009)

Trip plans

• May 14, 2012: Matsuyama, Japan
• May 29–June 2, 2012: Trier, Germany
• June 21–22, 2012: Sapporo, Japan
• June 24–27, 2012: Cambridge, UK

Past

Links

Courses

• Discrete Mathematics (Enshu) Summer 2012
• Advanced Algorithms Summer 2012
• Computational Complexity (Enshu) Winter 2011
• Discrete Mathematics (Enshu) Summer 2011
• Sogo Kamoku Ippan (Komaba) July 8, 2011

Coauthors

Y. Akama, S. Cook, K. Imai, K. Irie, J. Matoušek, Y. Muramatsu, D. Reem, T. Tokuyama, Y. Uwano

Places

• Imai's Group, University of Tokyo
• Logic Group, TU Darmstadt
• Theory Group, University of Toronto
• Algorithms and Complexity Group, University of Waterloo
• Theory of Combinatorial Algorithms Group, ETH Zürich
• Watanabe's Group, Tokyo Institute of Technology
• Tsuiki's Group, Kyoto University
• Research Center for Verification and Semantics, AIST, Japan
• Hagiya's Group, University of Tokyo

Useful websites

• List of Theory people in Japan (this is a webpage of a grant project that ended in 2008; not comprehensive or up to date)
• Job postings in Japan: JREC-IN (some but not all faculty positions require Japanese language skills; sometimes they even explicitly look for a non-Japanese)
• Tokyo tourist info by T. Nishida