Osamu Watanabe

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's isolation probability improvable? Computational Complexity 22(2): 345-383 (2013)

Masahiro Oda, Takayuki Kitasaka, Kazuhiro Furukawa, Osamu Watanabe, Takafumi Ando, Hidemi Goto, Kensaku Mori: Automated Ulcer Detection Method from CT Images for Computer Aided Diagnosis of Crohn's Disease. IEICE Transactions 96-D(4): 808-818 (2013)

Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe: Estimating the Gowers Norm of Modulo Functions over Prime Fields. IEICE Transactions 95-D(3): 755-762 (2012)

Osamu Watanabe, Takahiro Fukuhara, Hitoshi Kiya: Codestream-Based Identification of JPEG 2000 Images with Different Coding Parameters. IEICE Transactions 95-D(4): 1120-1129 (2012)

Kohei Onizuka, Hiroaki Ishihara, Masahiro Hosoya, Shigehito Saigusa, Osamu Watanabe, Shoji Otaka: A 1.9 GHz CMOS Power Amplifier With Embedded Linearizer to Compensate AM-PM Distortion. J. Solid-State Circuits 47(8): 1820-1827 (2012)

Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe: On the Optimality of Lattices for the Coppersmith Technique. ACISP 2012: 376-389

Osamu Watanabe: Message Passing Algorithms for MLS-3LIN Problem. ANALCO 2012: 68-85

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe: Is Valiant-Vazirani's Isolation Probability Improvable? IEEE Conference on Computational Complexity 2012: 10-20

Osamu Watanabe, Takahiro Fukuhara, Hitoshi Kiya: Hash based identification of JPEG 2000 images with different coding parameters. ICASSP 2012: 1037-1040

Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe: Interval Graph Representation with Given Interval and Intersection Lengths. ISAAC 2012: 517-526

Akihide Sai, Yuka Kobayashi, Shigehito Saigusa, Osamu Watanabe, Tetsuro Itakura: A digitally stabilized type-III PLL using ring VCO with 1.01psrms integrated jitter in 65nm CMOS. ISSCC 2012: 248-250

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe: Query Complexity and Error Tolerance of Witness Finding Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19: 2 (2012)

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe: Interval graph representation with given interval and intersection lengths. Electronic Colloquium on Computational Complexity (ECCC) 19: 32 (2012)

Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe: On the Optimality of Lattices for the Coppersmith Technique. IACR Cryptology ePrint Archive 2012: 108 (2012)

Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto: Spectral Analysis of Random Sparse Matrices. IEICE Transactions 94-A(6): 1247-1256 (2011)

Takeya Shigezumi, Yushi Uno, Osamu Watanabe: A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques. J. Graph Algorithms Appl. 15(5): 661-682 (2011)

Kohei Onizuka, Hiroaki Ishihara, Masahiro Hosoya, Shigehito Saigusa, Osamu Watanabe, Shoji Otaka: A 1.9/2.4GHz dual band CMOS power amplifier with integrated AM-PM distortion canceller. CICC 2011: 1-4

Osamu Watanabe, Takahiro Fukuhara, Hitoshi Kiya: Fast identification of JPEG 2000 images for digital cinema profiles. ICASSP 2011: 881-884

Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe: Evaluations of Hash Distributed A* in Optimal Sequence Alignment. IJCAI 2011: 584-590

Hiroki Sakurai, Yuka Kobayashi, Toshiya Mitomo, Osamu Watanabe, Shoji Otaka: A 1.5GHz-modulation-range 10ms-modulation-period 180kHzrms-frequency-error 26MHz-reference mixed-mode FMCW synthesizer for mm-wave radar application. ISSCC 2011: 292-294

Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, Osamu Watanabe (Eds.): Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings. Lecture Notes in Computer Science 7074, Springer 2011, isbn 978-3-642-25590-8

Valentine Kabanets, Osamu Watanabe: Is the Valiant-Vazirani Isolation Lemma Improvable? Electronic Colloquium on Computational Complexity (ECCC) 18: 151 (2011)

Toshiya Mitomo, Naoko Ono, Hiroaki Hoshino, Yoshiaki Yoshihara, Osamu Watanabe, Ichiro Seto: A 77 GHz 90 nm CMOS Transceiver for FMCW Radar Applications. J. Solid-State Circuits 45(4): 928-937 (2010)

Hiroaki Ishihara, Masahiro Hosoya, Shoji Otaka, Osamu Watanabe: A 10-MHz Signal Bandwidth Cartesian Loop Transmitter Capable of Off-Chip PA Linearization. J. Solid-State Circuits 45(12): 2785-2793 (2010)

Toshiya Itoh, Osamu Watanabe: Weighted random popular matchings. Random Struct. Algorithms 37(4): 477-494 (2010)

Yusuke Soejima, Akihiro Kishimoto, Osamu Watanabe: Evaluating Root Parallelization in Go. IEEE Trans. Comput. Intellig. and AI in Games 2(4): 278-287 (2010)

Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe: On the complexity of kings. Theor. Comput. Sci. 411(4-5): 783-798 (2010)

Osamu Watanabe, Masaki Yamamoto: Average-case analysis for the MAX-2SAT problem. Theor. Comput. Sci. 411(16-18): 1685-1697 (2010)

Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe: Propagation Connectivity of Random Hypergraphs. APPROX-RANDOM 2010: 490-503

Hiroaki Ishihara, Masahiro Hosoya, Shoji Otaka, Osamu Watanabe: A 10MHz signal bandwidth Cartesian-loop transmitter capable of off-chip PA linearization. ISSCC 2010: 66-67

Takeya Shigezumi, Yushi Uno, Osamu Watanabe: A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques. WALCOM 2010: 216-227

Mikael Onsjö, Osamu Watanabe: Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions. Theory Comput. Syst. 45(4): 926-942 (2009)

Mikael Onsjö, Osamu Watanabe: Finding Most Likely Solutions. Theory Comput. Syst. 45(4): 943 (2009)

Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe: Scale free interval graphs. Theor. Comput. Sci. 410(45): 4588-4600 (2009)

Manindra Agrawal, Osamu Watanabe: One-Way Functions and the Berman-Hartmanis Conjecture. IEEE Conference on Computational Complexity 2009: 194-202

Takeya Shigezumi, Yushi Uno, Osamu Watanabe: A Replacement Model for a Scale-Free Property of Cliques. CTW 2009: 285-289

Osamu Watanabe, Tomonori Iida, Takahiro Fukuhara, Hitoshi Kiya: Identification of JPEG 2000 images in encrypted domain for digital cinema. ICIP 2009: 2065-2068

Osamu Watanabe, Thomas Zeugmann (Eds.): Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA 2009, Sapporo, Japan, October 26-28, 2009. Proceedings. Lecture Notes in Computer Science 5792, Springer 2009, isbn 978-3-642-04943-9

Manindra Agrawal, Osamu Watanabe: One-Way Functions and the Isomorphism Conjecture. Electronic Colloquium on Computational Complexity (ECCC) 16: 19 (2009)

Akinori Kawachi, Osamu Watanabe: Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems. Electronic Colloquium on Computational Complexity (ECCC) 16: 23 (2009)

Osamu Watanabe, Rui Ito, Toshiya Mitomo, Shigehito Saigusa, Tadashi Arai, Takehiko Toyoda: A Triple-Band WCDMA Direct Conversion Receiver IC with Reduced Number of Off-Chip Components and Digital Baseband Control Signals. IEICE Transactions 91-C(6): 837-843 (2008)

José L. Balcázar, Yang Dai, Junichi Tanaka, Osamu Watanabe: Provably Fast Training Algorithms for Support Vector Machines. Theory Comput. Syst. 42(4): 568-595 (2008)

Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe: Scale Free Interval Graphs. AAIM 2008: 292-303

Hitoshi Kiya, Masahiro Iwahashi, Osamu Watanabe: A new class of lifting wavelet transform for guaranteeing losslessness of specific signals. ICASSP 2008: 3273-3276

Hitoshi Kiya, Masahiro Iwahashi, Osamu Watanabe: A new structure of lifting wavelet for reducing rounding error. ISCAS 2008: 2881-2884

Toshiya Mitomo, Osamu Watanabe, Ryuichi Fujimoto, Shunji Kawaguchi: A Quadrature Demodulator for WCDMA Receiver Using Common-Base Input Stage with Robustness to Transmitter Leakage. IEICE Transactions 90-C(6): 1241-1246 (2007)

Osamu Watanabe, Rui Ito, Shigehito Saigusa, Tadashi Arai, Tetsuro Itakura: A Fast f_c Automatic Tuning Circuit with Wide Tuning Range for WCDMA Direct Conversion Receiver Systems. IEICE Transactions 90-C(6): 1247-1252 (2007)

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe: Randomized Algorithms for 3-SAT. Theory Comput. Syst. 40(3): 249-262 (2007)

Osamu Watanabe, Mikael Onsjö: Finding Most Likely Solutions. CiE 2007: 758-767

Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe: On the Complexity of Kings. FCT 2007: 328-340

Toshiya Itoh, Osamu Watanabe: Weighted Random Popular Matchings. CoRR abs/0710.5338 (2007)

Jin-yi Cai, Osamu Watanabe: Random Access to Advice Strings and Collapsing Results. Algorithmica 46(1): 43-57 (2006)

Masaaki Fujiyoshi, Wataru Saitou, Osamu Watanabe, Hitoshi Kiya: Hierarchical Encryption of Multimedia Contents for Access Control. ICIP 2006: 1977-1980

Osamu Watanabe: A Neural Model for Stereo Transparency with the Population of the Disparity Energy Models. ICONIP (1) 2006: 165-174

Akio Kawana, Shinya Tsuzuki, Osamu Watanabe: Analysis of Dynamics of Cultured Neuronal Networks Using I&F Model. ICONIP (1) 2006: 547-553

Mikael Onsjö, Osamu Watanabe: A Simple Message Passing Algorithm for Graph Partitioning Problems. ISAAC 2006: 507-516

Osamu Watanabe, Masaki Yamamoto: Average-Case Analysis for the MAX-2SAT Problem. SAT 2006: 277-282

Toshiya Mitomo, Osamu Watanabe, Shoji Otaka, Ryuichi Fujimoto, Shunji Kawaguchi: A Low LO Leakage and Low Power LO Buffer for Direct-Conversion Quadrature Demodulator. IEICE Transactions 88-C(6): 1212-1217 (2005)

Masaaki Fujiyoshi, Osamu Watanabe, Hitoshi Kiya: A Method of Guaranteeing Image-Quality for Quantization-Based Watermarking Using a Nonorthogonal Transformation. IEICE Transactions 88-A(6): 1434-1442 (2005)

Ryoichi Kato, Osamu Watanabe: Substring search and repeat search using factor oracles. Inf. Process. Lett. 93(6): 269-274 (2005)

Osamu Watanabe, Masayuki Kikuchi: Nonlinearity of the population activity to transparent motion. Neural Networks 18(1): 15-22 (2005)

Osamu Watanabe: Sequential sampling techniques for algorithmic learning theory. Theor. Comput. Sci. 348(1): 3-14 (2005)

Shoko Imaizumi, Osamu Watanabe, Masaaki Fujiyoshi, Hitoshi Kiya: Generalized hierarchical encryption of JPEG 2000 codestreams for access control. ICIP (2) 2005: 1094-1097

Osamu Watanabe, Akiko Nakazaki, Hitoshi Kiya: A scalable encryption method allowing backward compatibility with JPEG2000 images. ISCAS (6) 2005: 6324-6327

Osamu Watanabe: Some Heuristic Analysis of Local Search Algorithms for SAT Problems. SAGA 2005: 14-25

Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe: The Complexity of Kings. CoRR abs/cs/0506055 (2005)

Jin-yi Cai, Osamu Watanabe: Relativized collapsing between BPP and PH under stringent oracle access. Inf. Process. Lett. 90(3): 147-154 (2004)

Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe: Games with Uniqueness Properties. Theory Comput. Syst. 37(1): 29-47 (2004)

Jin-yi Cai, Osamu Watanabe: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput. 33(4): 984-1009 (2004)

Kohei Hatano, Osamu Watanabe: Learning r-of-k Functions by Boosting. ALT 2004: 114-126

Osamu Watanabe, Akiko Nakazaki, Hitoshi Kiya: A fast image-scramble method using public-key encryption allowing backward compatibility with jpeg2000. ICIP 2004: 3435-3438

Jin-yi Cai, Osamu Watanabe: Random Access to Advice Strings and Collapsing Results. ISAAC 2004: 209-220

Osamu Watanabe, Masanori Idesawa: Computational model for neural representation of multiple disparities. Neural Networks 16(1): 25-37 (2003)

Jin-yi Cai, Osamu Watanabe: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON 2003: 202-211

Jin-yi Cai, Osamu Watanabe: Stringent Relativization. FSTTCS 2003: 408-419

Hitoshi Kiya, Shoko Imaizumi, Osamu Watanabe: Partial-scrambling of images encoded using JPEG2000 without generating marker codes. ICIP (3) 2003: 205-208

Osamu Watanabe, Hitoshi Kiya: ROI-based scalability for progressive transmission in JPEG2000 coding. ISCAS (2) 2003: 416-419

Osamu Watanabe, Takeshi Sawai, Hayato Takahashi: Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem. SAGA 2003: 50-60

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe: Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. Data Min. Knowl. Discov. 6(2): 131-152 (2002)

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe: The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. Theory Comput. Syst. 35(4): 449-463 (2002)

Osamu Watanabe, Arun Sharma: Preface. Theor. Comput. Sci. 288(2): 195-196 (2002)

Osamu Watanabe, Hitoshi Kiya: An extension of ROI-based scalability for progressive transmission in JPEG2000 coding. APCCAS (1) 2002: 535-540

Osamu Watanabe: Algorithmic Aspects of Boosting. Progress in Discovery Science 2002: 349-359

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe: A Probabilistic 3-SAT Algorithm Further Improved. STACS 2002: 192-202

Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe: Games with a Uniqueness Property. STACS 2002: 396-407

José L. Balcázar, Yang Dai, Osamu Watanabe: A Random Sampling Technique for Training Support Vector Machines. ALT 2001: 119-134

Kyoichi Okamoto, Osamu Watanabe: Deterministic Application of Grover's Quantum Search Algorithm. COCOON 2001: 493-501

José L. Balcázar, Yang Dai, Osamu Watanabe: Provably Fast Training Algorithms for Support Vector Machines. ICDM 2001: 43-50

Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem. RANDOM-APPROX 2001: 181-191

Ricard Gavaldà, Osamu Watanabe: Sequential Sampling Algorithms: Unified Analysis and Lower Bounds. SAGA 2001: 173-188

Osamu Watanabe: How Can Computer Science Contribute to Knowledge Discovery? SOFSEM 2001: 136-151

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe: On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. STACS 2001: 51-62

Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe: Corrigendum to "Upward separation for FewP and related classes". Inf. Process. Lett. 74(1-2): 89 (2000)

Wolfgang Lindner, Rainer Schuler, Osamu Watanabe: Resource-Bounded Measure and Learnability. Theory Comput. Syst. 33(2): 151-170 (2000)

Osamu Watanabe: Sequential Sampling Techniques for Algorithmic Learning Theory. ALT 2000: 27-40

Carlos Domingo, Osamu Watanabe: MadaBoost: A Modification of AdaBoost. COLT 2000: 180-189

Carlos Domingo, Osamu Watanabe: Scaling Up a Boosting-Based Learner via Adaptive Sampling. PAKDD 2000: 317-328

Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito (Eds.): Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference IFIP TCS 2000, Sendai, Japan, August 17-19, 2000, Proceedings. Lecture Notes in Computer Science 1872, Springer 2000, isbn 3-540-67823-9

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe: On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems. Electronic Colloquium on Computational Complexity (ECCC) 7(81) (2000)

Osamu Watanabe, Kunihiko Fukushima: Stereo algorithm that extracts a depth cue from interocularly unpaired points. Neural Networks 12(4-5): 569-578 (1999)

Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe: Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. COCOON 1999: 210-220

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe: Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. Discovery Science 1999: 172-183

Osamu Watanabe: From Computational Learning Theory to Discovery Science. ICALP 1999: 134-148

Osamu Watanabe, Takashi Yokomori (Eds.): Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 6-8, 1999, Proceedings. Lecture Notes in Computer Science 1720, Springer 1999, isbn 3-540-66748-2

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity. CoRR cs.CC/9907034 (1999)

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy. CoRR cs.CC/9907037 (1999)

Johannes Köbler, Osamu Watanabe: New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput. 28(1): 311-324 (1998)

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Boolean Operations, Joins, and the Extended Low Hierarchy. Theor. Comput. Sci. 205(1-2): 317-327 (1998)

Wolfgang Lindner, Rainer Schuler, Osamu Watanabe: Resource Bounded Measure and Learnability. IEEE Conference on Computational Complexity 1998: 261-

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe: Practical Algorithms for On-line Sampling. Discovery Science 1998: 150-161

Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki: A Role of Constraint in Self-Organization. RANDOM 1998: 307-318

Satoshi Horie, Osamu Watanabe: Hard instance generation for SAT. CoRR cs.CC/9809117 (1998)

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe: Practical algorithms for on-line sampling. CoRR cs.LG/9809122 (1998)

Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki: A role of constraint in self-organization. CoRR cs.NE/9809123 (1998)

Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe: Partial Occam's Razor and its Applications. Inf. Process. Lett. 64(4): 179-185 (1997)

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: Polynomial-Time Multi-Selectivity. J. UCS 3(3): 197-229 (1997)

Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe: Partial Occam's Razor and Its Applications. ALT 1997: 85-99

José L. Balcázar, Ricard Gavaldà, Osamu Watanabe: Coding Complexity: The Computational Complexity of Succinct Descriptions. Advances in Algorithms, Languages, and Complexity 1997: 73-91

Satoshi Horie, Osamu Watanabe: Hard Instance Generation for SAT (Extended Abstract). ISAAC 1997: 22-31

Ronald V. Book, Osamu Watanabe: On Random Hard Sets for NP. Inf. Comput. 125(1): 70-76 (1996)

Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-Selective Sets. ITA 30(2): 135-154 (1996)

Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of #P in the Context of PF ° #P. J. Comput. Syst. Sci. 53(2): 171-179 (1996)

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe: An Optimal Parallel Algorithm for Learning DFA. J. UCS 2(3): 97-112 (1996)

Hoong Chuin Lau, Osamu Watanabe: Randomized Approximation of the Constraint Satisfaction Problem. Nord. J. Comput. 3(4): 405-424 (1996)

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe: The Join Can Lower Complexity. COCOON 1996: 260-267

Osamu Watanabe, Osamu Yamashita: An Improvement of the Digital Cash Protocol of Okamoto and Ohta. ISAAC 1996: 436-445

Hoong Chuin Lau, Osamu Watanabe: Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract). SWAT 1996: 76-87

Luc Longpré, Osamu Watanabe: On Symmetry of Information and Polynomial Time Invertibility. Inf. Comput. 121(1): 14-22 (1995)

Rainer Schuler, Osamu Watanabe: Towards Average-Case Complexity Analysis of NP Optimization Problems. Structure in Complexity Theory Conference 1995: 148-159

Johannes Köbler, Osamu Watanabe: New Collapse Consequences of NP Having Small Circuits. ICALP 1995: 196-207

Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of GapP. Computational Complexity 4: 242-261 (1994)

Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe: Upward Separation for FewP and Related Classes. Inf. Process. Lett. 52(4): 175-180 (1994)

Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe: Instance Complexity. J. ACM 41(1): 96-121 (1994)

Osamu Watanabe: A Framework for Polynomial-Time Query Learnability. Mathematical Systems Theory 27(3): 211-229 (1994)

Osamu Watanabe, Ricard Gavaldà: Structural Analysis of Polynomial-Time Query Learnability. Mathematical Systems Theory 27(3): 231-256 (1994)

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe: The Query Complexity of Learning DFA. New Generation Comput. 12(4): 337-358 (1994)

Osamu Watanabe: Test Instance Generation for Promise NP Search Problems. Structure in Complexity Theory Conference 1994: 205-216

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe: An Optimal Parallel Algorithm for Learning DFA. COLT 1994: 208-217

Ronald V. Book, Osamu Watanabe: On Random Hard Sets for NP. ISAAC 1994: 47-55

Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-selective Sets. STACS 1994: 427-438

Osamu Watanabe, Seinosuke Toda: Structural Analysis of the Complexity of Inverse Functions. Mathematical Systems Theory 26(2): 203-214 (1993)

Ricard Gavaldà, Osamu Watanabe: On the Computational Complexity of Small Descriptions. SIAM J. Comput. 22(6): 1257-1275 (1993)

Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Closure Properties of #P in the Context of PF°#P. Structure in Complexity Theory Conference 1993: 139-146

Osamu Watanabe: On Polynomial Time One-Truth-Table Reducibility to a Sparse Set. J. Comput. Syst. Sci. 44(3): 500-516 (1992)

Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992)

Osamu Watanabe, Shouwen Tang: On Polynomial-Time Turing and Many-One Completeness in PSPACE. Theor. Comput. Sci. 97(2): 199-215 (1992)

Seinosuke Toda, Osamu Watanabe: Polynomial Time 1-Turing Reductions from #PH to #P. Theor. Comput. Sci. 100(1): 205-221 (1992)

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe: A Note on the Query Complexity of Learning DFA (Extended Abstract). ALT 1992: 53-62

Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: How Hard Are Sparse Sets? Structure in Complexity Theory Conference 1992: 222-238

Luc Longpré, Osamu Watanabe: On Symmetry of Information and Polynomial Time Invertibility. ISAAC 1992: 410-419

Kaoru Kurosawa, Osamu Watanabe: Computational and Statistical Indistinguishabilities. ISAAC 1992: 430-438

Osamu Watanabe: On the Complexity of Small Description and Related Topics. MFCS 1992: 82-94

Osamu Watanabe: On Intractability of the Class UP. Mathematical Systems Theory 24(1): 1-10 (1991)

Mitsunori Ogiwara, Osamu Watanabe: On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. SIAM J. Comput. 20(3): 471-483 (1991)

Osamu Watanabe: On the p-Isomorphism Conjecture. Theor. Comput. Sci. 83(2): 337-343 (1991)

Ricard Gavaldà, Osamu Watanabe: On the Computational Complexity of Small Descriptions. Structure in Complexity Theory Conference 1991: 89-101

Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. Structure in Complexity Theory Conference 1991: 220-229

Eric Allender, Osamu Watanabe: Kolmogorov Complexity and Degrees of Tally Sets. Inf. Comput. 86(2): 160-178 (1990)

Mitsunori Ogiwara, Osamu Watanabe: On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract). Structure in Complexity Theory Conference 1990: 2

Osamu Watanabe: A Formal Study of Learning via Queries. ICALP 1990: 139-152

Ricard Gavaldà, Leen Torenvliet, Osamu Watanabe, José L. Balcázar: Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract). MFCS 1990: 269-276

Osamu Watanabe, Seinosuke Toda: Structural Analyses on the Complexity of Inverting Functions. SIGAL International Symposium on Algorithms 1990: 31-38

Mitsunori Ogiwara, Osamu Watanabe: On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. STOC 1990: 457-467

Ronald V. Book, Osamu Watanabe: A view of structural complexity theory. Bulletin of the EATCS 39: 122-138 (1989)

Shouwen Tang, Osamu Watanabe: On Tally Relativizations of BP-Complexity Classes. SIAM J. Comput. 18(3): 449-462 (1989)

Osamu Watanabe, Shouwen Tang: On Polynomial Time Turing and Many-One Completeness in PSPACE. Structure in Complexity Theory Conference 1989: 15-23

Osamu Watanabe: On Hardness of One-Way Functions. Inf. Process. Lett. 27(3): 151-157 (1988)

Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe: Lowness Properties of Sets in the Exponential-Time Hierarchy. SIAM J. Comput. 17(3): 504-516 (1988)

Shouwen Tang, Osamu Watanabe: On tally relativizations of BP-complexity classes. Structure in Complexity Theory Conference 1988: 10-18

Eric Allender, Osamu Watanabe: Kolmogorov complexity and degrees of tally sets. Structure in Complexity Theory Conference 1988: 102-111

Osamu Watanabe: On <=^P_{1-tt}-Sparseness and Nondeterministic Complexity Classes (Extended Abstract). ICALP 1988: 697-709

Osamu Watanabe: On the structure of interactable complexity classes. Tokyo Inst. of Techn. 1987, pp. I-IV, 1-115

Osamu Watanabe: A Comparison of Polynomial Time Completeness Notions. Theor. Comput. Sci. 54: 249-265 (1987)

Osamu Watanabe: Polynomial time reducibility to a set of small density. Structure in Complexity Theory Conference 1987

Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe: What Is a Hard Instance of a Computational Problem?. Structure in Complexity Theory Conference 1986: 197-217

Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe: On Exponential Lowness. ICALP 1986: 40-49

Osamu Watanabe: On One-One Polynomial Time Equivalence Relations. Theor. Comput. Sci. 38: 157-165 (1985)

Osamu Watanabe: The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines. Theor. Comput. Sci. 24: 105-117 (1983)

Osamu Watanabe: A Fast Algorithm for Finding all Shortest Paths. Inf. Process. Lett. 13(1): 1-3 (1981)

Osamu Watanabe: Another Application of Recursion Introduction. Inf. Process. Lett. 10(3): 116-119 (1980)