Another Application of Recursion Introduction. - Osamu Watanabe 001 (Inf. Process. Lett., 1980)

A Fast Algorithm for Finding all Shortest Paths. - Osamu Watanabe 001 (Inf. Process. Lett., 1981)

The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines. - Osamu Watanabe 001 (Theor. Comput. Sci., 1983)

On One-One Polynomial Time Equivalence Relations. - Osamu Watanabe 001 (Theor. Comput. Sci., 1985)

What Is a Hard Instance of a Computational Problem?. - Ker-I Ko; Pekka Orponen; Uwe Schöning; Osamu Watanabe 001 (SCT, 1986)

On Exponential Lowness. - Ronald V. Book; Pekka Orponen; David A. Russo; Osamu Watanabe 001 (ICALP, 1986)

On the structure of interactable complexity classes. - Osamu Watanabe 001 (1987)

Polynomial time reducibility to a set of small density. - Osamu Watanabe 001 (SCT, 1987)

A Comparison of Polynomial Time Completeness Notions. - Osamu Watanabe 001 (Theor. Comput. Sci., 1987)

On ≤1-ttp-Sparseness and Nondeterministic Complexity Classes (Extended Abstract). - Osamu Watanabe 001 (ICALP, 1988)

On Hardness of One-Way Functions. - Osamu Watanabe 001 (Inf. Process. Lett., 1988)

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

A view of structural complexity theory. - Ronald V. Book; Osamu Watanabe 001 (Bull. EATCS, 1989)

On Tally Relativizations of BP-Complexity Classes. - Shouwen Tang; Osamu Watanabe 001 (SIAM J. Comput., 1989)

On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract). - Mitsunori Ogiwara; Osamu Watanabe 001 (SCT, 1990)

A Formal Study of Learning via Queries. - Osamu Watanabe 001 (ICALP, 1990)

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

Structural Analyses on the Complexity of Inverting Functions. - Osamu Watanabe 001; Seinosuke Toda (SIGAL International Symposium on Algorithms, 1990)

Kolmogorov Complexity and Degrees of Tally Sets - Eric Allender; Osamu Watanabe 001 (Inf. Comput., 1990)

On Intractability of the Class UP. - Osamu Watanabe 001 (Math. Syst. Theory, 1991)

On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. - Mitsunori Ogiwara; Osamu Watanabe 001 (SIAM J. Comput., 1991)

On the p-Isomorphism Conjecture. - Osamu Watanabe 001 (Theor. Comput. Sci., 1991)

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

How Hard Are Sparse Sets? - Lane A. Hemachandra; Mitsunori Ogiwara; Osamu Watanabe 001 (SCT, 1992)

Computational and Statistical Indistinguishabilities. - Kaoru Kurosawa; Osamu Watanabe 001 (ISAAC, 1992)

On the Complexity of Small Description and Related Topics. - Osamu Watanabe 001 (MFCS, 1992)

On Polynomial Time One-Truth-Table Reducibility to a Sparse Set. - Osamu Watanabe 001 (J. Comput. Syst. Sci., 1992)

Relating Equivalence and Reducibility to Sparse Sets. - Eric Allender; Lane A. Hemachandra; Mitsunori Ogiwara; Osamu Watanabe 001 (SIAM J. Comput., 1992)

Polynomial Time 1-Turing Reductions from #PH to #P. - Seinosuke Toda; Osamu Watanabe 001 (Theor. Comput. Sci., 1992)

On Polynomial-Time Turing and Many-One Completeness in PSPACE. - Osamu Watanabe 001; Shouwen Tang (Theor. Comput. Sci., 1992)

Structural Analysis of the Complexity of Inverse Functions. - Osamu Watanabe 001; Seinosuke Toda (Math. Syst. Theory, 1993)

On the Computational Complexity of Small Descriptions. - Ricard Gavaldà; Osamu Watanabe 001 (SIAM J. Comput., 1993)

A View of Structural Complexity Theory. - Ronald V. Book; Osamu Watanabe 001 (Current Trends in Theoretical Computer Science, 1993)

Test Instance Generation for Promise NP Search Problems. - Osamu Watanabe 001 (SCT, 1994)

On Closure Properties of GapP. - Thomas Thierauf; Seinosuke Toda; Osamu Watanabe 001 (Comput. Complex., 1994)

Upward Separation for FewP and Related Classes. - Rajesh P. N. Rao; Jörg Rothe; Osamu Watanabe 001 (Inf. Process. Lett., 1994)

Instance Complexity. - Pekka Orponen; Ker-I Ko; Uwe Schöning; Osamu Watanabe 001 (J. ACM, 1994)

A Framework for Polynomial-Time Query Learnability. - Osamu Watanabe 001 (Math. Syst. Theory, 1994)

Structural Analysis of Polynomial-Time Query Learnability. - Osamu Watanabe 001; Ricard Gavaldà (Math. Syst. Theory, 1994)

The Query Complexity of Learning DFA. - José L. Balcázar; Josep Díaz; Ricard Gavaldà; Osamu Watanabe 001 (New Gener. Comput., 1994)

Towards Average-Case Complexity Analysis of NP Optimization Problems. - Rainer Schuler; Osamu Watanabe 001 (SCT, 1995)

On Symmetry of Information and Polynomial Time Invertibility - Luc Longpré; Osamu Watanabe 001 (Inf. Comput., 1995)

The Join Can Lower Complexity. - Lane A. Hemaspaandra; Zhigen Jiang; Jörg Rothe; Osamu Watanabe 001 (COCOON, 1996)

An Improvement of the Digital Cash Protocol of Okamoto and Ohta. - Osamu Watanabe 001; Osamu Yamashita (ISAAC, 1996)

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

On Random Hard Sets for NP. - Ronald V. Book; Osamu Watanabe 001 (Inf. Comput., 1996)

On Sets Bounded Truth-Table Reducible to P-Selective Sets. - Thomas Thierauf; Seinosuke Toda; Osamu Watanabe 001 (RAIRO Theor. Informatics Appl., 1996)

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

An Optimal Parallel Algorithm for Learning DFA. - José L. Balcázar; Josep Díaz; Ricard Gavaldà; Osamu Watanabe 001 (J. Univers. Comput. Sci., 1996)

Randomized Approximation of the Constraint Satisfaction Problem. - Hoong Chuin Lau; Osamu Watanabe 001 (Nord. J. Comput., 1996)

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

Hard Instance Generation for SAT (Extended Abstract). - Satoshi Horie; Osamu Watanabe 001 (ISAAC, 1997)

Partial Occam's Razor and its Applications. - Carlos Domingo; Tatsuie Tsukiji; Osamu Watanabe 001 (Inf. Process. Lett., 1997)

Polynomial-Time Multi-Selectivity. - Lane A. Hemaspaandra; Zhigen Jiang; Jörg Rothe; Osamu Watanabe 001 (J. Univers. Comput. Sci., 1997)

Practical Algorithms for On-line Sampling. - Carlos Domingo; Ricard Gavaldà; Osamu Watanabe 001 (Discovery Science, 1998)

A Role of Constraint in Self-Organization. - Carlos Domingo; Osamu Watanabe 001; Tadashi Yamazaki (RANDOM, 1998)

Hard instance generation for SAT - Satoshi Horie; Osamu Watanabe 001 (CoRR, 1998)

New Collapse Consequences of NP Having Small Circuits. - Johannes Köbler; Osamu Watanabe 001 (SIAM J. Comput., 1998)

Boolean Operations, Joins, and the Extended Low Hierarchy. - Lane A. Hemaspaandra; Zhigen Jiang; Jörg Rothe; Osamu Watanabe 001 (Theor. Comput. Sci., 1998)

Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. - Peter Bro Miltersen; N. V. Vinodchandran; Osamu Watanabe 001 (COCOON, 1999)

From Computational Learning Theory to Discovery Science. - Osamu Watanabe 001 (ICALP, 1999)

MadaBoost: A Modification of AdaBoost. - Carlos Domingo; Osamu Watanabe 001 (COLT, 2000)

Scaling Up a Boosting-Based Learner via Adaptive Sampling. - Carlos Domingo; Osamu Watanabe 001 (PAKDD, 2000)

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems - Shin Aida; Rainer Schuler; Tatsuie Tsukiji; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2000)

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

Resource-Bounded Measure and Learnability. - Wolfgang Lindner 002; Rainer Schuler; Osamu Watanabe 001 (Theory Comput. Syst., 2000)

A Random Sampling Technique for Training Support Vector Machines. - José L. Balcázar; Yang Dai; Osamu Watanabe 001 (ALT, 2001)

Deterministic Application of Grover's Quantum Search Algorithm. - Kyoichi Okamoto; Osamu Watanabe 001 (COCOON, 2001)

Provably Fast Training Algorithms for Support Vector Machines. - José L. Balcázar; Yang Dai; Osamu Watanabe 001 (ICDM, 2001)

On a Generalized Ruin Problem. - Kazuyuki Amano; John Tromp; Paul M. B. Vitányi; Osamu Watanabe 001 (RANDOM-APPROX, 2001)

Sequential Sampling Algorithms: Unified Analysis and Lower Bounds. - Ricard Gavaldà; Osamu Watanabe 001 (SAGA, 2001)

How Can Computer Science Contribute to Knowledge Discovery? - Osamu Watanabe 001 (SOFSEM, 2001)

Algorithmic Aspects of Boosting. - Osamu Watanabe 001 (Progress in Discovery Science, 2002)

Games with a Uniqueness Property. - Shin Aida; Marcel Crâsmaru; Kenneth W. Regan; Osamu Watanabe 001 (STACS, 2002)

A Probabilistic 3-SAT Algorithm Further Improved. - Thomas Hofmeister; Uwe Schöning; Rainer Schuler; Osamu Watanabe 001 (STACS, 2002)

Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. - Carlos Domingo; Ricard Gavaldà; Osamu Watanabe 001 (Data Min. Knowl. Discov., 2002)

Preface - Osamu Watanabe 001; Arun Sharma 001 (Theor. Comput. Sci., 2002)

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

Stringent Relativization. - Jin-yi Cai; Osamu Watanabe 001 (FSTTCS, 2003)

Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem. - Osamu Watanabe 001; Takeshi Sawai; Hayato Takahashi 001 (SAGA, 2003)

Learning r-of-k Functions by Boosting. - Kohei Hatano; Osamu Watanabe 001 (ALT, 2004)

Relativized collapsing between BPP and PH under stringent oracle access. - Jin-yi Cai; Osamu Watanabe 001 (Inf. Process. Lett., 2004)

Games with Uniqueness Properties. - Shin Aida; Marcel Crâsmaru; Kenneth W. Regan; Osamu Watanabe 001 (Theory Comput. Syst., 2004)

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. - Jin-yi Cai; Osamu Watanabe 001 (SIAM J. Comput., 2004)

Some Heuristic Analysis of Local Search Algorithms for SAT Problems. - Osamu Watanabe 001 (SAGA, 2005)

The Complexity of Kings - Edith Hemaspaandra; Lane A. Hemaspaandra; Osamu Watanabe 001 (CoRR, 2005)

Substring search and repeat search using factor oracles. - Ryoichi Kato; Osamu Watanabe 001 (Inf. Process. Lett., 2005)

Sequential sampling techniques for algorithmic learning theory. - Osamu Watanabe 001 (Theor. Comput. Sci., 2005)

A Simple Message Passing Algorithm for Graph Partitioning Problems. - Mikael Onsjö; Osamu Watanabe 001 (ISAAC, 2006)

Random Access to Advice Strings and Collapsing Results. - Jin-yi Cai; Osamu Watanabe 001 (Algorithmica, 2006)

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

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

One-Way Functions and the Berman-Hartmanis Conjecture. - Manindra Agrawal; Osamu Watanabe 001 (CCC, 2009)

A Replacement Model for a Scale-Free Property of Cliques. - Takeya Shigezumi; Yushi Uno; Osamu Watanabe 001 (CTW, 2009)

One-Way Functions and the Isomorphism Conjecture. - Manindra Agrawal; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2009)

Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems. - Akinori Kawachi; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2009)

Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions. - Mikael Onsjö; Osamu Watanabe 001 (Theory Comput. Syst., 2009)

Finding Most Likely Solutions. - Mikael Onsjö; Osamu Watanabe 001 (Theory Comput. Syst., 2009)

Scale free interval graphs. - Naoto Miyoshi; Takeya Shigezumi; Ryuhei Uehara; Osamu Watanabe 001 (Theor. Comput. Sci., 2009)

Weighted random popular matchings. - Toshiya Itoh; Osamu Watanabe 001 (Random Struct. Algorithms, 2010)

Evaluating Root Parallelization in Go. - Yusuke Soejima; Akihiro Kishimoto; Osamu Watanabe 001 (IEEE Trans. Comput. Intell. AI Games, 2010)

On the complexity of kings. - Edith Hemaspaandra; Lane A. Hemaspaandra; Till Tantau; Osamu Watanabe 001 (Theor. Comput. Sci., 2010)

Average-case analysis for the MAX-2SAT problem. - Osamu Watanabe 001; Masaki Yamamoto 001 (Theor. Comput. Sci., 2010)

Evaluations of Hash Distributed A* in Optimal Sequence Alignment. - Yoshikazu Kobayashi; Akihiro Kishimoto; Osamu Watanabe 001 (IJCAI, 2011)

Is the Valiant-Vazirani Isolation Lemma Improvable? - Valentine Kabanets; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2011)

Spectral Analysis of Random Sparse Matrices. - Tomonori Ando; Yoshiyuki Kabashima; Hisanao Takahashi; Osamu Watanabe 001; Masaki Yamamoto 001 (IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2011)

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

Propagation Connectivity of Random Hypergraphs. - Amin Coja-Oghlan; Mikael Onsjö; Osamu Watanabe 001 (Electron. J. Comb., 2012)

Query Complexity and Error Tolerance of Witness Finding Algorithms. - Akinori Kawachi; Benjamin Rossman; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2012)

Interval graph representation with given interval and intersection lengths. - Sebastian Kuhnert; Johannes Köbler; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2012)

Estimating the Gowers Norm of Modulo Functions over Prime Fields. - Akinori Kawachi; Hidetoki Tanaka; Osamu Watanabe 001 (IEICE Trans. Inf. Syst., 2012)

An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. - Tatsuya Imai; Kotaro Nakagawa; Aduri Pavan; N. V. Vinodchandran; Osamu Watanabe 001 (CCC, 2013)

Message Passing Algorithms for MLS-3LIN Problem. - Osamu Watanabe 001 (Algorithmica, 2013)

Is Valiant-Vazirani's isolation probability improvable? - Holger Dell; Valentine Kabanets; Dieter van Melkebeek; Osamu Watanabe 001 (Comput. Complex., 2013)

A Short Implicant of CNFs with Relatively Many Satisfying Assignments. - Daniel M. Kane; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2013)

Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. - Tetsuo Asano; David G. Kirkpatrick; Kotaro Nakagawa; Osamu Watanabe 001 (MFCS (2), 2014)

Polynomial size linear programs for non-bipartite matching problems and other problems in P. - David Avis; David Bremner; Hans Raj Tiwary; Osamu Watanabe 001 (CoRR, 2014)

Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets. - Ryuhei Mori; Takeshi Koshiba; Osamu Watanabe 001; Masaki Yamamoto 001 (CoRR, 2014)

O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. - Tetsuo Asano; David G. Kirkpatrick; Kotaro Nakagawa; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2014)

Generalized Shortest Path Kernel on Graphs. - Linus Hermansson; Fredrik D. Johansson; Osamu Watanabe 001 (Discovery Science, 2015)

Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges. - Ryuhei Mori; Osamu Watanabe 001 (CoRR, 2015)

Limits of Minimum Circuit Size Problem as Oracle. - Shuichi Hirahara; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2015)

Relating Sublinear Space Computability Among Graph Connectivity and Related Problems. - Tatsuya Imai; Osamu Watanabe 001 (SOFSEM, 2016)

A Short Implicant of a CNF Formula with Many Satisfying Assignments. - Daniel Kane 001; Osamu Watanabe 001 (Algorithmica, 2016)

The Query Complexity of Witness Finding. - Akinori Kawachi; Benjamin Rossman; Osamu Watanabe 001 (Theory Comput. Syst., 2017)

Local Restrictions from the Furst-Saxe-Sipser Paper. - Suguru Tamaki; Osamu Watanabe 001 (Theory Comput. Syst., 2017)

On the optimality of lattices for the coppersmith technique. - Yoshinori Aono; Manindra Agrawal; Takakazu Satoh; Osamu Watanabe 001 (Appl. Algebra Eng. Commun. Comput., 2018)

Polynomial size linear programs for problems in P. - David Avis; David Bremner; Hans Raj Tiwary; Osamu Watanabe 001 (Discret. Appl. Math., 2019)

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs. - Ryo Ashida; Tatsuya Imai; Kotaro Nakagawa; A. Pavan 001; N. V. Vinodchandran; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2019)

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. - Shuichi Hirahara; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2019)

A Space-Efficient Separator Algorithm for Planar Graphs. - Ryo Ashida; Sebastian Kuhnert; Osamu Watanabe 001 (IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2019)

On Nonadaptive Security Reductions of Hitting Set Generators. - Shuichi Hirahara; Osamu Watanabe 001 (APPROX-RANDOM, 2020)

Space Efficient Separator Algorithms for Planar Graphs. - Osamu Watanabe 001 (WALCOM, 2020)

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. - Edith Hemaspaandra; Lane A. Hemaspaandra; Holger Spakowski; Osamu Watanabe 001 (Comput. Complex., 2020)

An improvement of the algorithm of Hertli for the unique 3SAT problem. - Tong Qin 003; Osamu Watanabe 001 (Theor. Comput. Sci., 2020)