日本語
The University of Electro-Communications 
Graduate School of Informatics and Engineering, School of Informatics and Engineering 
Department of Computer and Network Engineering, Cluster I (Informatics and Computer Engineering) 

Associate Professor 
JUN TARUI 

Fax.0424-443-5293  
Personal website  

Career
電気通信大学情報理工学研究科  准教授  2010/04/01-Present 
電気通信大学電気通信学研究科  准教授  2008/05/01-2010/03/31 
電気通信大学電気通信学部  講師  1993/10/01-2008/04/30 
University of Warwick (United Kingdom)  Lecturer  1991/10/01-1993/09/30 

Academic background
The University of Tokyo  Faculty of Education  1985/03  Graduated 
University of Rochester  Department of Computer Science  Doctoral program  1991/09  Completed 

Academic degrees
MS in Computer Science  University of Rochester  1987 
MA in Mathematics  University of Rochester  1991 
PhD in Computer Science  University of Rochester  1992 

Education and research activities in foreign countries
Lecturer, Deparment of Computer Science, University of Warwick  1991-1993  United Kingdom 
Research Associate, Department of Computer Science, University of Rochester  1985-1991  USA 
View details...

Current research areas
Theory of informatics 
Mathematical informatics 

Current research subjects
Computational Complexity  P =? BPP L =? NL P =? NP  2001/01/01-Present 
Computational Learning Theory  DNFs Efficiently PAC-Learnable? 
Trying to understand the nature and the difficulty of the P vs NP problem.  P vs NP: Where are we now? What tools do we need? Answer-Solution:When? 

Published books
Book  Proceedings of TAMC2011: Theory and Applications of Models of Computation, 8th Annual Conference (Tokyo, Japan, May 23-25, 2011).  Mitsunori Ogihara and Jun Tarui (Editors)  Springer-Verlag  2011/05 
View details...

Published papers
International conference proceedings, etc.  Yes  Depth-First Search Using O(n) bits  Joint  T. Asano, T. Izumi, M. Kiyomi, M. Konagaya, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui, R. Uehara  Lecture Notes in Computer Science vol. 8889: Proceedings of ISAAC2014: the 33rd International Symposium on Algorithms and Computation, Springer. doi: 10.1007/978-3-319-13075-0_44  8889, 553-564  2014/12 
Tutorial  No  P≠NP予想,代数的計算量  垂井淳  数学セミナー12月号:P≠NP予想特集号,2013  18-22  2013/12 
Paper  Yes  Learning Boolean Functions in AC^0^ on Attribute and Classification Noise  A. Miyata, J. Tarui, and E. Tomita  Theoretical Computer Science. DOI:10.1016/j.tcs.2011.04.047  412/ 35, 4650-4660  2011 
Paper  Yes  A Well-Mixed Function with Circuit Complexity 5n: Tightness of the Lachish-Raz-type Bounds  K. Amano and J. Tarui  Theoretical Computer Science. DOI:10.1016/j.tcs.2010.12.040  412/ 18, 1646-1651  2011 
Paper  Yes  Smallest Formulas for the Parity of 2^k^ Variables Are Essentially Unique  Jun Tarui  Theoretical Computer Science. DOI: 10.1016/j.tcs.2010.03.022  411/ 26-28, 2623-2627  2010 
View details...

Research presentations
Other speech or lecture  ブログは研究に役立つか?どのように?  国際学術情報流通基盤整備事業(SPARC Japan)2015年第3回セミナー招待講演(会場:国立情報学研究所)  No  垂井淳  2016/01/19 
Invited lecture for a domestic conference  計算の複雑さと証明の複雑さ  京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012)  No  垂井淳  2012/09 
Invited lecture for a domestic conference  計算量理論のいろんな話題  計算量理論秋学校講演(熱海, 9月24日--26日, 2012)  No  垂井淳  2012/09 
Invited lecture for an international conference  Complexity of Finding a Duplicate in a Stream  NII Shonan Meeting: "Large-Scale Distributed Computation"  No  Jun Tarui  2012/01 
Invited lecture for a domestic conference  DeolalikarのP≠NP論文をめぐって  No  垂井淳  2010 
View details...

Memberships of academic societies
ACM  2002-Present 
IEEE  2003-2003 
EATCS  2003-2003 
LA シンポジウム  2003-2003 
電子情報通信学会 
View details...