Akitoshi Kawamura

I moved to another department (within UTokyo) in April 2015. The information on this webpage may be old.

Department of Computer Science, University of Tokyo

Ph.D. (Computer Science), Toronto, June 2011

Research interests and projects

• Computable Analysis
  • Computational Complexity in the Continuous World (KAKENHI Young Scientists A 26700001)
  • Complexity of real functions and operators
• Exploring the Limits of Computation (KAKENHI Innovative Areas, Leader: Osamu Watanabe)
• Resource-bounded randomness and complexity (Kayamori)
• Computation in Mathematical Fluid Dynamics (JSPS-DFG International Research Training Group)
• Quantum Graph Theory and Computation (KAKENHI A, Leader: Hiroshi Imai)
• Optimization Theory on Graphs and Networks (Kawarabayashi Large Graph Project) (In Japanese)
• Computational and discrete geometry

Events etc. (past)

• Dagstuhl Seminar: Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis September 20–25, 2015
• Twelfth International Conference on Computability and Complexity in Analysis (CCA) July 12–15, 2015 (abstracts due March 31)
• Sixteenth International Workshop on Logic and Computational Complexity (LCC) July 4–5, 2015
• 31st International Symposium on Computational Geometry (SoCG) June 25–28, 2015
• IEICE Transactions A: Special Section on Discrete Mathematics and Its Applications June 2015
• Exploring the Limits of Computation
• IEICE-COMP: Theoretical Foundation of Computing

Papers

• Simple strategies versus optimal schedules in multi-agent patrolling (with M. Soejima)
  LA Symposium Summer 2014 (in Japanese)
  CIAC 2015
• Fence patrolling by mobile agents with distinct speeds (with Y. Kobayashi) arXiv preprint
  LA Symposium Summer 2012 (in Japanese)
  ISAAC 2012
  Distributed Computing 28 (2015)
• On minimum- and maximum-weight minimum spanning trees with neighborhoods (with R. Dorrigiv, R. Fraser, M. He, S. Kamali, A. López-Ortiz, and D. Seco)
  WAOA 2012
  Theory of Computing Systems 56 (2015)
• On characterizations of randomized computation using plain Kolmogorov complexity (with S. Hirahara)
  IEICE-COMP 2014-06
  MFCS 2014
• Small complexity classes for computable analysis (with H. Ota)
  MFCS 2014
• A lower bound on opaque sets (with S. Moriyama, Y. Otachi, and J. Pach)
  Preprint, March 2014
• Thin strip graphs (with T. Hayashi, Y. Otachi, H. Shinohara, and K. Yamazaki)
  IEICE-COMP 2014-04
• Function spaces for second-order polynomial time (with A. Pauly)
  CiE 2014
• Weight balancing on boundaries and skeletons (with L. Barba, O. Cheong, J.-L. De Carufel, M. Dobbins, R. Fleischer, M. Korman, Y. Okamoto, J. Pach, Y. Tang, T. Tokuyama, S. Verdonschot, and T. Wang)
  EATCS/LA Workshop Winter 2013 (in Japanese)
  SoCG 2014
• Computational complexity of smooth differential equations (with H. Ota, C. Rösnick, and M. Ziegler)
  EATCS/LA Workshop Winter 2011 (preliminary results, in Japanese)
  MFCS 2012
  Logical Methods in Computer Science 10 (2014)
• The distance 4-sector of two points is unique (with R. Fraser, M. He, A. López-Ortiz, J. I. Munro, and P. K. Nicholson)
  LA Symposium Summer 2011 (in Japanese)
  ISAAC 2013
• Morpion Solitaire 5D: a new upper bound (with T. Okamoto, Y. Tatsu, Y. Uno, and M. Yamato)
  IEICE-COMP 2013-06 (in Japanese)
  CCCG 2013
• Relativizing the NL hierarchy (with H. Ota)
  EATCS/LA Workshop Winter 2012 (in Japanese)
• Uniform polytime computable operators on univariate real analytic functions (with N. Müller, C. Rösnick and M. Ziegler)
  CiE 2012 (informal presentation)
  CCA 2012
• Complexity theory for operators in analysis (with S. Cook)
  EATCS/LA Workshop Winter 2009 (in Japanese)
  STOC 2010
  ACM Transactions on Computation Theory 4 (2012)
• Zone diagrams in Euclidean spaces and in other normed spaces (with J. Matoušek and T. Tokuyama)
  IEICE-COMP 2010-01 (in Japanese)
  SoCG 2010
  Mathematische Annalen 354 (2012)
• On function spaces and polynomial-time computability (PDF)
  Presented at Dagstuhl Seminar 11411, October 2011
• 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)
  IEICE-COMP 2010-01 (in Japanese)
  SoCG 2010
  Computational Geometry 43 (2010)
• Lipschitz continuous ordinary differential equations are polynomial-space complete
  CCC 2009, Best Student Paper
  Computational Complexity 19 (2010)
  (Slides for invited talk at CCA 2012)
• 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)

Travel plans

• February 24: Tokyo, Japan
• March 2–6: Kanazawa, Japan
• March 8–13: Banff, AB, Canada
• March 15–18: Ljubljana, Slovenia
• March 21
• March 22–24: Tokyo, Japan
• May 8: Potsdam, Germany
• May 26: Tokyo, Japan
• July 4–5: Kyoto, Japan
• July 12–15: Tokyo, Japan
• September 20–25: Wadern (Dagstuhl), Germany

Past

Links

Courses

• Computational Complexity (Enshu) Winter 2014
• Advanced Algorithms Summer 2014
• Discrete Mathematics (Enshu) Summer 2014
• A short course on randomness and complexity (Kyoto) Winter 2013
• Computational Complexity (Enshu) Winter 2013
• A short course on Computational Complexity in Analysis (Kyoto) Summer 2013

Coauthors

Y. Akama, L. Barba, O. Cheong, S. A. Cook, J.-L. De Carufel, M. Dobbins, R. Dorrigiv, R. Fleischer, R. Fraser, T. Hayashi, M. He, S. Hirahara, K. Imai, K. Irie, S. Kamali, Y. Kobayashi, M. Korman, A. López-Ortiz, J. Matoušek, S. Moriyama, N. Th. Müller, J. I. Munro, Y. Muramatsu, P. K. Nicholson, T. Okamoto, Y. Okamoto, H. Ota, Y. Otachi, J. Pach, A. Pauly, D. Reem, C. Rösnick, D. Seco, H. Shinohara, F. Steinberg, Y. Tang, Y. Tatsu, H. Thies, T. Tokuyama, Y. Uno, Y. Uwano, S. Verdonschot, T. Wang, M. Yamato, K. Yamazaki, M. Ziegler

Places

• Imai Lab, University of Tokyo
• The ELC Project
• Rutgers and DIMACS
• 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 Lab, Tokyo Institute of Technology
• Tsuiki Lab, Kyoto University
• Research Center for Verification and Semantics, AIST, Japan
• Hagiya Lab, University of Tokyo

Useful websites

• Job postings in Japan: JREC-IN (some but not all faculty positions require Japanese language skills; sometimes they even look for a non-Japanese)