Osamu Watanabe

ORCID

Publication Activity (10 Years)

Years Active: 1980-2020
Publications (10 Years): 24

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

Computational Complexity Conference

WALCOM

Tokyo Inst. of Techn. (PHD)

Education History

Tokyo Inst. of Techn.

PHD

Publications

Osamu Watanabe
Space Efficient Separator Algorithms for Planar Graphs. WALCOM (2020)
Tong Qin, Osamu Watanabe
An improvement of the algorithm of Hertli for the unique 3SAT problem. Theor. Comput. Sci. 806 (2020)
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. Comput. Complex. 29 (2) (2020)
Shuichi Hirahara, Osamu Watanabe
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Complexity and Approximation (2020)
Shuichi Hirahara, Osamu Watanabe
On Nonadaptive Security Reductions of Hitting Set Generators. APPROX-RANDOM (2020)
Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe
A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe
Polynomial size linear programs for problems in P. Discret. Appl. Math. 265 (2019)
Ryo Ashida, Sebastian Kuhnert, Osamu Watanabe
A Space-Efficient Separator Algorithm for Planar Graphs. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (9) (2019)
Shuichi Hirahara, Osamu Watanabe
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Electron. Colloquium Comput. Complex. 26 (2019)
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. MFCS (2018)
Tong Qin, Osamu Watanabe
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. WALCOM (2018)
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
On the optimality of lattices for the coppersmith technique. Appl. Algebra Eng. Commun. Comput. 29 (2) (2018)
Suguru Tamaki, Osamu Watanabe
Local Restrictions from the Furst-Saxe-Sipser Paper. Theory Comput. Syst. 60 (1) (2017)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
The Query Complexity of Witness Finding. Theory Comput. Syst. 61 (2) (2017)
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. CoRR (2017)
Tong Qin, Osamu Watanabe
An improvement of the algorithm of Hertli for the unique 3SAT problem. Electron. Colloquium Comput. Complex. 24 (2017)
Shuichi Hirahara, Osamu Watanabe
Limits of Minimum Circuit Size Problem as Oracle. Computational Complexity Conference (2016)
Tatsuya Imai, Osamu Watanabe
Relating Sublinear Space Computability Among Graph Connectivity and Related Problems. SOFSEM (2016)
Daniel Kane, Osamu Watanabe
A Short Implicant of a CNF Formula with Many Satisfying Assignments. Algorithmica 76 (4) (2016)
Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
Generalized Shortest Path Kernel on Graphs. CoRR (2015)
Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
Generalized Shortest Path Kernel on Graphs. Discovery Science (2015)
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
Interval graph representation with given interval and intersection lengths. J. Discrete Algorithms 34 (2015)
Ryuhei Mori, Osamu Watanabe
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges. CoRR (2015)
Shuichi Hirahara, Osamu Watanabe
Limits of Minimum Circuit Size Problem as Oracle. Electron. Colloquium Comput. Complex. 22 (2015)
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. MFCS (2) (2014)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
The Query Complexity of Witness Finding. CSR (2014)
David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe
Polynomial size linear programs for non-bipartite matching problems and other problems in P. CoRR (2014)
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. Electron. Colloquium Comput. Complex. 21 (2014)
Daniel M. Kane, Osamu Watanabe
A Short Implicant of a CNF Formula with Many Satisfying Assignments. ISAAC (2014)
Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets. CoRR (2014)
Osamu Watanabe
Message Passing Algorithms for MLS-3LIN Problem. Algorithmica 66 (4) (2013)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's isolation probability improvable? Comput. Complex. 22 (2) (2013)
Daniel M. Kane, Osamu Watanabe
A Short Implicant of CNFs with Relatively Many Satisfying Assignments. Electron. Colloquium Comput. Complex. 20 (2013)
Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. Computational Complexity Conference (2013)
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe
Is Valiant-Vazirani's Isolation Probability Improvable? Computational Complexity Conference (2012)
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
On the Optimality of Lattices for the Coppersmith Technique. ACISP (2012)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
Query Complexity and Error Tolerance of Witness Finding Algorithms. Electron. Colloquium Comput. Complex. 19 (2012)
Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe
Propagation Connectivity of Random Hypergraphs. Electron. J. Comb. 19 (1) (2012)
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe
On the Optimality of Lattices for the Coppersmith Technique. IACR Cryptol. ePrint Arch. 2012 (2012)
Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe
Estimating the Gowers Norm of Modulo Functions over Prime Fields. IEICE Trans. Inf. Syst. (3) (2012)
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe
Interval graph representation with given interval and intersection lengths. Electron. Colloquium Comput. Complex. 19 (2012)
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
Interval Graph Representation with Given Interval and Intersection Lengths. ISAAC (2012)
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques. J. Graph Algorithms Appl. 15 (5) (2011)
Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe
Evaluations of Hash Distributed A* in Optimal Sequence Alignment. IJCAI (2011)
Valentine Kabanets, Osamu Watanabe
Is the Valiant-Vazirani Isolation Lemma Improvable? Electron. Colloquium Comput. Complex. 18 (2011)
Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto
Spectral Analysis of Random Sparse Matrices. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (6) (2011)
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques. WALCOM (2010)
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
On the complexity of kings. Theor. Comput. Sci. 411 (4-5) (2010)
Yusuke Soejima, Akihiro Kishimoto, Osamu Watanabe
Evaluating Root Parallelization in Go. IEEE Trans. Comput. Intell. AI Games 2 (4) (2010)
Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe
Propagation Connectivity of Random Hypergraphs. APPROX-RANDOM (2010)
Toshiya Itoh, Osamu Watanabe
Weighted random popular matchings. Random Struct. Algorithms 37 (4) (2010)
Osamu Watanabe, Masaki Yamamoto
Average-case analysis for the MAX-2SAT problem. Theor. Comput. Sci. 411 (16-18) (2010)
Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
Scale free interval graphs. Theor. Comput. Sci. 410 (45) (2009)
Manindra Agrawal, Osamu Watanabe
One-Way Functions and the Isomorphism Conjecture. Electron. Colloquium Comput. Complex. 16 (2009)
Mikael Onsjö, Osamu Watanabe
Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions. Theory Comput. Syst. 45 (4) (2009)
Manindra Agrawal, Osamu Watanabe
One-Way Functions and the Berman-Hartmanis Conjecture. Computational Complexity Conference (2009)
Mikael Onsjö, Osamu Watanabe
Finding Most Likely Solutions. Theory Comput. Syst. 45 (4) (2009)
Akinori Kawachi, Osamu Watanabe
Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems. Electron. Colloquium Comput. Complex. 16 (2009)
Takeya Shigezumi, Yushi Uno, Osamu Watanabe
A Replacement Model for a Scale-Free Property of Cliques. CTW (2009)
José L. Balcázar, Yang Dai, Junichi Tanaka, Osamu Watanabe
Provably Fast Training Algorithms for Support Vector Machines. Theory Comput. Syst. 42 (4) (2008)
Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe
Scale Free Interval Graphs. AAIM (2008)
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
On the Complexity of Kings. FCT (2007)
Toshiya Itoh, Osamu Watanabe
Weighted Random Popular Matchings CoRR (2007)
Osamu Watanabe, Mikael Onsjö
Finding Most Likely Solutions. CiE (2007)
Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe
Randomized Algorithms for 3-SAT. Theory Comput. Syst. 40 (3) (2007)
Jin-yi Cai, Osamu Watanabe
Random Access to Advice Strings and Collapsing Results. Algorithmica 46 (1) (2006)
Osamu Watanabe, Masaki Yamamoto
Average-Case Analysis for the MAX-2SAT Problem. SAT (2006)
Mikael Onsjö, Osamu Watanabe
A Simple Message Passing Algorithm for Graph Partitioning Problems. ISAAC (2006)
Osamu Watanabe
Some Heuristic Analysis of Local Search Algorithms for SAT Problems. SAGA (2005)
Ryoichi Kato, Osamu Watanabe
Substring search and repeat search using factor oracles. Inf. Process. Lett. 93 (6) (2005)
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
The Complexity of Kings CoRR (2005)
Osamu Watanabe
Sequential sampling techniques for algorithmic learning theory. Theor. Comput. Sci. 348 (1) (2005)
Kohei Hatano, Osamu Watanabe
Learning r-of-k Functions by Boosting. ALT (2004)
Jin-yi Cai, Osamu Watanabe
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput. 33 (4) (2004)
Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe
Games with Uniqueness Properties. Theory Comput. Syst. 37 (1) (2004)
Jin-yi Cai, Osamu Watanabe
Random Access to Advice Strings and Collapsing Results. ISAAC (2004)
Jin-yi Cai, Osamu Watanabe
Relativized collapsing between BPP and PH under stringent oracle access. Inf. Process. Lett. 90 (3) (2004)
Jin-yi Cai, Osamu Watanabe
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON (2003)
Osamu Watanabe, Takeshi Sawai, Hayato Takahashi
Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem. SAGA (2003)
Jin-yi Cai, Osamu Watanabe
Stringent Relativization. FSTTCS (2003)
Osamu Watanabe
Algorithmic Aspects of Boosting. Progress in Discovery Science (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) (2002)
Carlos Domingo, Ricard Gavaldà, Osamu Watanabe
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. Data Min. Knowl. Discov. 6 (2) (2002)
Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe
A Probabilistic 3-SAT Algorithm Further Improved. STACS (2002)
Osamu Watanabe, Arun Sharma
Preface Theor. Comput. Sci. 288 (2) (2002)
Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe
Games with a Uniqueness Property. STACS (2002)
José L. Balcázar, Yang Dai, Osamu Watanabe
Provably Fast Training Algorithms for Support Vector Machines. ICDM (2001)
Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe
On a Generalized Ruin Problem. RANDOM-APPROX (2001)
Ricard Gavaldà, Osamu Watanabe
Sequential Sampling Algorithms: Unified Analysis and Lower Bounds. SAGA (2001)
José L. Balcázar, Yang Dai, Osamu Watanabe
A Random Sampling Technique for Training Support Vector Machines. ALT (2001)
Kyoichi Okamoto, Osamu Watanabe
Deterministic Application of Grover's Quantum Search Algorithm. COCOON (2001)
Osamu Watanabe
How Can Computer Science Contribute to Knowledge Discovery? SOFSEM (2001)
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)
Wolfgang Lindner, Rainer Schuler, Osamu Watanabe
Resource-Bounded Measure and Learnability. Theory Comput. Syst. 33 (2) (2000)
Carlos Domingo, Osamu Watanabe
Scaling Up a Boosting-Based Learner via Adaptive Sampling. PAKDD (2000)
Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe
Corrigendum to "Upward separation for FewP and related classes". Inf. Process. Lett. 74 (1-2) (2000)
Carlos Domingo, Osamu Watanabe
MadaBoost: A Modification of AdaBoost. COLT (2000)
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems Electron. Colloquium Comput. Complex. 7 (81) (2000)
Osamu Watanabe
Sequential Sampling Techniques for Algorithmic Learning Theory. ALT (2000)
Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. COCOON (1999)

Osamu Watanabe.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Osamu Watanabe