Osamu Watanabe

183 papers A* 10A 10B 29C 3Misc 6Journal 95Unranked 26
YearRankTypeTitle / Venue / Authors
2020 J jnl
An improvement of the algorithm of Hertli for the unique 3SAT problem.
Theor. Comput. Sci.
Tong Qin, Osamu Watanabe
2020 — conf
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Complexity and Approximation
Shuichi Hirahara, Osamu Watanabe
2020 — conf
On Nonadaptive Security Reductions of Hitting Set Generators.
APPROX-RANDOM
Shuichi Hirahara, Osamu Watanabe
2020 B conf
Space Efficient Separator Algorithms for Planar Graphs.
WALCOM
Osamu Watanabe
2020 J jnl
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
Comput. Complex.
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2019 J jnl
A Space-Efficient Separator Algorithm for Planar Graphs.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Ryo Ashida, Sebastian Kuhnert, Osamu Watanabe
2019 J jnl
A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.
Electron. Colloquium Comput. Complex.
Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe
2019 J jnl
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Osamu Watanabe
2019 J jnl
Polynomial size linear programs for problems in P.
Discret. Appl. Math.
David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe
2018 B conf
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem.
WALCOM
Tong Qin, Osamu Watanabe
2018 J jnl
On the optimality of lattices for the coppersmith technique.
Appl. Algebra Eng. Commun. Comput.
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
2018 B conf
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
MFCS
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2017 J jnl
An improvement of the algorithm of Hertli for the unique 3SAT problem.
Electron. Colloquium Comput. Complex.
Tong Qin, Osamu Watanabe
2017 J jnl
Local Restrictions from the Furst-Saxe-Sipser Paper.
Theory Comput. Syst.
Suguru Tamaki, Osamu Watanabe
2017 J jnl
The Query Complexity of Witness Finding.
Theory Comput. Syst.
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
2017 J jnl
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
CoRR
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2016 J jnl
A Short Implicant of a CNF Formula with Many Satisfying Assignments.
Algorithmica
Daniel Kane, Osamu Watanabe
2016 A conf
Limits of Minimum Circuit Size Problem as Oracle.
CCC
Shuichi Hirahara, Osamu Watanabe
2016 B conf
Relating Sublinear Space Computability Among Graph Connectivity and Related Problems.
SOFSEM
Tatsuya Imai, Osamu Watanabe
2015 B conf
Generalized Shortest Path Kernel on Graphs.
Discovery Science
Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
2015 J jnl
Generalized Shortest Path Kernel on Graphs.
CoRR
Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
2015 J jnl
Interval graph representation with given interval and intersection lengths.
J. Discrete Algorithms
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
2015 J jnl
Limits of Minimum Circuit Size Problem as Oracle.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Osamu Watanabe
2015 J jnl
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges.
CoRR
Ryuhei Mori, Osamu Watanabe
2014 B conf
A Short Implicant of a CNF Formula with Many Satisfying Assignments.
ISAAC
Daniel M. Kane, Osamu Watanabe
2014 J jnl
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets.
CoRR
Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto
2014 J jnl
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem.
Electron. Colloquium Comput. Complex.
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe
2014 J jnl
Polynomial size linear programs for non-bipartite matching problems and other problems in P.
CoRR
David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe
2014 Misc conf
The Query Complexity of Witness Finding.
CSR
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
2014 — conf
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability.
MFCS (2)
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe
2013 J jnl
A Short Implicant of CNFs with Relatively Many Satisfying Assignments.
Electron. Colloquium Comput. Complex.
Daniel M. Kane, Osamu Watanabe
2013 A conf
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.
CCC
Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe
2013 J jnl
Is Valiant-Vazirani's isolation probability improvable?
Comput. Complex.
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
2013 J jnl
Message Passing Algorithms for MLS-3LIN Problem.
Algorithmica
Osamu Watanabe
2012 J jnl
Estimating the Gowers Norm of Modulo Functions over Prime Fields.
IEICE Trans. Inf. Syst.
Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe
2012 B conf
Interval Graph Representation with Given Interval and Intersection Lengths.
ISAAC
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
2012 J jnl
Interval graph representation with given interval and intersection lengths.
Electron. Colloquium Comput. Complex.
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe
2012 A conf
Is Valiant-Vazirani's Isolation Probability Improvable?
CCC
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
2012 Misc conf
On the Optimality of Lattices for the Coppersmith Technique.
ACISP
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
2012 J jnl
On the Optimality of Lattices for the Coppersmith Technique.
IACR Cryptol. ePrint Arch.
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
2012 J jnl
Propagation Connectivity of Random Hypergraphs.
Electron. J. Comb.
Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe
2012 J jnl
Query Complexity and Error Tolerance of Witness Finding Algorithms.
Electron. Colloquium Comput. Complex.
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
2011 J jnl
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques.
J. Graph Algorithms Appl.
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
2011 B ed.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings
ISAAC
Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, Osamu Watanabe
2011 A* conf
Evaluations of Hash Distributed A* in Optimal Sequence Alignment.
IJCAI
Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe
2011 J jnl
Is the Valiant-Vazirani Isolation Lemma Improvable?
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Osamu Watanabe
2011 J jnl
Spectral Analysis of Random Sparse Matrices.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto
2010 B conf
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques.
WALCOM
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
2010 J jnl
Average-case analysis for the MAX-2SAT problem.
Theor. Comput. Sci.
Osamu Watanabe, Masaki Yamamoto
2010 J jnl
Evaluating Root Parallelization in Go.
IEEE Trans. Comput. Intell. AI Games
Yusuke Soejima, Akihiro Kishimoto, Osamu Watanabe
2010 J jnl
On the complexity of kings.
Theor. Comput. Sci.
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
2010 — conf
Propagation Connectivity of Random Hypergraphs.
APPROX-RANDOM
Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe
2010 J jnl
Weighted random popular matchings.
Random Struct. Algorithms
Toshiya Itoh, Osamu Watanabe
2009 C conf
A Replacement Model for a Scale-Free Property of Cliques.
CTW
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
2009 J jnl
Finding Most Likely Solutions.
Theory Comput. Syst.
Mikael Onsjö, Osamu Watanabe
2009 A conf
One-Way Functions and the Berman-Hartmanis Conjecture.
CCC
Manindra Agrawal, Osamu Watanabe
2009 J jnl
One-Way Functions and the Isomorphism Conjecture.
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Osamu Watanabe
2009 J jnl
Scale free interval graphs.
Theor. Comput. Sci.
Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
2009 — ed.
Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA 2009, Sapporo, Japan, October 26-28, 2009. Proceedings
SAGA
Osamu Watanabe, Thomas Zeugmann
2009 J jnl
Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems.
Electron. Colloquium Comput. Complex.
Akinori Kawachi, Osamu Watanabe
2009 J jnl
Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions.
Theory Comput. Syst.
Mikael Onsjö, Osamu Watanabe
2008 J jnl
Provably Fast Training Algorithms for Support Vector Machines.
Theory Comput. Syst.
José L. Balcázar, Yang Dai, Junichi Tanaka, Osamu Watanabe
2008 C conf
Scale Free Interval Graphs.
AAIM
Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
2007 C conf
Finding Most Likely Solutions.
CiE
Osamu Watanabe, Mikael Onsjö
2007 B conf
On the Complexity of Kings.
FCT
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
2007 J jnl
Randomized Algorithms for 3-SAT.
Theory Comput. Syst.
Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe
2007 J jnl
Weighted Random Popular Matchings
CoRR
Toshiya Itoh, Osamu Watanabe
2006 B conf
A Simple Message Passing Algorithm for Graph Partitioning Problems.
ISAAC
Mikael Onsjö, Osamu Watanabe
2006 A conf
Average-Case Analysis for the MAX-2SAT Problem.
SAT
Osamu Watanabe, Masaki Yamamoto
2006 J jnl
Random Access to Advice Strings and Collapsing Results.
Algorithmica
Jin-Yi Cai, Osamu Watanabe
2005 J jnl
Sequential sampling techniques for algorithmic learning theory.
Theor. Comput. Sci.
Osamu Watanabe
2005 — conf
Some Heuristic Analysis of Local Search Algorithms for SAT Problems.
SAGA
Osamu Watanabe
2005 J jnl
Substring search and repeat search using factor oracles.
Inf. Process. Lett.
Ryoichi Kato, Osamu Watanabe
2005 J jnl
The Complexity of Kings
CoRR
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
2004 J jnl
Games with Uniqueness Properties.
Theory Comput. Syst.
Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe
2004 B conf
Learning r-of-k Functions by Boosting.
ALT
Kohei Hatano, Osamu Watanabe
2004 J jnl
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.
SIAM J. Comput.
Jin-Yi Cai, Osamu Watanabe
2004 B conf
Random Access to Advice Strings and Collapsing Results.
ISAAC
Jin-Yi Cai, Osamu Watanabe
2004 J jnl
Relativized collapsing between BPP and PH under stringent oracle access.
Inf. Process. Lett.
Jin-Yi Cai, Osamu Watanabe
2003 — conf
Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem.
SAGA
Osamu Watanabe, Takeshi Sawai, Hayato Takahashi
2003 Misc conf
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.
COCOON
Jin-Yi Cai, Osamu Watanabe
2003 — conf
Stringent Relativization.
FSTTCS
Jin-Yi Cai, Osamu Watanabe
2002 A conf
A Probabilistic 3-SAT Algorithm Further Improved.
STACS
Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe
2002 J jnl
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Data Min. Knowl. Discov.
Carlos Domingo, Ricard Gavaldà, Osamu Watanabe
2002 — conf
Algorithmic Aspects of Boosting.
Progress in Discovery Science
Osamu Watanabe
2002 A conf
Games with a Uniqueness Property.
STACS
Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe
2002 J jnl
Preface
Theor. Comput. Sci.
Osamu Watanabe, Arun Sharma
2002 J jnl
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
Theory Comput. Syst.
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
2001 B conf
A Random Sampling Technique for Training Support Vector Machines.
ALT
José L. Balcázar, Yang Dai, Osamu Watanabe
2001 Misc conf
Deterministic Application of Grover's Quantum Search Algorithm.
COCOON
Kyoichi Okamoto, Osamu Watanabe
2001 B conf
How Can Computer Science Contribute to Knowledge Discovery?
SOFSEM
Osamu Watanabe
2001 — conf
On a Generalized Ruin Problem.
RANDOM-APPROX
Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe
2001 A conf
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
STACS
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
2001 A* conf
Provably Fast Training Algorithms for Support Vector Machines.
ICDM
José L. Balcázar, Yang Dai, Osamu Watanabe
2001 — conf
Sequential Sampling Algorithms: Unified Analysis and Lower Bounds.
SAGA
Ricard Gavaldà, Osamu Watanabe
2000 J jnl
Corrigendum to "Upward separation for FewP and related classes".
Inf. Process. Lett.
Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe
2000 A* conf
MadaBoost: A Modification of AdaBoost.
COLT
Carlos Domingo, Osamu Watanabe
2000 J jnl
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems
Electron. Colloquium Comput. Complex.
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
2000 J jnl
Resource-Bounded Measure and Learnability.
Theory Comput. Syst.
Wolfgang Lindner, Rainer Schuler, Osamu Watanabe
2000 B conf
Scaling Up a Boosting-Based Learner via Adaptive Sampling.
PAKDD
Carlos Domingo, Osamu Watanabe
2000 B conf
Sequential Sampling Techniques for Algorithmic Learning Theory.
ALT
Osamu Watanabe
2000 — ed.
Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, International Conference IFIP TCS 2000, Sendai, Japan, August 17-19, 2000, Proceedings
IFIP TCS
Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito
1999 B conf
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Discovery Science
Carlos Domingo, Ricard Gavaldà, Osamu Watanabe
1999 B ed.
Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 6-8, 1999, Proceedings
ALT
Osamu Watanabe, Takashi Yokomori
1999 J jnl
Boolean Operations, Joins, and the Extended Low Hierarchy
CoRR
Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe
1999 A* conf
From Computational Learning Theory to Discovery Science.
ICALP
Osamu Watanabe
1999 J jnl
Polynomial-Time Multi-Selectivity
CoRR
Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe
1999 Misc conf
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.
COCOON
Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe
1998 — conf
A Role of Constraint in Self-Organization.
RANDOM
Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki
1998 J jnl
A role of constraint in self-organization
CoRR
Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki
1998 J jnl
Boolean Operations, Joins, and the Extended Low Hierarchy.
Theor. Comput. Sci.
Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe
1998 J jnl
Hard instance generation for SAT
CoRR
Satoshi Horie, Osamu Watanabe
1998 J jnl
New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput.
Johannes Köbler, Osamu Watanabe
1998 B conf
Practical Algorithms for On-line Sampling.
Discovery Science
Carlos Domingo, Ricard Gavaldà, Osamu Watanabe
1998 J jnl
Practical algorithms for on-line sampling
CoRR
Carlos Domingo, Ricard Gavaldà, Osamu Watanabe
1998 A conf
Resource Bounded Measure and Learnability.
CCC
Wolfgang Lindner, Rainer Schuler, Osamu Watanabe
1997 — conf
Coding Complexity: The Computational Complexity of Succinct Descriptions.
Advances in Algorithms, Languages, and Complexity
José L. Balcázar, Ricard Gavaldà, Osamu Watanabe
1997 B conf
Hard Instance Generation for SAT (Extended Abstract).
ISAAC
Satoshi Horie, Osamu Watanabe
1997 B conf
Partial Occam's Razor and Its Applications.
ALT
Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe
1997 J jnl
Partial Occam's Razor and its Applications.
Inf. Process. Lett.
Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe
1997 J jnl
Polynomial-Time Multi-Selectivity.
J. Univers. Comput. Sci.
Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe
1996 B conf
An Improvement of the Digital Cash Protocol of Okamoto and Ohta.
ISAAC
Osamu Watanabe, Osamu Yamashita
1996 J jnl
An Optimal Parallel Algorithm for Learning DFA.
J. Univers. Comput. Sci.
José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
1996 J jnl
On Closure Properties of #P in the Context of PF ° #P.
J. Comput. Syst. Sci.
Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1996 J jnl
On Random Hard Sets for NP.
Inf. Comput.
Ronald V. Book, Osamu Watanabe
1996 J jnl
On Sets Bounded Truth-Table Reducible to P-Selective Sets.
RAIRO Theor. Informatics Appl.
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1996 — conf
Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract).
SWAT
Hoong Chuin Lau, Osamu Watanabe
1996 J jnl
Randomized Approximation of the Constraint Satisfaction Problem.
Nord. J. Comput.
Hoong Chuin Lau, Osamu Watanabe
1996 Misc conf
The Join Can Lower Complexity.
COCOON
Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe
1995 A* conf
New Collapse Consequences of NP Having Small Circuits.
ICALP
Johannes Köbler, Osamu Watanabe
1995 J jnl
On Symmetry of Information and Polynomial Time Invertibility
Inf. Comput.
Luc Longpré, Osamu Watanabe
1995 — conf
Towards Average-Case Complexity Analysis of NP Optimization Problems.
SCT
Rainer Schuler, Osamu Watanabe
1994 J jnl
A Framework for Polynomial-Time Query Learnability.
Math. Syst. Theory
Osamu Watanabe
1994 A* conf
An Optimal Parallel Algorithm for Learning DFA.
COLT
José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
1994 J jnl
Instance Complexity.
J. ACM
Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe
1994 J jnl
On Closure Properties of GapP.
Comput. Complex.
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1994 B conf
On Random Hard Sets for NP.
ISAAC
Ronald V. Book, Osamu Watanabe
1994 A conf
On Sets Bounded Truth-Table Reducible to P-selective Sets.
STACS
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1994 J jnl
Structural Analysis of Polynomial-Time Query Learnability.
Math. Syst. Theory
Osamu Watanabe, Ricard Gavaldà
1994 — conf
Test Instance Generation for Promise NP Search Problems.
SCT
Osamu Watanabe
1994 J jnl
The Query Complexity of Learning DFA.
New Gener. Comput.
José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
1994 J jnl
Upward Separation for FewP and Related Classes.
Inf. Process. Lett.
Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe
1993 — ch.
A View of Structural Complexity Theory.
Current Trends in Theoretical Computer Science
Ronald V. Book, Osamu Watanabe
1993 — conf
On Closure Properties of #P in the Context of PF°#P.
SCT
Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe
1993 J jnl
On the Computational Complexity of Small Descriptions.
SIAM J. Comput.
Ricard Gavaldà, Osamu Watanabe
1993 J jnl
Structural Analysis of the Complexity of Inverse Functions.
Math. Syst. Theory
Osamu Watanabe, Seinosuke Toda
1992 B conf
A Note on the Query Complexity of Learning DFA (Extended Abstract).
ALT
José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
1992 B conf
Computational and Statistical Indistinguishabilities.
ISAAC
Kaoru Kurosawa, Osamu Watanabe
1992 — conf
How Hard Are Sparse Sets?
SCT
Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1992 J jnl
On Polynomial Time One-Truth-Table Reducibility to a Sparse Set.
J. Comput. Syst. Sci.
Osamu Watanabe
1992 J jnl
On Polynomial-Time Turing and Many-One Completeness in PSPACE.
Theor. Comput. Sci.
Osamu Watanabe, Shouwen Tang
1992 B conf
On Symmetry of Information and Polynomial Time Invertibility.
ISAAC
Luc Longpré, Osamu Watanabe
1992 B conf
On the Complexity of Small Description and Related Topics.
MFCS
Osamu Watanabe
1992 J jnl
Polynomial Time 1-Turing Reductions from #PH to #P.
Theor. Comput. Sci.
Seinosuke Toda, Osamu Watanabe
1992 J jnl
Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput.
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1991 J jnl
On Intractability of the Class UP.
Math. Syst. Theory
Osamu Watanabe
1991 J jnl
On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets.
SIAM J. Comput.
Mitsunori Ogiwara, Osamu Watanabe
1991 — conf
On the Computational Complexity of Small Descriptions.
SCT
Ricard Gavaldà, Osamu Watanabe
1991 J jnl
On the p-Isomorphism Conjecture.
Theor. Comput. Sci.
Osamu Watanabe
1991 — conf
Relating Equivalence and Reducibility to Sparse Sets.
SCT
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1990 A* conf
A Formal Study of Learning via Queries.
ICALP
Osamu Watanabe
1990 B conf
Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract).
MFCS
Ricard Gavaldà, Leen Torenvliet, Osamu Watanabe, José L. Balcázar
1990 J jnl
Kolmogorov Complexity and Degrees of Tally Sets
Inf. Comput.
Eric Allender, Osamu Watanabe
1990 A* conf
On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
STOC
Mitsunori Ogiwara, Osamu Watanabe
1990 — conf
On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract).
SCT
Mitsunori Ogiwara, Osamu Watanabe
1990 — conf
Structural Analyses on the Complexity of Inverting Functions.
SIGAL International Symposium on Algorithms
Osamu Watanabe, Seinosuke Toda
1989 J jnl
A view of structural complexity theory.
Bull. EATCS
Ronald V. Book, Osamu Watanabe
1989 — conf
On Polynomial Time Turing and Many-One Completeness in PSPACE.
SCT
Osamu Watanabe, Shouwen Tang
1989 J jnl
On Tally Relativizations of BP-Complexity Classes.
SIAM J. Comput.
Shouwen Tang, Osamu Watanabe
1988 — conf
Kolmogorov complexity and degrees of tally sets.
SCT
Eric Allender, Osamu Watanabe
1988 J jnl
Lowness Properties of Sets in the Exponential-Time Hierarchy.
SIAM J. Comput.
Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe
1988 J jnl
On Hardness of One-Way Functions.
Inf. Process. Lett.
Osamu Watanabe
1988 — conf
On tally relativizations of BP-complexity classes.
SCT
Shouwen Tang, Osamu Watanabe
1988 A* conf
On ≤
ICALP
Osamu Watanabe
1987 J jnl
A Comparison of Polynomial Time Completeness Notions.
Theor. Comput. Sci.
Osamu Watanabe
1987 — —
On the structure of interactable complexity classes.
Osamu Watanabe
1987 — conf
Polynomial time reducibility to a set of small density.
SCT
Osamu Watanabe
1986 A* conf
On Exponential Lowness.
ICALP
Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe
1986 — conf
What Is a Hard Instance of a Computational Problem?.
SCT
Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe
1985 J jnl
On One-One Polynomial Time Equivalence Relations.
Theor. Comput. Sci.
Osamu Watanabe
1983 J jnl
The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines.
Theor. Comput. Sci.
Osamu Watanabe
1981 J jnl
A Fast Algorithm for Finding all Shortest Paths.
Inf. Process. Lett.
Osamu Watanabe
1980 J jnl
Another Application of Recursion Introduction.
Inf. Process. Lett.
Osamu Watanabe