@book{CTT100715536,
  author = {渡辺 治},
  title = {コンピュータサイエンス －計算を通して世界を観るー},
  publisher = {丸善サイエンスパレット},
  year = 2015,
}

@book{CTT100721922,
  author = {渡辺 治},
  title = {今度こそわかるＰ≠ＮＰ予想},
  publisher = {講談社サイエンティフィク},
  year = 2014,
}

@book{CTT100633312,
  author = {OSAMU WATANABE},
  title = {Randomness in Algorithms},
  publisher = {World Scientific},
  year = 2011,
}

@book{CTT100721918,
  author = {T. Asano and Nakano and Y. Okamoto and O. Watanabe},
  title = {Algorithm and Computation, Proc. 22nd International Symposium on Algorithms and Computation (ISAAC'11)},
  publisher = {Springer-Verlag},
  year = 2011,
}

@book{CTT100721920,
  author = {O. Watanabe},
  title = {Randomness in Algorithms (Chap.24 of Randomness through Computation (H. Zenil ed.))},
  publisher = {World Scientific},
  year = 2011,
}

@book{CTT100721916,
  author = {O. Watanabe and T. Zeugmann},
  title = {Proc. 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10)},
  publisher = {Springer-Verlag},
  year = 2010,
}

@book{CTT100604584,
  author = {OSAMU WATANABE and Thomas Zeugmann},
  title = {Proceedings of 5th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA'10)},
  publisher = {},
  year = 2009,
}

@book{CTT100564595,
  author = {渡辺治 and 北野晃朗 and 木村泰紀 and 谷口雅治},
  title = {数学の言葉と論理},
  publisher = {朝倉書店},
  year = 2008,
}

@book{CTT100575580,
  author = {Michael Sipser and 太田和夫 and 阿部正幸 and 植田広樹 and 田中圭介 and 藤岡淳 and 渡辺治},
  title = {計算理論の基礎 [原著第2版] 1. オートマトンと言語},
  publisher = {共立出版},
  year = 2008,
}

@book{CTT100575582,
  author = {Michael Sipser and 太田和夫 and 阿部正幸 and 植田広樹 and 田中圭介 and 藤岡淳 and 渡辺治},
  title = {計算理論の基礎 [原著第2版] 3. 複雑さの理論},
  publisher = {共立出版},
  year = 2008,
}

@book{CTT100575581,
  author = {Michael Sipser and 太田和夫 and 阿部正幸 and 植田広樹 and 田中圭介 and 藤岡淳 and 渡辺治},
  title = {計算理論の基礎 [原著第2版] 2. 計算可能性の理論},
  publisher = {共立出版},
  year = 2008,
}

@book{CTT100556925,
  author = {金森 敬文 and 畑埜 晃平 and 渡辺 治},
  title = {ブースティング --- 学習アルゴリズムの設計技法},
  publisher = {森北出版},
  year = 2006,
}

@book{CTT100393218,
  author = {松田裕幸 and 渡辺治},
  title = {スーパーコン甲子園},
  publisher = {日本評論社},
  year = 2005,
}

@book{CTT100556912,
  author = {A. Sharma and O Watanabe},
  title = {Algorithmic Learning Theory},
  publisher = {Elsevier},
  year = 2002,
}

@book{CTT100454751,
  author = {渡辺治},
  title = {教養としてのコンピュータ・サイエンス},
  publisher = {サイエンス社},
  year = 2001,
}

@book{CTT100556911,
  author = {A. Sharma and O Watanabe},
  title = {Special Issue on Algorithmic Learning Theory},
  publisher = {Elsevier},
  year = 2001,
}

@book{CTT100395082,
  author = {太田和夫 and 渡辺治},
  title = {計算理論の基礎},
  publisher = {共立出版},
  year = 2000,
}

@book{CTT100556910,
  author = {O. Watanabe and T. Yokomori},
  title = {Proc. 10th International Conference on Algorithmic Learning Theory},
  publisher = {Springer-Verlag},
  year = 1999,
}

@book{CTT100546893,
  author = {太田和夫 and 黒澤馨 and 渡辺治},
  title = {情報セキュリtィの科学},
  publisher = {講談社ブルーバックス},
  year = 1995,
}

@book{CTT100721912,
  author = {太田 和夫 and 黒澤 肇 and 渡辺 治},
  title = {情報セキュリティーの科学： マジック・プロトコルへの招待},
  publisher = {講談社ブルーバックス},
  year = 1995,
}

@book{CTT100556924,
  author = {渡辺 治},
  title = {コンピュータ基礎理論ハンドブック I : アルゴリズムと複雑さ},
  publisher = {丸善},
  year = 1994,
}

@book{CTT100453227,
  author = {Seinosuke Toda and Osamu Watanabe},
  title = {Some structural analysis on the complexity of inverse functions},
  publisher = {Mathematical Systems Theory},
  year = 1993,
}

@book{CTT100394573,
  author = {OSAMU WATANABE},
  title = {Kolgomorov Complexity and Computational Complexity},
  publisher = {Springer-Verlag},
  year = 1992,
}

@book{CTT100453225,
  author = {渡辺治},
  title = {計算可能性・計算の複雑さ入門},
  publisher = {近代科学社},
  year = 1992,
}

@book{CTT100556904,
  author = {O. Watanabe and T. Ibaraki},
  title = {Special Section on Theoretical Foundation of Computing},
  publisher = {IEICE},
  year = 1992,
}

@book{CTT100556909,
  author = {O. Watanabe},
  title = {Kolmogorov Complexity: Theory and Relations to Computational Complexity},
  publisher = {Springer-Verlag},
  year = 1992,
}

@article{CTT100809310,
  author = {Ryo Ashida and Sebastian Kuhnert and Osamu Watanabe},
  title = {A Space-Efficient Separator Algorithm for Planar Graphs},
  journal = {IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences},
  year = 2019,
}

@article{CTT100767956,
  author = {Suguru Tamaki and Osamu Watanabe},
  title = {Local Restrictions from the Furst-Saxe-Sipser Paper},
  journal = {Theory of Computing Systems},
  year = 2017,
}

@article{CTT100759220,
  author = {Akinori Kawachi and Benjamin Rossman and Osamu Watanabe},
  title = {The Query Complexity of Witness Finding},
  journal = {Theory of Computing Systems},
  year = 2016,
}

@article{CTT100715512,
  author = {Daniel Kane and Osamu Watanabe},
  title = {A short implicant of a CNF formula with many satisfying assignments},
  journal = {Algorithmica},
  year = 2016,
}

@article{CTT100715483,
  author = {Johannes Köbler and Sebastian Kuhnert and Osamu Watanabe},
  title = {Interval graph representation with given interval and intersection lengths},
  journal = {Journal of Discrete Algorithms},
  year = 2015,
}

@article{CTT100716229,
  author = {Osamu Watanabe},
  title = {Message passing algorithms for MLS-3LIN problem},
  journal = {Algorithmica},
  year = 2013,
}

@article{CTT100716230,
  author = {Holger Dell and Valentine Kabanets and Dieter van Melkebeek and Osamu Watanabe},
  title = {Is Valiant-Vazirani's isolation probability improvable?},
  journal = {computational complexity},
  year = 2013,
}

@article{CTT100719744,
  author = {O. Watanabe},
  title = {Introduction of the ELC project},
  journal = {},
  year = 2013,
}

@article{CTT100719711,
  author = {O. Watanabe},
  title = {Perturbed k-linear-equation problems},
  journal = {Workshop at IIT Kanpur},
  year = 2012,
}

@article{CTT100716228,
  author = {A. Kawachi and H. Tanaka and O. Watanabe},
  title = {Estimating the Gowers norm of modulo functions over prime fields},
  journal = {IEICE TRANSACTIONS on Information and Systems},
  year = 2012,
}

@article{CTT100716227,
  author = {Amin Coja-Oghlan and Mikael Onsjö and Osamu Watanabe},
  title = {Propagation connectivity of random hypergraphs},
  journal = {The Electronic Journal of Combinatorics},
  year = 2012,
}

@article{CTT100716226,
  author = {Takeya Shigezumi and Yushi Uno and Osamu Watanabe},
  title = {A new model for a scale-free hierarchical structure of isolated clique},
  journal = {Journal of Graph Algorithms and Applications},
  year = 2011,
}

@article{CTT100633311,
  author = {T. Ando and Y. Kabashima and H. Takahashi and O. Watanabe and M. Yamamoto},
  title = {Spectral analysis of random sparse matrices},
  journal = {IEICE Transactions on Information and Systems},
  year = 2011,
}

@article{CTT100615415,
  author = {Toshiya Itoh and Osamu Watanabe},
  title = {Weighted Random Popular Matchings},
  journal = {Random Structures and Algorithms},
  year = 2010,
}

@article{CTT100633313,
  author = {Y. Soejima and A. Kishimoto and O. Watanabe},
  title = {Evaluating root parallelization in Go},
  journal = {IEEE Transactions on Computational Intelligence and AI in Games},
  year = 2010,
}

@article{CTT100604588,
  author = {OSAMU WATANABE and Masaki Yamamoto},
  title = {Average-case analysis for the MAX-2SAT problem},
  journal = {Theoretical Computer Science},
  year = 2010,
}

@article{CTT100597646,
  author = {Edith Hemaspaandra and Lane Hemaspaandra and Till Tantau and OSAMU WATANABE},
  title = {On the complexity of kings},
  journal = {Theoretical Computer Science},
  year = 2010,
}

@article{CTT100719695,
  author = {渡辺 治},
  title = {理論研究の役割（学会５０周年企画，情報処理技術の未来地図）},
  journal = {情報処理学会誌},
  year = 2010,
}

@article{CTT100719700,
  author = {渡辺 治},
  title = {情報科学技術は人類の言葉},
  journal = {情報科学教育学会全国大会},
  year = 2010,
}

@article{CTT100597647,
  author = {Mikael Onsjö and OSAMU WATANABE},
  title = {Finding most likely solutions},
  journal = {Theory of Computing Systems},
  year = 2009,
}

@article{CTT100591712,
  author = {Naoto Miyoshi and Takeya Shigezumi and Ryuhei Uehara and Osamu Watanabe},
  title = {Scale free interval graphs},
  journal = {Theoretical Computer Science},
  year = 2009,
}

@article{CTT100590418,
  author = {飯田勝吉 and 新里卓史 and 伊東利哉 and 渡辺治},
  title = {キャンパス共通認証認可システムの構築と運用},
  journal = {電子情報通信学会},
  year = 2009,
}

@article{CTT100604577,
  author = {Jose Balcazar and Yang Dai and Junichi Tanaka and OSAMU WATANABE},
  title = {Provably fast training algorithms for support vector machines},
  journal = {Theory Computing Systems},
  year = 2008,
}

@article{CTT100548533,
  author = {Thomas Hofmeister and Uwe Schoning and Rainer Schuler and Osamu Watanabe},
  title = {Randomized algorithms for 3-SAT},
  journal = {Theoretical Computer Science},
  year = 2007,
}

@article{CTT100548532,
  author = {JinYi Cai and Osamu Watanabe},
  title = {Random access to advice strings and collapsing result},
  journal = {Algorithmica},
  year = 2006,
}

@article{CTT100555861,
  author = {S. Balaji and H.M. Mahmoud and O. Watanabe},
  title = {Distributions in the Ehrenfest process},
  journal = {Statistics and Probability Letters},
  year = 2006,
}

@article{CTT100393217,
  author = {Osamu Watanabe},
  title = {Pseudo expectation: A tool for analyzing local search algorithms},
  journal = {Progress of Theoretical Physics, Supplement},
  year = 2005,
}

@article{CTT100555860,
  author = {R. Kato and O. Watanabe},
  title = {Substring search and repeat search using factor oracles},
  journal = {Information Processing Letters},
  year = 2005,
}

@article{CTT100395085,
  author = {Osamu Watanabe},
  title = {Sequential sampling techniques for algorithmic learning theory},
  journal = {Theoretical Computer Science},
  year = 2005,
}

@article{CTT100387520,
  author = {Jin-Yi Cai and Osamu Watanabe},
  title = {Relativized collapsing between BPP and PH under stringent oracle access},
  journal = {Information Processing Letters},
  year = 2004,
}

@article{CTT100387521,
  author = {Jin-Yi Cai and Osamu Watanabe},
  title = {On proving circuit lower bounds against the polynomial-time hierarchy},
  journal = {SIAM Journal on Computing},
  year = 2004,
}

@article{CTT100711394,
  author = {S. Aida and M. Crasmaru and K. Regan and O. Watanabe},
  title = {Games with a uniqueness property},
  journal = {Theory of Comput. Systems},
  year = 2003,
}

@article{CTT100467956,
  author = {T. Hoffmaister and U. Schoening and R. Schuler and O. Watanabe},
  title = {A Probabilistic 3-SAT Algorithm Further Improved},
  journal = {Proc. 19th Symposium on Theoretical Aspects of Computer Science (STACS'02)},
  year = 2002,
}

@article{CTT100467957,
  author = {S. Aida and M. Crasmaru and K. Regan and O.Watanabe},
  title = {Games with a uniqueness property },
  journal = {Proc. 19th Symposium on Theoretical Aspects of Computer Science },
  year = 2002,
}

@article{CTT100489359,
  author = {S. Aida and R. Schuler and T. Tsukiji and O. Watanabe},
  title = {The difference between polynominal-time many-one and truth-table reducibilities on distributional problems},
  journal = {Theory of Comput. Systems},
  year = 2002,
}

@article{CTT100454501,
  author = {K. Okamoto and O. Watanabe},
  title = {Deterministic application of Grover's quantum search algorithm},
  journal = {Proc. 7th Annual Int'l Conf. on Computing and Combinatorics},
  year = 2001,
}

@article{CTT100546894,
  author = {Jose Balcazar and Dai Yang and OSAMU WATANABE},
  title = {A random sampling technique for training support vector machines: for primal-form maximal-margin classifiers},
  journal = {Proc. 12th Int'l Conference on Algorithmic Learning Theory, Lecture Notes in AI, Springer},
  year = 2001,
}

@article{CTT100454733,
  author = {S. Aida and R. Schuler and T. Tsukiji and O. Watanabe},
  title = {On the difference between polynomial-time many-one and truth-table reduciblities on distributional problems},
  journal = {Proc. 18th Int'l Sympos. on Theoretical Aspects of Computer Science},
  year = 2001,
}

@article{CTT100462080,
  author = {OSAMU WATANABE},
  title = {How can computer science contribute to knowlede discovery?},
  journal = {Proc. SOFSEM 2001, Lecture Notes in Computer Scinece, Springer},
  year = 2001,
}

@article{CTT100555862,
  author = {W. Lindner and R. Schuler and O. Watanabe},
  title = {Resource-bounded measure and learnability},
  journal = {Theory of Comput. Systems},
  year = 2000,
}

@article{CTT100718911,
  author = {O. Watanabe},
  title = {Sequential sampling techniques for algorithmic learning theory},
  journal = {Proc. 11th International Conference on Algorithmic Learning Theory (ALT'00)},
  year = 2000,
}

@article{CTT100446769,
  author = {OSAMU WATANABE},
  title = {Simple sampling techniques for discovery science},
  journal = {IEICE Trans. Information and Systems},
  year = 2000,
}

@article{CTT100555865,
  author = {望月 厚 and 元木 光雄 and 渡辺 治},
  title = {３充足可能性判定問題３ＳＡTの正例題生成手法の解析},
  journal = {情報処理学会論文誌},
  year = 1998,
}

@article{CTT100555863,
  author = {J. Kobler and O.Watanabe},
  title = {New collapse consequence of NP having small circuits},
  journal = {SIAM Journal on Computing},
  year = 1998,
}

@article{CTT100555864,
  author = {L. Hemaspaandra and Z. Jiang and J. Rothe and O. Watanabe},
  title = {Boolean operations, joins and the extended low hierarchy},
  journal = {Theoretical Computer Science},
  year = 1998,
}

@article{CTT100555868,
  author = {L. Hemaspaandra and Z. Jiang and J. Rothe and O. Watanabe},
  title = {Pollynomial-time multi-selectivity},
  journal = {Journal of Universal Computer Science},
  year = 1997,
}

@article{CTT100555867,
  author = {C. Domingo and T. Tsukiji and O. Watanabe},
  title = {Partial Occam's razor its applications},
  journal = {Information Processing Letters},
  year = 1997,
}

@article{CTT100453231,
  author = {Ronald Book and Osamu Watanabe},
  title = {On random hard sets for NP},
  journal = {Information and Computation},
  year = 1996,
}

@article{CTT100555870,
  author = {J. Balcazar and J. Diaz and R. Gavalda and O. Watanabe},
  title = {An optimal parallel algorithm for learning DFA},
  journal = {Journal of Universal Computer Science},
  year = 1996,
}

@article{CTT100555856,
  author = {M. Ogiwara and T. Thierauf and S. Toda and O. Watanabe},
  title = {On closure properties of #P in the context of PFo#P},
  journal = {Journal of Computer and System Sciences},
  year = 1996,
}

@article{CTT100453232,
  author = {OSAMU WATANABE},
  title = {Randomized approximation of the constraint satisfaction problem},
  journal = {Nordic Journal of Computing},
  year = 1996,
}

@article{CTT100555871,
  author = {T. Thierauf and S. Toda and O. Watanabe},
  title = {On sets bounded truth-table reducible to P-selective sets},
  journal = {Theoretical Informatics and Applications},
  year = 1996,
}

@article{CTT100453229,
  author = {Luc Longpre and Osamu Watanabe},
  title = {On Symmetry of Information and Polynomial Time Invertibility},
  journal = {Information and Computation},
  year = 1995,
}

@article{CTT100555855,
  author = {R. Rao and J. Rothe and O. Watanabe},
  title = {Upward separation for FewP and related classes},
  journal = {Information Processing Letters},
  year = 1994,
}

@article{CTT100555854,
  author = {T. Thierauf and S. Toda and O. Watanabe},
  title = {On closure properties of GapP},
  journal = {Computational Complexity},
  year = 1994,
}

@article{CTT100555853,
  author = {J. Balcazar and J. Diaz and R. Gavalda and O. Watanabe},
  title = {The query complexity of learning DFA},
  journal = {New Generation Computing},
  year = 1994,
}

@article{CTT100711393,
  author = {P. Orponen and K. Ko and U. Schoning and O. Watanabe},
  title = {Instance Commplexity},
  journal = {Journal of the Association for Computing Machinery},
  year = 1994,
}

@article{CTT100555852,
  author = {R. Gavalda and O. Watanabe},
  title = {Structural analysis of polynomial time query learnability},
  journal = {Mathematical Systems Theory},
  year = 1994,
}

@article{CTT100555851,
  author = {O. Watanabe},
  title = {A framework for polynomial time query learnability},
  journal = {Mathematical Systems Theory},
  year = 1994,
}

@article{CTT100453228,
  author = {Pekka Orponen and Uwe Schoening and Ker-I Ko and Osamu Watanabe},
  title = {Instance Complexity(共著)},
  journal = {Journal of the Association for Computing Machiner,y},
  year = 1994,
}

@article{CTT100453226,
  author = {Ricard Gavalda and Osamu Watanabe},
  title = {On the computational complexity of small descriptions},
  journal = {SIAM Journal of Computing},
  year = 1993,
}

@article{CTT100555850,
  author = {N. Abe and O. Watanabe},
  title = {polonomially sparse variations and reducibility among prediction problems},
  journal = {IEICE Trans. Information and Systems},
  year = 1992,
}

@article{CTT100453224,
  author = {OSAMU WATANABE},
  title = {Relating equivalence and reducibility to sparse sets},
  journal = {SIAM Journal on Computing},
  year = 1992,
}

@article{CTT100555849,
  author = {S. Toda and O. Watanabe},
  title = {Polynomial time 1-turing reductions from #PH to #P},
  journal = {Theoretical Computer Science},
  year = 1992,
}

@article{CTT100555845,
  author = {O. Watanabe},
  title = {On polynomial-time one-truth-table reduccibility to sparse sets},
  journal = {Journal of Computer and System Sciences},
  year = 1992,
}

@article{CTT100715393,
  author = {S. Tang and O. Watanabe},
  title = {On polynomial -time turing and many-one completeness in PSPACE},
  journal = {Theoretical Computer Science},
  year = 1992,
}

@article{CTT100555843,
  author = {O. Watanabe},
  title = {On intractability of the class UP},
  journal = {Mathematical Systems Theory},
  year = 1991,
}

@article{CTT100555842,
  author = {O. Watanabe},
  title = {A note on the p-isomorphism conjecture},
  journal = {Theoretical Computer Science},
  year = 1991,
}

@article{CTT100715395,
  author = {M. Ogiwara and O. Watanabe},
  title = {On polynomial time bounded truth -table reducibility of NP sets to sparse sets},
  journal = {SIAM Journal on Computing},
  year = 1991,
}

@article{CTT100453222,
  author = {OSAMU WATANABE},
  title = {Kolmogorov Complexity and degrees of tally sets(共著)},
  journal = {Information and Computation},
  year = 1990,
}

@article{CTT100555841,
  author = {S.Tang and O. Watanabe},
  title = {On tally relativizations of BP-commplexity classes},
  journal = {SIAM Journal on Computing},
  year = 1989,
}

@article{CTT100555840,
  author = {R. Book and P. Orponen and D. Russo and Osamu Watanabe},
  title = {Lowness properties of sets in the exponential-time hierarchy},
  journal = {SIAM Journal on Computing},
  year = 1988,
}

@article{CTT100555839,
  author = {O. Watanabe},
  title = {On hardness of one-way functions},
  journal = {Information Processing Letters},
  year = 1988,
}

@article{CTT100718763,
  author = {O. Watanabe},
  title = {On the computational complexity of small descriptions},
  journal = {17th Int'l Symposium on Mathematical Foundations of Computer Science (MFCS)},
  year = 1987,
}

@article{CTT100453221,
  author = {OSAMU WATANABE},
  title = {A comparison of polynomial time completeness notions},
  journal = {Theoretical Computer Science},
  year = 1987,
}

@article{CTT100555838,
  author = {渡辺 治},
  title = {確率的アルゴリズムにおける効率・正解率間のトレードオフ関係について},
  journal = {情報処理学会論文誌},
  year = 1986,
}

@article{CTT100453220,
  author = {OSAMU WATANABE},
  title = {On one-one polynomial time equivalence relations},
  journal = {Theoretical Computer Science},
  year = 1985,
}

@article{CTT100555837,
  author = {O. WATANABE},
  title = {On one-one polynomial trade off problem on on-line probabilistic turing machines},
  journal = {Theoretical Computer Science},
  year = 1985,
}

@article{CTT100453219,
  author = {Osamu Watanabe},
  title = {The time-precision trade off problem on on-line probabilistic turing machines},
  journal = {Theoretical Computer Science},
  year = 1983,
}

@article{CTT100555363,
  author = {O. Watanabe},
  title = {A fast algorithm for finding all shortest paths},
  journal = {Information Processing Letters},
  year = 1981,
}

@article{CTT100715834,
  author = {O. Watanabe},
  title = {Another application of recursion introduction},
  journal = {Information Processing Letters},
  year = 1980,
}

@inproceedings{CTT100772527,
  author = {Tong Qin and Osamu Watanabe},
  title = {An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem},
  booktitle = {信学技報},
  year = 2017,
}

@inproceedings{CTT100715868,
  author = {Osamu Watanabe},
  title = {Sublinear space complexity},
  booktitle = {},
  year = 2016,
}

@inproceedings{CTT100704714,
  author = {渡辺 治},
  title = {この本！ おすすめします コンピューターサイエンスを教養に},
  booktitle = {情報管理},
  year = 2016,
}

@inproceedings{CTT100715867,
  author = {Shuichi Hirahara and Osamu Watanabe},
  title = {Limits of minimum circuit size problem as oracle},
  booktitle = {Proc. of the  31st Conference on Computational Complexity},
  year = 2016,
}

@inproceedings{CTT100715534,
  author = {Tatsuya Imai and Osamu Watanabe},
  title = {Relating sublinear space computability},
  booktitle = {SOFSEM 2016: Theory and Practice of Computer Science},
  year = 2016,
}

@inproceedings{CTT100715524,
  author = {Linus Hermannson and Fredrik Johansson and Osamu Watanabe},
  title = {Generalized shortest path kernel on graphs},
  booktitle = {Discovery Science},
  year = 2015,
}

@inproceedings{CTT100715527,
  author = {渡辺 治},
  title = {新学術領域「計算限界解明」の研究紹介},
  booktitle = {},
  year = 2015,
}

@inproceedings{CTT100720225,
  author = {O. Watanabe},
  title = {On the limit of some algorithmic approach to circuit lower bounds},
  booktitle = {LNCS},
  year = 2014,
}

@inproceedings{CTT100720222,
  author = {渡辺 治},
  title = {計算限界への挑戦：Ｐ＝ＮＰの世界を目指して},
  booktitle = {},
  year = 2014,
}

@inproceedings{CTT100721905,
  author = {D. Kane and O. Watanabe},
  title = {Implicant size of a CNF formula with many satisfying assignments},
  booktitle = {信学技報 COMP2014-31},
  year = 2014,
}

@inproceedings{CTT100720221,
  author = {O. Watanabe},
  title = {The Strong Exponential Time Hypothesis and the structure of the solution space of CNF-SAT problems},
  booktitle = {},
  year = 2014,
}

@inproceedings{CTT100704715,
  author = {ケイン ダニエル and 渡辺 治},
  title = {多くの充足解を持つ和積形論理式のインプリカントの大きさについて},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2014,
}

@inproceedings{CTT100704716,
  author = {渡辺 治},
  title = {スーパーコン : 高校生・高専生の電脳甲子園(<特集>若い力:高校生の問題解決)},
  booktitle = {オペレーションズ・リサーチ : 経営の科学},
  year = 2014,
}

@inproceedings{CTT100720219,
  author = {O. Watanabe},
  title = {Max k-linear equation problem},
  booktitle = {},
  year = 2014,
}

@inproceedings{CTT100720218,
  author = {渡辺 治},
  title = {環境適用型アルゴリズム},
  booktitle = {},
  year = 2014,
}

@inproceedings{CTT100720223,
  author = {渡辺 治},
  title = {「多面的アプローチの統合による計算限界の解明」について},
  booktitle = {},
  year = 2014,
}

@inproceedings{CTT100717794,
  author = {Tetsuo Asano and David Kirkpatrick and Kotaro Nakagawa and Osamu Watanabe},
  title = {O(sqrt(n))-space and polynomial-time algorithm for planar directed graph reachability},
  booktitle = {Lecture Notes in Computer Science},
  year = 2014,
}

@inproceedings{CTT100717799,
  author = {Akinori Kawachi and Benjamin Rossman and Osamu Watanabe},
  title = {The query complexity of witness finding},
  booktitle = {Lecture Notes in Computer Science},
  year = 2014,
}

@inproceedings{CTT100717795,
  author = {Daniel M. Kane and Osamu Watanabe},
  title = {A short implicant of a CNF formula with many satisfying assignments},
  booktitle = {Lecture Notes in Computer Science},
  year = 2014,
}

@inproceedings{CTT100720216,
  author = {渡辺 治},
  title = {計算複雑さの理論とその進展},
  booktitle = {},
  year = 2013,
}

@inproceedings{CTT100720215,
  author = {渡辺 治},
  title = {計算限界解明：なぜ限界を？＆なぜ今？},
  booktitle = {},
  year = 2013,
}

@inproceedings{CTT100720213,
  author = {渡辺 治},
  title = {計算限界への挑戦：Ｐ＝ＮＰの世界を目指して},
  booktitle = {},
  year = 2013,
}

@inproceedings{CTT100721904,
  author = {Tatsuya Imai and Kotaro Nakagawa and Aduri Pavan and Variyam Vinochandran and Osamu Watanabe},
  title = {An O(sqrt(n)+eps})-Space Algorithm for Directed Planar Reachability with Polynomial Running Time},
  booktitle = {情処研報 AL},
  year = 2013,
}

@inproceedings{CTT100704717,
  author = {河内 亮周 and ロスマン ベンジャミン and 渡辺 治},
  title = {NP-解探索における質問計算量について(一般)},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2013,
}

@inproceedings{CTT100704718,
  author = {河内 亮周 and ロスマン ベンジャミン and 渡辺 治},
  title = {NP-解探索における質問計算量について},
  booktitle = {研究報告アルゴリズム（AL）},
  year = 2013,
}

@inproceedings{CTT100704719,
  author = {遊佐 俊彦 and 渡辺 治},
  title = {DS-1-5 正規化圧縮距離の妥当性解析(DS-1.COMP学生シンポジウム,シンポジウムセッション)},
  booktitle = {電子情報通信学会総合大会講演論文集},
  year = 2013,
}

@inproceedings{CTT100717798,
  author = {Tatsuya Imai and Kotaro Nakagawa and A. Pavan and N.V. Vinodchandran and Osamu Watanabe},
  title = {An O(n^{{1/2}+epsilon}})-space and polynomial-time algorithm for directed planar reachability},
  booktitle = {Computational Complexity (CCC), 2013 IEEE Conference on},
  year = 2013,
}

@inproceedings{CTT100704721,
  author = {山口 裕生 and 渡辺 治},
  title = {べき則グラフ上での対立する噂の拡散の解析 : 二種類の次数の頂点からなるグラフの場合(一般)},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2012,
}

@inproceedings{CTT100704720,
  author = {渡辺 治},
  title = {計算複雑さへの招待(1):基本+平均時計算複雑さ(特別企画)},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2012,
}

@inproceedings{CTT100704722,
  author = {渡辺 治},
  title = {[招待講演]新学術領域「計算限界解明」発足にあたって},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2012,
}

@inproceedings{CTT100633310,
  author = {OSAMU WATANABE},
  title = {Message passing algorithms for MLS-3LIN problem},
  booktitle = {Proc. of the 9th Meeting on Analytic Algorithmics and Combinatrics},
  year = 2012,
}

@inproceedings{CTT100717797,
  author = {Johannes Köbler and Sebastian Kuhnert and Osamu Watanabe},
  title = {Interval graphg representation with given interval and intersection lengths},
  booktitle = {Lecture Notes in Computer Science},
  year = 2012,
}

@inproceedings{CTT100717744,
  author = {Yoshinori Aono and Manindra Agrawal and Takakazu Satoh and Osamu Watanabe},
  title = {On the optimality of lattices for the Coppersmith technique},
  booktitle = {Lecture Notes in Computer Science},
  year = 2012,
}

@inproceedings{CTT100717793,
  author = {Holger Dell and Valentine Kabanets and Dieter van Melkebeek and Osamu Watanabe},
  title = {Is Valiant-Vazirani's isolation probability improvable?},
  booktitle = {Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on},
  year = 2012,
}

@inproceedings{CTT100704724,
  author = {渡辺 治},
  title = {計算複雑さの理論 : 我々は何を研究しているのか?},
  booktitle = {電子情報通信学会技術研究報告. COMP, コンピュテーション},
  year = 2011,
}

@inproceedings{CTT100633309,
  author = {Y. Kobayashi and A. Kishimoto and O. Watanabe},
  title = {Evaluations of hash distributed A* in optimal sequence alignment},
  booktitle = {IJCAI Proceedings},
  year = 2011,
}

@inproceedings{CTT100618131,
  author = {石畑 清 and 大岩 元 and 角田 博保 and 清水 謙多郎 and 玉井 哲雄 and 長崎 等 and 中里 秀則 and 中谷 多哉子 and 疋田 輝雄 and 三浦 孝夫 and 箕原 辰夫 and 和田 耕一 and 渡辺 治},
  title = {理工系情報学科の授業内容分布のシラバスによる調査（中間報告）},
  booktitle = {情報教育シンポジウム},
  year = 2010,
}

@inproceedings{CTT100618130,
  author = {Amin Coja-Oghlan and Mikael Onsjo and Osamu Watanabe},
  title = {Propagation connectivity of random hypergraph},
  booktitle = {in Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM'10)},
  year = 2010,
}

@inproceedings{CTT100711375,
  author = {Yoshiyuki Kabashima and Hisanao Takahashi and Osamu Watanabe},
  title = {Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices},
  booktitle = {Journal of Physics Conference Series},
  year = 2010,
}

@inproceedings{CTT100615165,
  author = {Yoshinori Aono and Manindra Agrawal and Osamu Watanabe},
  title = {On Coppersmith's technique and its limit},
  booktitle = {},
  year = 2010,
}

@inproceedings{CTT100604578,
  author = {Takeya Shigezumi and Yushi Uno and OSAMU WATANABE},
  title = {A new model for a scale-free hierarchical structure of isolated cliques},
  booktitle = {Proc. of 4th Workshop on Algorithms and Computation (WALCOM'10)},
  year = 2010,
}

@inproceedings{CTT100615288,
  author = {副島佑介 and 岸本 章宏 and 渡辺治},
  title = {モンテカルロ木探索のRoot並列化とコンピュータ囲碁での有効性について},
  booktitle = {},
  year = 2009,
}

@inproceedings{CTT100604586,
  author = {副島佑介 and 岸本章宏 and 渡辺治},
  title = {モンテカルロ木探索のroot並列化とコンピュータ囲碁での有効性について},
  booktitle = {},
  year = 2009,
}

@inproceedings{CTT100615216,
  author = {Yoshiyuki Kabashima and Osamu Watanabe},
  title = {On spectral analysis of large low-density random matrices: rigorous vs. cavity analysis},
  booktitle = {},
  year = 2009,
}

@inproceedings{CTT100597648,
  author = {Madhusuden Agrawal and OSAMU WATANABE},
  title = {One-way functions and the Berman-Hartmanis conjecture},
  booktitle = {},
  year = 2009,
}

@inproceedings{CTT100604585,
  author = {Mikael Onsjö and OSAMU WATANABE},
  title = {Implementation of a bit-parallel approximate string matching algorithm},
  booktitle = {},
  year = 2009,
}

@inproceedings{CTT100565468,
  author = {Naoto Miyoshi and Takeya Shigezumi and Ryuhei Uehara and Osamu Watanabe},
  title = {Scale-free interval graphs},
  booktitle = {Algorithmic Aspects in Information and Management},
  year = 2008,
}

@inproceedings{CTT100576248,
  author = {Takeya Shigezumi and Naoto Miyoshi and Ryuhei Uehara and Osamu Watanabe},
  title = {Scale free interval graphs},
  booktitle = {},
  year = 2008,
}

@inproceedings{CTT100576238,
  author = {Takeya Shigezumi and Naoto Miyoshi and Ryuhei Uehara and Osamu Watanabe},
  title = {Scale free interval graphs},
  booktitle = {},
  year = 2008,
}

@inproceedings{CTT100564252,
  author = {新里卓史 and 飯田勝吉 and 植松友彦 and 渡辺治},
  title = {東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構},
  booktitle = {電子情報通信学会},
  year = 2008,
}

@inproceedings{CTT100563162,
  author = {新里卓史 and 飯田勝吉 and 植松友彦 and 渡辺治},
  title = {東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構の設計と実装},
  booktitle = {電子情報通信学会},
  year = 2008,
}

@inproceedings{CTT100576251,
  author = {Naoto Miyoshi and Takeya Shigezumi and Ryuhei Uehara and Osamu Watanabe},
  title = {Scale Free Interval Graphs},
  booktitle = {},
  year = 2007,
}

@inproceedings{CTT100575529,
  author = {Osamu Watanabe},
  title = {Complexity of finding most likely solutions},
  booktitle = {信学技報 COMP},
  year = 2007,
}

@inproceedings{CTT100575528,
  author = {伊東利哉 and 渡辺治},
  title = {重みつき乱択最適選好マッチング},
  booktitle = {信学技報 COMP},
  year = 2007,
}

@inproceedings{CTT100575902,
  author = {Takeya Shigezumi and 上原隆平 and Osamu Watanabe},
  title = {Do interval graphs dream of scale-free network?},
  booktitle = {},
  year = 2007,
}

@inproceedings{CTT100576153,
  author = {Osamu Watanabe and Mikael Onsjoe},
  title = {Finding most likely solutions},
  booktitle = {Lecture Notes in Computer Science},
  year = 2007,
}

@inproceedings{CTT100556129,
  author = {E. Hemaspaandra and L. Hemaspaandra and T. Tantau and O. Watanabe},
  title = {On the complexity of kings},
  booktitle = {Lecture notes in computer science},
  year = 2007,
}

@inproceedings{CTT100556126,
  author = {O. Watanabe and M. Yamamoto},
  title = {Average-case analysis for the MAX-2SAT problem},
  booktitle = {Lecture notes in computer science},
  year = 2006,
}

@inproceedings{CTT100556127,
  author = {M. Onsjoe and O. Watanabe},
  title = {A simple message passing algorithm for graph partition problem},
  booktitle = {Lecture Notes in Computer Science},
  year = 2006,
}

@inproceedings{CTT100556921,
  author = {M.M. Halldorsson and O. Watanabe and M. Yamamoto},
  title = {An improved upper bound for the three domatic number problems},
  booktitle = {},
  year = 2006,
}

@inproceedings{CTT100556928,
  author = {渡辺 治 and 山本 真基},
  title = {MAX-2SAT 問題の平均時間計算量の解析},
  booktitle = {信学技報 COMP},
  year = 2006,
}

@inproceedings{CTT100556929,
  author = {M. Onsjoe and 渡辺 治},
  title = {メッセージ伝播法によるグラフの分割アルゴリズム},
  booktitle = {情処研報 AL},
  year = 2006,
}

@inproceedings{CTT100393216,
  author = {Osamu Watanabe},
  title = {Some heuristic analysis of local search algorithms for SAT problems},
  booktitle = {Lecture Notes in Computer Sciecne, Springer},
  year = 2005,
}

@inproceedings{CTT100721903,
  author = {M. Onsjoe and O. Watanabe},
  title = {A message passing algorithm for the bisection problem},
  booktitle = {},
  year = 2005,
}

@inproceedings{CTT100556395,
  author = {渡辺治},
  title = {Computational Complexity and Its Applications},
  booktitle = {},
  year = 2005,
}

@inproceedings{CTT100387525,
  author = {Kouhei Hatano and Osamu Watanabe},
  title = {Learning r-of-k functions by boosting},
  booktitle = {Proc. 15th International Conference on Algorithmic Learning Theory (ALT 2004)},
  year = 2004,
}

@inproceedings{CTT100721899,
  author = {O. Watanabe},
  title = {Pseudo expectation: A tool for analyzing local search algorithms},
  booktitle = {湘南国際村},
  year = 2004,
}

@inproceedings{CTT100556920,
  author = {K. Hatano and O. Watanabe},
  title = {Learning r-of-k functions by boosting},
  booktitle = {信学技報 COMP},
  year = 2004,
}

@inproceedings{CTT100721901,
  author = {O. Watanabe},
  title = {Pseudo expectation: A tool for analyzing local search algorithms},
  booktitle = {},
  year = 2004,
}

@inproceedings{CTT100387530,
  author = {Jin-Yi Cai and Osamu Watanabe},
  title = {Random access to advice strings and collapsing results},
  booktitle = {Proc. 15th International Symposium on Algorithms and Computation (ISAAC'04)},
  year = 2004,
}

@inproceedings{CTT100556926,
  author = {新倉 康明 and J. Schneider and 渡辺 治},
  title = {単純な規則で表されるマルコフ過程の近似解析手法},
  booktitle = {情処研報 AL},
  year = 2004,
}

@inproceedings{CTT100489360,
  author = {J.Y. Cai and O. Watanabe},
  title = {On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results},
  booktitle = {Proc. 9th International Computing and Combinatorics Conference},
  year = 2003,
}

@inproceedings{CTT100489361,
  author = {O. Watanabe and K. Sawai and H. Takahashi},
  title = {Analysis of a randomized local search algorithm for LDPCC decoding problem},
  booktitle = {Proc. 2nd International Symposium on Stochastic Algorithms},
  year = 2003,
}

@inproceedings{CTT100556383,
  author = {O. Watanabe},
  title = {Analysis of randomized algorithms for some constraint satisfaction problem},
  booktitle = {},
  year = 2003,
}

@inproceedings{CTT100556919,
  author = {O. Watanabe},
  title = {P vs. NP and P vs. PSPACE},
  booktitle = {},
  year = 2003,
}

@inproceedings{CTT100721897,
  author = {O. Watanabe},
  title = {Analysis of a randomized local search algorithm for LDPCC decoding problems},
  booktitle = {},
  year = 2003,
}

@inproceedings{CTT100721896,
  author = {O. Watanabe},
  title = {Analysis of a randomized local search algorithm for LDPCC decoding problems},
  booktitle = {},
  year = 2003,
}

@inproceedings{CTT100556102,
  author = {J.Y. Cai and O. Watanabe},
  title = {Relativized collapsing results under stringent oracle access},
  booktitle = {情報技術レターズ},
  year = 2002,
}

@inproceedings{CTT100556337,
  author = {渡辺 治},
  title = {LDPCの複合化のためのランダム局所探索アルゴリズムの解析},
  booktitle = {},
  year = 2002,
}

@inproceedings{CTT100556918,
  author = {J. Balcazar and 戴 陽 and O. Watanabe},
  title = {Provably fast trainning algorithms for support vector machines},
  booktitle = {信学技報 COMP},
  year = 2002,
}

@inproceedings{CTT100556375,
  author = {渡辺 治},
  title = {ある制約式充足問題群の解法について},
  booktitle = {},
  year = 2002,
}

@inproceedings{CTT100556101,
  author = {R. Gavalda and O. Watanabe},
  title = {Sequential sampling algorithms: Unified analysis and lower bounds},
  booktitle = {Lecture notes in computer science},
  year = 2001,
}

@inproceedings{CTT100556096,
  author = {K. Amano and J. Tromp and O. Watanabe},
  title = {On a generalized ruin problem},
  booktitle = {Lecture notes in computer science},
  year = 2001,
}

@inproceedings{CTT100556097,
  author = {J. Balcazar and Y.Dai and O. Watanabe},
  title = {Provably fast training algorithms for support vector machines},
  booktitle = {Proceedings, 2001 IEEE International Conference on Data Mining, 29 November-2 December 2001, San Jose, California},
  year = 2001,
}

@inproceedings{CTT100759247,
  author = {Carlos Domingo and Osamu Watanabe},
  title = {MadaBoost: A modification of AdaBoost},
  booktitle = {Proc. of 3th Annual Confernce on Computational Learning Theory (COLT'00)},
  year = 2000,
}

@inproceedings{CTT100556917,
  author = {K. Amano and P. Vitanyi and O. Watanabe},
  title = {On the length of the monopolist game},
  booktitle = {信学技報 COMP},
  year = 2000,
}

@inproceedings{CTT100556095,
  author = {C. Domingo and O. Watanabe},
  title = {Scaling up a boosting-based learner via adaptive sampling},
  booktitle = {Lecture notes in artificial intelligence},
  year = 2000,
}

@inproceedings{CTT100721892,
  author = {Kyoichi Okamoto and Osamu Watanabe},
  title = {Deterministic application of Grover's quantum search algorithm},
  booktitle = {情処研報 AL},
  year = 2000,
}

@inproceedings{CTT100556094,
  author = {P.B. Miltersen and N.V. Vinodchandran and O. Watanabe},
  title = {Super-polynomial verseus half-exponential circuit size exponential hierarchy},
  booktitle = {Lecture notes in computer science},
  year = 1999,
}

@inproceedings{CTT100711388,
  author = {Carlos Domingo and Ricard Gavaldà and Osamu Watanabe},
  title = {Adaptive sampling methods for scaling up knowledge discovery algorithms},
  booktitle = {Second International Conference, DS’99 Tokyo, Japan, December 6–8, 1999 Proceedings},
  year = 1999,
}

@inproceedings{CTT100556236,
  author = {O. Watanabe},
  title = {From learning theory to discovery science},
  booktitle = {Lecture notes in computer science},
  year = 1999,
}

@inproceedings{CTT100556092,
  author = {C. Domingo and O. Watanabe and T. Yamazaki},
  title = {A role of constaint in self-organization},
  booktitle = {Lecture notes in computer science},
  year = 1998,
}

@inproceedings{CTT100556093,
  author = {C. Domingo and R. Gavalda and O. Watanabe},
  title = {Practical algorithms for on-line sampling},
  booktitle = {Lecture notes in artificial intelligence},
  year = 1998,
}

@inproceedings{CTT100556091,
  author = {W. Lindner and R. Schuler and O. Watanabe},
  title = {Resource bounded measure and learnability},
  booktitle = {Proceedings, Thirteenth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), June 15-18, 1998, Buffalo, New York, USA},
  year = 1998,
}

@inproceedings{CTT100556090,
  author = {C. Domingo and T. Tsukiji and O. Watanabe},
  title = {Partial Occam's razor and its appliations},
  booktitle = {Lecture notes in artificial intelligence},
  year = 1997,
}

@inproceedings{CTT100556089,
  author = {S. Horie and O. Watanabe},
  title = {Hard instance generataion for SAT},
  booktitle = {Lecture notes in computer science},
  year = 1997,
}

@inproceedings{CTT100556087,
  author = {L. Hemachandra and Z. Jiang and J. Rothe and O. Watanabe},
  title = {The join can lower complexity},
  booktitle = {Lecture notes in computer science},
  year = 1996,
}

@inproceedings{CTT100711387,
  author = {Hoong Chuin Lau and Osamu Watanabe},
  title = {Randomized approximation of the constraint satisfaction problem},
  booktitle = {5th Scandinavian Workshop on Algorithm Theory Reykjavík, Iceland, July 3–5, 1996 Proceedings},
  year = 1996,
}

@inproceedings{CTT100556088,
  author = {O. Watanabe and O. Yamashita},
  title = {An improvement of the digital cash  protocol of Okamoto and Ohta},
  booktitle = {Lecture notes in computer science},
  year = 1996,
}

@inproceedings{CTT100555981,
  author = {R. Schuler and O. Watanabe},
  title = {Towards average-case complexity analysis of NP optimization problems},
  booktitle = {Proceedings of the tenth Annual Structure in Complexity Theory Conference, June 19-22, 1995, Minneapolis, Minnesota},
  year = 1995,
}

@inproceedings{CTT100556086,
  author = {J. Kobler and O. Watanabe},
  title = {New collapse consequence of NP having small circuits},
  booktitle = {Lecture notes in computer science},
  year = 1995,
}

@inproceedings{CTT100555975,
  author = {J. Balcazar and J. Diaz and R. Gavalda and O. Watanabe},
  title = {An optimal parallel algorithm for learning DFA},
  booktitle = {Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory : COLT 94 : July 12th-15th, 1994, New Brunswick, New Jersey},
  year = 1994,
}

@inproceedings{CTT100555971,
  author = {T. Tierauf and S. Toda and O. Watanabe},
  title = {On sets bounded truth-table reducible to P-selective sets},
  booktitle = {Lecture notes in computer science},
  year = 1994,
}

@inproceedings{CTT100711363,
  author = {R. Book and O. Watanabe},
  title = {On random hard sets for NP},
  booktitle = {5th International Symposium, ISAAC '94 Beijing, P. R. China, August 25–27, 1994 Proceedings},
  year = 1994,
}

@inproceedings{CTT100555976,
  author = {O. Watanabe},
  title = {Test instance gereration for promised NP seaarch problems},
  booktitle = {Proceedings of the Ninth Annual Structure in Complexity Theory Conference, June 28-July 1, 1994, Amsterdam, the Netherlands},
  year = 1994,
}

@inproceedings{CTT100555965,
  author = {M. Ogiwara and T. Tierauf and S. Toda and O. Watanabe},
  title = {On closure properties of #P in the context of Pfo # P},
  booktitle = {Proceedings of the Eighth Annual Structure in Complexity Theory Conference, May 18-21, 1993, San Diego, California},
  year = 1993,
}

@inproceedings{CTT100555960,
  author = {J. Balcazar and J. Diaz and R. Gavalda and O. Watanabe},
  title = {A note on the query complexity of learning DFA},
  booktitle = {Lecture Notes In Computer Science},
  year = 1993,
}

@inproceedings{CTT100556916,
  author = {O. Watanabe},
  title = {Three layer network for identity mapping},
  booktitle = {信学技報 COMP},
  year = 1992,
}

@inproceedings{CTT100555961,
  author = {K. kurosawa and O. Watanabe},
  title = {Computational and statistical indistinguishability},
  booktitle = {Lecture notes in computer science},
  year = 1992,
}

@inproceedings{CTT100555958,
  author = {O. Watanabe},
  title = {On the complexity of small description and related topics},
  booktitle = {Lecture notes in computer science},
  year = 1992,
}

@inproceedings{CTT100711362,
  author = {L. Longpre and O. Watanabe},
  title = {On symmetry of information and polynomial time invertibility},
  booktitle = {Third International Symposium, ISAAC'92 Nagoya, Japan, December 16–18, 1992 Proceedings},
  year = 1992,
}

@inproceedings{CTT100555957,
  author = {L. Hemachandra and M. Ogiwara and O. Watanabe},
  title = {How hard are sparse sets ?},
  booktitle = {SProceedings of the Seventh Annual Structure in Complexity Theory Conference, June 22-25, 1992, Boston University, Boston, Massachusetts},
  year = 1992,
}

@inproceedings{CTT100711360,
  author = {E. Allender and L. Hemachandra and M. Ogiwara and O. Watanabe},
  title = {Relating equivalence and reducibility to sparse sets},
  booktitle = {Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual},
  year = 1991,
}

@inproceedings{CTT100556915,
  author = {T. Koshiba and O. Watanabe},
  title = {A note on the construction of decision trees},
  booktitle = {信学技報 COMP},
  year = 1991,
}

@inproceedings{CTT100711361,
  author = {R. Gavalda and O. Watanabe},
  title = {On the computational complexity of small descriptions},
  booktitle = {Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual},
  year = 1991,
}

@inproceedings{CTT100555911,
  author = {O. Watanabe},
  title = {A formal study of learning via queries},
  booktitle = {Lecture notes in computer science},
  year = 1990,
}

@inproceedings{CTT100710979,
  author = {M. Ogiwara and O. Watanabe},
  title = {On polynomial time bounded truth-table reducibility of NP sets to sparse sets},
  booktitle = {Proceeding STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing},
  year = 1990,
}

@inproceedings{CTT100555915,
  author = {R. Gavalda and L. Torenvilet and J. Balcazar and O. Watanabe},
  title = {Generalized Kolmogorov complexity in relativized separations},
  booktitle = {Lecture notes in computer science},
  year = 1990,
}

@inproceedings{CTT100555912,
  author = {O. Watanabe},
  title = {Structural analyses on the complexity of inverting functions},
  booktitle = {Lecture notes in computer science},
  year = 1990,
}

@inproceedings{CTT100555910,
  author = {S. Tang and O. Watanabe},
  title = {On polynomial-time turning and many-one completeness in PSPACE},
  booktitle = {Proceegings, structure in complexity theory : fourth annual conference},
  year = 1989,
}

@inproceedings{CTT100555909,
  author = {O. Watanabe},
  title = {On 1-tt-sparseness of nondeterministic complexity classes},
  booktitle = {Lecture Notes in Computer Science},
  year = 1988,
}

@inproceedings{CTT100555908,
  author = {S. Tang and O. Watanabe},
  title = {On tally relativizations of BP-complexity classes,},
  booktitle = {Proceedings, structure in complexity theory, third annual conference : June 14-17, 1988, Georgetown University, Washington, D.C.},
  year = 1988,
}

@inproceedings{CTT100710563,
  author = {A. Allender and O. Watanabe},
  title = {Kolmogorov complexity and degrees of tally sets},
  booktitle = {Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual},
  year = 1988,
}

@inproceedings{CTT100555907,
  author = {O. Watanabe},
  title = {Polynomial time reducibility to a set of small density},
  booktitle = {Proceedings : structure in complexity theory : second annual conference, June 16-19, 1987, Cornell University, Ithaca, NY},
  year = 1987,
}

@inproceedings{CTT100555906,
  author = {R. Book and P. Orponen and D. Russo and O. Watanabe},
  title = {On exponential lowness},
  booktitle = {Lecture Notes in Computer Science},
  year = 1986,
}

@inproceedings{CTT100555873,
  author = {K. Ko and U. Schoning and P. Orponen and O. Watanabe},
  title = {What is a hard instance of a computational problem ?},
  booktitle = {Lecture Notes in Computer Science},
  year = 1986,
}

@misc{CTT100721909,
  author = {渡辺 治 and 遠藤 敏夫},
  title = {スーパーコンピューティングコンテスト・2013},
  year = 2014,
}

@misc{CTT100721908,
  author = {渡辺 治},
  title = {P≠NP予想って？},
  year = 2013,
}

@misc{CTT100721906,
  author = {渡辺 治},
  title = {P≠NP予想最前線},
  year = 2013,
}

@misc{CTT100704723,
  author = {渡辺 治},
  title = {計算複雑さの研究って?},
  year = 2012,
}

@misc{CTT100575527,
  author = {渡辺治 and 松田裕幸},
  title = {スパコンをぶん回せ - スーパーコンピューティングコンテスト・2008},
  year = 2008,
}

@misc{CTT100556941,
  author = {渡辺 治},
  title = {でたらめさを利用した計算},
  year = 2007,
}

@misc{CTT100556424,
  author = {J. Cai and O. Watanabe},
  title = {Stringent relativization: a new approach for studying complexity classes},
  year = 2006,
}

@misc{CTT100556432,
  author = {渡辺 治},
  title = {教養としてのコンピュータ・サイエンス教育――東京工業大学での試み},
  year = 2006,
}

@misc{CTT100556940,
  author = {渡辺 治},
  title = {ランダムネスの面白さ},
  year = 2006,
}

@misc{CTT100556392,
  author = {J. Cai and O. Watanabe},
  title = {Stringent relativization},
  year = 2003,
}

@misc{CTT100556937,
  author = {渡辺 治},
  title = {ネヴァンリンナ賞業績紹介：スダン},
  year = 2003,
}

@misc{CTT100556938,
  author = {渡辺 治},
  title = {ＰＣＰ：驚異の証明検証法},
  year = 2003,
}

@misc{CTT100556939,
  author = {渡辺 治},
  title = {スーパーコンピュータ・コンテスト２００３},
  year = 2003,
}

@misc{CTT100556237,
  author = {渡辺 治},
  title = {ブースティング技法のアルゴリズム的考察},
  year = 2002,
}

@misc{CTT100556327,
  author = {O. Watanabe},
  title = {Algorithmic aspects of boosting},
  year = 2002,
}

@misc{CTT100556935,
  author = {渡辺 治},
  title = {コンピュータサイエンスのための単純かつ効率的なサンプリング技法},
  year = 2000,
}

@misc{CTT100556936,
  author = {渡辺 治},
  title = {計算を究める−アルゴリズムと計算の複雑さの研究},
  year = 2000,
}

@misc{CTT100556906,
  author = {根上 生也 and 松井 知己 and 渡辺 治},
  title = {Web 鼎談},
  year = 1999,
}

@misc{CTT100556923,
  author = {T. Motoki and 渡辺 治},
  title = {Test instance generators for SAT},
  year = 1997,
}

@misc{CTT100556933,
  author = {渡辺 治},
  title = {東工大スーパーコンピュータコンテスト},
  year = 1997,
}

@misc{CTT100556932,
  author = {渡辺 治},
  title = {東工大スーパーコンピュータコンテスト},
  year = 1995,
}

@misc{CTT100556931,
  author = {渡辺 治},
  title = {一方向関数の基礎理論},
  year = 1994,
}

@misc{CTT100556235,
  author = {渡辺 治},
  title = {NP型問題の近似解法の可能性について},
  year = 1994,
}

@misc{CTT100556234,
  author = {O. Watanabe},
  title = {A view of structural complexity theory},
  year = 1993,
}

@misc{CTT100556138,
  author = {R. Book and O. Watanabe},
  title = {A view of structural complexity theory},
  year = 1993,
}

@misc{CTT100556154,
  author = {渡辺 治},
  title = {一方向関数のお話},
  year = 1991,
}

@misc{CTT100556231,
  author = {渡辺 治},
  title = {計算論的学習のお話},
  year = 1991,
}

@misc{CTT100556130,
  author = {O. Watanabe},
  title = {On one-way functions},
  year = 1989,
}

@misc{CTT100555872,
  author = {渡辺 治},
  title = {確率的アルゴリズム},
  year = 1983,
}

@misc{CTT100556443,
  author = {O. Watanabe},
  title = {On the Structure of Intractable Complexity Classes},
  year = 1987,
}



@phdthesis{CTT100556443,
  author = {O. Watanabe},
  title = {On the Structure of Intractable Complexity Classes},
  school = {東京工業大学},
  year = 1987,
}