English
電気通信大学 
大学院情報理工学研究科、情報理工学域 
情報・ネットワーク工学専攻、Ⅰ類 (情報系) 

准教授 
垂井 淳 
タルイ ジュン 
JUN TARUI 

Fax.0424-443-5293  
個人ウェブサイトはこちら  

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

学歴
東京大学  教育学部  1985/03  卒業 
University of Rochester,  Department of Computer Science  博士  1991/09  修了 

学位
MS in Computer Science  University of Rochester  1987 
MA in Mathematics  University of Rochester  1991 
PhD in Computer Science  University of Rochester  1992 

海外教育研究活動
Lecturer, Deparment of Computer Science, University of Warwick  1991-1993  United Kingdom 
Research Associate, Department of Computer Science, University of Rochester  1985-1991  USA 
詳細表示...

現在の専門分野
情報学基礎理論 
数理情報学 

現在の研究課題
計算量理論: Computational Complexity  P =? BPP L =? NL P =? NP  2001/01/01-現在 
計算論的学習理論: 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?! 

著書
著書  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 
詳細表示...

論文
国際会議プロシーディングス等  有  Depth-First Search Using O(n) bits  共著  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 
解説  無  P≠NP予想,代数的計算量  垂井淳  数学セミナー12月号:P≠NP予想特集号,2013  18-22  2013/12 
一般論文  有  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 
一般論文  有  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 
一般論文  有  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 
詳細表示...

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

所属学協会
ACM  2002-現在 
IEEE  2003-2003 
EATCS  2003-2003 
LA シンポジウム  2003-2003 
電子情報通信学会 
詳細表示...