Osamu Watanabe

According to our database, Osamu Watanabe authored at least 135 papers between 1980 and 2020.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2020

An improvement of the algorithm of Hertli for the unique 3SAT problem.

Tong Qin, Osamu Watanabe

Theor. Comput. Sci., 2020

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.

Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe

Comput. Complex., 2020

Space Efficient Separator Algorithms for Planar Graphs.

Osamu Watanabe

Proceedings of the WALCOM: Algorithms and Computation - 14th International Conference, 2020

On Nonadaptive Security Reductions of Hitting Set Generators.

Shuichi Hirahara, Osamu Watanabe

Proceedings of the Approximation, 2020

2019

A Space-Efficient Separator Algorithm for Planar Graphs.

Ryo Ashida, Sebastian Kuhnert, Osamu Watanabe

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2019

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.

Shuichi Hirahara, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2019

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2019

Polynomial size linear programs for problems in P.

David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe

Discret. Appl. Math., 2019

2018

On the optimality of lattices for the coppersmith technique.

Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe

Appl. Algebra Eng. Commun. Comput., 2018

2017

Local Restrictions from the Furst-Saxe-Sipser Paper.

Suguru Tamaki, Osamu Watanabe

Theory Comput. Syst., 2017

The Query Complexity of Witness Finding.

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Theory Comput. Syst., 2017

2016

A Short Implicant of a CNF Formula with Many Satisfying Assignments.

Daniel Kane, Osamu Watanabe

Algorithmica, 2016

Relating Sublinear Space Computability Among Graph Connectivity and Related Problems.

Tatsuya Imai, Osamu Watanabe

Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

2015

Limits of Minimum Circuit Size Problem as Oracle.

Shuichi Hirahara, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2015

Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges.

Ryuhei Mori, Osamu Watanabe

CoRR, 2015

Generalized Shortest Path Kernel on Graphs.

Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe

Proceedings of the Discovery Science - 18th International Conference, 2015

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

Electron. Colloquium Comput. Complex., 2014

Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets.

Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto

CoRR, 2014

Polynomial size linear programs for non-bipartite matching problems and other problems in P.

David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe

CoRR, 2014

Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability.

Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

A Short Implicant of CNFs with Relatively Many Satisfying Assignments.

Daniel M. Kane, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2013

Is Valiant-Vazirani's isolation probability improvable?

Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe

Comput. Complex., 2013

Message Passing Algorithms for MLS-3LIN Problem.

Osamu Watanabe

Algorithmica, 2013

An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.

Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Estimating the Gowers Norm of Modulo Functions over Prime Fields.

Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe

IEICE Trans. Inf. Syst., 2012

Interval graph representation with given interval and intersection lengths.

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2012

Query Complexity and Error Tolerance of Witness Finding Algorithms.

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2012

Propagation Connectivity of Random Hypergraphs.

Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe

Electron. J. Comb., 2012

2011

A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques.

Takeya Shigezumi, Yushi Uno, Osamu Watanabe

J. Graph Algorithms Appl., 2011

Spectral Analysis of Random Sparse Matrices.

Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2011

Is the Valiant-Vazirani Isolation Lemma Improvable?

Valentine Kabanets, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2011

Evaluations of Hash Distributed A* in Optimal Sequence Alignment.

Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe

Proceedings of the IJCAI 2011, 2011

2010

Average-case analysis for the MAX-2SAT problem.

Osamu Watanabe, Masaki Yamamoto

Theor. Comput. Sci., 2010

On the complexity of kings.

Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe

Theor. Comput. Sci., 2010

Evaluating Root Parallelization in Go.

Yusuke Soejima, Akihiro Kishimoto, Osamu Watanabe

IEEE Trans. Comput. Intell. AI Games, 2010

Weighted random popular matchings.

Toshiya Itoh, Osamu Watanabe

Random Struct. Algorithms, 2010

2009

Scale free interval graphs.

Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe

Theor. Comput. Sci., 2009

Finding Most Likely Solutions.

Mikael Onsjö, Osamu Watanabe

Theory Comput. Syst., 2009

Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions.

Mikael Onsjö, Osamu Watanabe

Theory Comput. Syst., 2009

Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems.

Akinori Kawachi, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2009

One-Way Functions and the Isomorphism Conjecture.

Manindra Agrawal, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2009

A Replacement Model for a Scale-Free Property of Cliques.

Takeya Shigezumi, Yushi Uno, Osamu Watanabe

Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

One-Way Functions and the Berman-Hartmanis Conjecture.

Manindra Agrawal, Osamu Watanabe

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Provably Fast Training Algorithms for Support Vector Machines.

José L. Balcázar, Yang Dai, Junichi Tanaka, Osamu Watanabe

Theory Comput. Syst., 2008

2007

Randomized Algorithms for 3-SAT.

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe

Theory Comput. Syst., 2007

2006

Random Access to Advice Strings and Collapsing Results.

Jin-yi Cai, Osamu Watanabe

Algorithmica, 2006

A Simple Message Passing Algorithm for Graph Partitioning Problems.

Mikael Onsjö, Osamu Watanabe

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

Sequential sampling techniques for algorithmic learning theory.

Osamu Watanabe

Theor. Comput. Sci., 2005

Substring search and repeat search using factor oracles.

Ryoichi Kato, Osamu Watanabe

Inf. Process. Lett., 2005

The Complexity of Kings

Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe

CoRR, 2005

Some Heuristic Analysis of Local Search Algorithms for SAT Problems.

Osamu Watanabe

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2005

2004

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.

Jin-yi Cai, Osamu Watanabe

SIAM J. Comput., 2004

Games with Uniqueness Properties.

Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe

Theory Comput. Syst., 2004

Relativized collapsing between BPP and PH under stringent oracle access.

Jin-yi Cai, Osamu Watanabe

Inf. Process. Lett., 2004

Learning r-of-k Functions by Boosting.

Kohei Hatano, Osamu Watanabe

Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003

Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem.

Osamu Watanabe, Takeshi Sawai, Hayato Takahashi

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

Stringent Relativization.

Jin-yi Cai, Osamu Watanabe

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.

Jin-yi Cai, Osamu Watanabe

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002

Preface

Osamu Watanabe, Arun Sharma

Theor. Comput. Sci., 2002

Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe

Data Min. Knowl. Discov., 2002

A Probabilistic 3-SAT Algorithm Further Improved.

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Games with a Uniqueness Property.

Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Algorithmic Aspects of Boosting.

Osamu Watanabe

Proceedings of the Progress in Discovery Science, 2002

2001

How Can Computer Science Contribute to Knowledge Discovery?

Osamu Watanabe

Proceedings of the SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics Piestany, Slovak Republic, November 24, 2001

Sequential Sampling Algorithms: Unified Analysis and Lower Bounds.

Ricard Gavaldà, Osamu Watanabe

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

On a Generalized Ruin Problem.

Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe

Proceedings of the Approximation, 2001

Provably Fast Training Algorithms for Support Vector Machines.

José L. Balcázar, Yang Dai, Osamu Watanabe

Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November, 2001

Deterministic Application of Grover's Quantum Search Algorithm.

Kyoichi Okamoto, Osamu Watanabe

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

A Random Sampling Technique for Training Support Vector Machines.

José L. Balcázar, Yang Dai, Osamu Watanabe

Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

2000

Resource-Bounded Measure and Learnability.

Wolfgang Lindner, Rainer Schuler, Osamu Watanabe

Theory Comput. Syst., 2000

Corrigendum to "Upward separation for FewP and related classes".

Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe

Inf. Process. Lett., 2000

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2000

Scaling Up a Boosting-Based Learner via Adaptive Sampling.

Carlos Domingo, Osamu Watanabe

Proceedings of the Knowledge Discovery and Data Mining, 2000

MadaBoost: A Modification of AdaBoost.

Carlos Domingo, Osamu Watanabe

Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999

From Computational Learning Theory to Discovery Science.

Osamu Watanabe

Proceedings of the Automata, 1999

Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.

Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

Boolean Operations, Joins, and the Extended Low Hierarchy.

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe

Theor. Comput. Sci., 1998

New Collapse Consequences of NP Having Small Circuits.

Johannes Köbler, Osamu Watanabe

SIAM J. Comput., 1998

Hard instance generation for SAT

Satoshi Horie, Osamu Watanabe

CoRR, 1998

A Role of Constraint in Self-Organization.

Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Practical Algorithms for On-line Sampling.

Carlos Domingo, Ricard Gavaldà, Osamu Watanabe

Proceedings of the Discovery Science, 1998

1997

Polynomial-Time Multi-Selectivity.

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe

J. Univers. Comput. Sci., 1997

Partial Occam's Razor and its Applications.

Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe

Inf. Process. Lett., 1997

Hard Instance Generation for SAT (Extended Abstract).

Satoshi Horie, Osamu Watanabe

Proceedings of the Algorithms and Computation, 8th International Symposium, 1997

Coding Complexity: The Computational Complexity of Succinct Descriptions.

José L. Balcázar, Ricard Gavaldà, Osamu Watanabe

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

Randomized Approximation of the Constraint Satisfaction Problem.

Hoong Chuin Lau, Osamu Watanabe

Nord. J. Comput., 1996

An Optimal Parallel Algorithm for Learning DFA.

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe

J. Univers. Comput. Sci., 1996

On Closure Properties of #P in the Context of PF ° #P.

Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe

J. Comput. Syst. Sci., 1996

On Sets Bounded Truth-Table Reducible to P-Selective Sets.

Thomas Thierauf, Seinosuke Toda, Osamu Watanabe

RAIRO Theor. Informatics Appl., 1996

On Random Hard Sets for NP.

Ronald V. Book, Osamu Watanabe

Inf. Comput., 1996

Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract).

Hoong Chuin Lau, Osamu Watanabe

Proceedings of the Algorithm Theory, 1996

An Improvement of the Digital Cash Protocol of Okamoto and Ohta.

Osamu Watanabe, Osamu Yamashita

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

The Join Can Lower Complexity.

Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

On Symmetry of Information and Polynomial Time Invertibility

Luc Longpré, Osamu Watanabe

Inf. Comput., August, 1995

Towards Average-Case Complexity Analysis of NP Optimization Problems.

Rainer Schuler, Osamu Watanabe

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

The Query Complexity of Learning DFA.

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe

New Gener. Comput., 1994

Structural Analysis of Polynomial-Time Query Learnability.

Osamu Watanabe, Ricard Gavaldà

Math. Syst. Theory, 1994

A Framework for Polynomial-Time Query Learnability.

Osamu Watanabe

Math. Syst. Theory, 1994

Instance Complexity.

Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe

J. ACM, 1994

Upward Separation for FewP and Related Classes.

Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe

Inf. Process. Lett., 1994

On Closure Properties of GapP.

Thomas Thierauf, Seinosuke Toda, Osamu Watanabe

Comput. Complex., 1994

Test Instance Generation for Promise NP Search Problems.

Osamu Watanabe

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

A View of Structural Complexity Theory.

Ronald V. Book, Osamu Watanabe

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On the Computational Complexity of Small Descriptions.

Ricard Gavaldà, Osamu Watanabe

SIAM J. Comput., 1993

Structural Analysis of the Complexity of Inverse Functions.

Osamu Watanabe, Seinosuke Toda

Math. Syst. Theory, 1993

1992

On Polynomial-Time Turing and Many-One Completeness in PSPACE.

Osamu Watanabe, Shouwen Tang

Theor. Comput. Sci., 1992

Polynomial Time 1-Turing Reductions from #PH to #P.

Seinosuke Toda, Osamu Watanabe

Theor. Comput. Sci., 1992

Relating Equivalence and Reducibility to Sparse Sets.

Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe

SIAM J. Comput., 1992

On Polynomial Time One-Truth-Table Reducibility to a Sparse Set.

Osamu Watanabe

J. Comput. Syst. Sci., 1992

On the Complexity of Small Description and Related Topics.

Osamu Watanabe

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Computational and Statistical Indistinguishabilities.

Kaoru Kurosawa, Osamu Watanabe

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

How Hard Are Sparse Sets?

Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

A Note on the Query Complexity of Learning DFA (Extended Abstract).

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe

Proceedings of the Algorithmic Learning Theory, Third Workshop, 1992

1991

On the p-Isomorphism Conjecture.

Osamu Watanabe

Theor. Comput. Sci., 1991

On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets.

Mitsunori Ogiwara, Osamu Watanabe

SIAM J. Comput., 1991

On Intractability of the Class UP.

Osamu Watanabe

Math. Syst. Theory, 1991

1990

Kolmogorov Complexity and Degrees of Tally Sets

Eric Allender, Osamu Watanabe

Inf. Comput., June, 1990

Structural Analyses on the Complexity of Inverting Functions.

Osamu Watanabe, Seinosuke Toda

Proceedings of the Algorithms, 1990

Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract).

Ricard Gavaldà, Leen Torenvliet, Osamu Watanabe, José L. Balcázar

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

A Formal Study of Learning via Queries.

Osamu Watanabe

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract).

Mitsunori Ogiwara, Osamu Watanabe

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

On Tally Relativizations of BP-Complexity Classes.

Shouwen Tang, Osamu Watanabe

SIAM J. Comput., 1989

A view of structural complexity theory.

Ronald V. Book, Osamu Watanabe

Bull. EATCS, 1989

1988

Lowness Properties of Sets in the Exponential-Time Hierarchy.

Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe

SIAM J. Comput., 1988

On Hardness of One-Way Functions.

Osamu Watanabe

Inf. Process. Lett., 1988

On ≤_1-tt^p-Sparseness and Nondeterministic Complexity Classes (Extended Abstract).

Osamu Watanabe

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987

A Comparison of Polynomial Time Completeness Notions.

Osamu Watanabe

Theor. Comput. Sci., 1987

Polynomial time reducibility to a set of small density.

Osamu Watanabe

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

On the structure of interactable complexity classes.

Osamu Watanabe

PhD thesis, 1987

1986

On Exponential Lowness.

Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

What Is a Hard Instance of a Computational Problem?.

Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe

Proceedings of the Structure in Complexity Theory, 1986

1985

On One-One Polynomial Time Equivalence Relations.

Osamu Watanabe

Theor. Comput. Sci., 1985

1983

The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines.

Osamu Watanabe

Theor. Comput. Sci., 1983

1981

A Fast Algorithm for Finding all Shortest Paths.

Osamu Watanabe

Inf. Process. Lett., 1981

1980

Another Application of Recursion Introduction.

Osamu Watanabe

Inf. Process. Lett., 1980