default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDOsamu Watanabe 0001
Person information
- affiliation: Tokyo Institute of Technology, Japan
Other persons with the same name
- Osamu Watanabe — disambiguation page
- Osamu Watanabe 0002 — Takushoku University, Japan
- Osamu Watanabe 0003 — Toshiba, Kawasaki, Japan
- Osamu Watanabe 0004 — Muroran Institute of Technology, Hokkaido, Japan
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2020
[j70]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): 7 (2020)- [j69]Tong Qin, Osamu Watanabe:
An improvement of the algorithm of Hertli for the unique 3SAT problem. Theor. Comput. Sci. 806: 70-80 (2020) - [c82]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Security Reductions of Hitting Set Generators. APPROX-RANDOM 2020: 15:1-15:14 - [c81]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Complexity and Approximation 2020: 67-79 - [c80]Osamu Watanabe:
Space Efficient Separator Algorithms for Planar Graphs. WALCOM 2020: 15-21
2010 – 2019
- 2019
- [j68]David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe:
Polynomial size linear programs for problems in P. Discret. Appl. Math. 265: 22-39 (2019) - [j67]Ryo Ashida, Sebastian Kuhnert, Osamu Watanabe:
A Space-Efficient Separator Algorithm for Planar Graphs. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 102-A(9): 1007-1016 (2019) - [i25]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. TR19 (2019) - [i24]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j66]Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe:
On the optimality of lattices for the coppersmith technique. Appl. Algebra Eng. Commun. Comput. 29(2): 169-195 (2018) - [c79]Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe:
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. MFCS 2018: 51:1-51:14 - [c78]Tong Qin, Osamu Watanabe:
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. WALCOM 2018: 93-105 - 2017
- [j65]Suguru Tamaki, Osamu Watanabe:
Local Restrictions from the Furst-Saxe-Sipser Paper. Theory Comput. Syst. 60(1): 20-32 (2017) - [j64]Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
The Query Complexity of Witness Finding. Theory Comput. Syst. 61(2): 305-321 (2017) - [i23]Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe:
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. CoRR abs/1711.01250 (2017) - [i22]Tong Qin, Osamu Watanabe:
An improvement of the algorithm of Hertli for the unique 3SAT problem. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j63]Daniel Kane, Osamu Watanabe:
A Short Implicant of a CNF Formula with Many Satisfying Assignments. Algorithmica 76(4): 1203-1223 (2016) - [c77]Shuichi Hirahara, Osamu Watanabe:
Limits of Minimum Circuit Size Problem as Oracle. CCC 2016: 18:1-18:20 - [c76]Tatsuya Imai, Osamu Watanabe:
Relating Sublinear Space Computability Among Graph Connectivity and Related Problems. SOFSEM 2016: 17-28 - 2015
- [j62]Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. J. Discrete Algorithms 34: 108-117 (2015) - [c75]Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe:
Generalized Shortest Path Kernel on Graphs. Discovery Science 2015: 78-85 - [i21]Ryuhei Mori, Osamu Watanabe:
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges. CoRR abs/1506.00718 (2015) - [i20]Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe:
Generalized Shortest Path Kernel on Graphs. CoRR abs/1510.06492 (2015) - [i19]Shuichi Hirahara, Osamu Watanabe:
Limits of Minimum Circuit Size Problem as Oracle. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c74]Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
The Query Complexity of Witness Finding. CSR 2014: 218-231 - [c73]Daniel M. Kane, Osamu Watanabe:
A Short Implicant of a CNF Formula with Many Satisfying Assignments. ISAAC 2014: 273-284 - [c72]Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. MFCS (2) 2014: 45-56 - [i18]Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe, Masaki Yamamoto:
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets. CoRR abs/1406.0373 (2014) - [i17]David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe:
Polynomial size linear programs for non-bipartite matching problems and other problems in P. CoRR abs/1408.0807 (2014) - [i16]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. TR14 (2014) - 2013
- [j61]Osamu Watanabe:
Message Passing Algorithms for MLS-3LIN Problem. Algorithmica 66(4): 848-868 (2013) - [j60]Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe:
Is Valiant-Vazirani's isolation probability improvable? Comput. Complex. 22(2): 345-383 (2013) - [c71]Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe:
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. CCC 2013: 277-286 - [i15]Daniel M. Kane, Osamu Watanabe:
A Short Implicant of CNFs with Relatively Many Satisfying Assignments. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j59]Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe:
Propagation Connectivity of Random Hypergraphs. Electron. J. Comb. 19(1): 17 (2012) - [j58]Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe:
Estimating the Gowers Norm of Modulo Functions over Prime Fields. IEICE Trans. Inf. Syst. 95-D(3): 755-762 (2012) - [c70]Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe:
On the Optimality of Lattices for the Coppersmith Technique. ACISP 2012: 376-389 - [c69]Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe:
Is Valiant-Vazirani's Isolation Probability Improvable? CCC 2012: 10-20 - [c68]Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe:
Interval Graph Representation with Given Interval and Intersection Lengths. ISAAC 2012: 517-526 - [i14]Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
Query Complexity and Error Tolerance of Witness Finding Algorithms. Electron. Colloquium Comput. Complex. TR12 (2012) - [i13]Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. Electron. Colloquium Comput. Complex. TR12 (2012) - [i12]Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe:
On the Optimality of Lattices for the Coppersmith Technique. IACR Cryptol. ePrint Arch. 2012: 108 (2012) - 2011
- [j57]Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto:
Spectral Analysis of Random Sparse Matrices. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 94-A(6): 1247-1256 (2011) - [j56]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) - [c67]Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe:
Evaluations of Hash Distributed A* in Optimal Sequence Alignment. IJCAI 2011: 584-590 - [e4]Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, Osamu Watanabe:
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 [contents] - [i11]Valentine Kabanets, Osamu Watanabe:
Is the Valiant-Vazirani Isolation Lemma Improvable? Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j55]Toshiya Itoh, Osamu Watanabe:
Weighted random popular matchings. Random Struct. Algorithms 37(4): 477-494 (2010) - [j54]Yusuke Soejima, Akihiro Kishimoto, Osamu Watanabe:
Evaluating Root Parallelization in Go. IEEE Trans. Comput. Intell. AI Games 2(4): 278-287 (2010) - [j53]Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
On the complexity of kings. Theor. Comput. Sci. 411(4-5): 783-798 (2010) - [j52]Osamu Watanabe, Masaki Yamamoto:
Average-case analysis for the MAX-2SAT problem. Theor. Comput. Sci. 411(16-18): 1685-1697 (2010) - [c66]Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe:
Propagation Connectivity of Random Hypergraphs. APPROX-RANDOM 2010: 490-503 - [c65]Takeya Shigezumi, Yushi Uno, Osamu Watanabe:
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques. WALCOM 2010: 216-227
2000 – 2009
- 2009
- [j51]Mikael Onsjö, Osamu Watanabe:
Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions. Theory Comput. Syst. 45(4): 926-942 (2009) - [j50]Mikael Onsjö, Osamu Watanabe:
Finding Most Likely Solutions. Theory Comput. Syst. 45(4): 943 (2009) - [j49]Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe:
Scale free interval graphs. Theor. Comput. Sci. 410(45): 4588-4600 (2009) - [c64]Manindra Agrawal, Osamu Watanabe:
One-Way Functions and the Berman-Hartmanis Conjecture. CCC 2009: 194-202 - [c63]Takeya Shigezumi, Yushi Uno, Osamu Watanabe:
A Replacement Model for a Scale-Free Property of Cliques. CTW 2009: 285-289 - [e3]Osamu Watanabe, Thomas Zeugmann:
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 [contents] - [i10]Manindra Agrawal, Osamu Watanabe:
One-Way Functions and the Isomorphism Conjecture. Electron. Colloquium Comput. Complex. TR09 (2009) - [i9]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. TR09 (2009) - 2008
- [j48]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) - [c62]Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe:
Scale Free Interval Graphs. AAIM 2008: 292-303 - 2007
- [j47]Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe:
Randomized Algorithms for 3-SAT. Theory Comput. Syst. 40(3): 249-262 (2007) - [c61]Osamu Watanabe, Mikael Onsjö:
Finding Most Likely Solutions. CiE 2007: 758-767 - [c60]Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
On the Complexity of Kings. FCT 2007: 328-340 - [i8]Toshiya Itoh, Osamu Watanabe:
Weighted Random Popular Matchings. CoRR abs/0710.5338 (2007) - 2006
- [j46]Jin-yi Cai, Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results. Algorithmica 46(1): 43-57 (2006) - [c59]Mikael Onsjö, Osamu Watanabe:
A Simple Message Passing Algorithm for Graph Partitioning Problems. ISAAC 2006: 507-516 - [c58]Osamu Watanabe, Masaki Yamamoto:
Average-Case Analysis for the MAX-2SAT Problem. SAT 2006: 277-282 - 2005
- [j45]Ryoichi Kato, Osamu Watanabe:
Substring search and repeat search using factor oracles. Inf. Process. Lett. 93(6): 269-274 (2005) - [j44]Osamu Watanabe:
Sequential sampling techniques for algorithmic learning theory. Theor. Comput. Sci. 348(1): 3-14 (2005) - [c57]Osamu Watanabe:
Some Heuristic Analysis of Local Search Algorithms for SAT Problems. SAGA 2005: 14-25 - [i7]Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe:
The Complexity of Kings. CoRR abs/cs/0506055 (2005) - 2004
- [j43]Jin-yi Cai, Osamu Watanabe:
Relativized collapsing between BPP and PH under stringent oracle access. Inf. Process. Lett. 90(3): 147-154 (2004) - [j42]Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe:
Games with Uniqueness Properties. Theory Comput. Syst. 37(1): 29-47 (2004) - [j41]Jin-yi Cai, Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput. 33(4): 984-1009 (2004) - [c56]Kohei Hatano, Osamu Watanabe:
Learning r-of-k Functions by Boosting. ALT 2004: 114-126 - [c55]Jin-yi Cai, Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results. ISAAC 2004: 209-220 - 2003
- [c54]Jin-yi Cai, Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON 2003: 202-211 - [c53]Jin-yi Cai, Osamu Watanabe:
Stringent Relativization. FSTTCS 2003: 408-419 - [c52]Osamu Watanabe, Takeshi Sawai, Hayato Takahashi:
Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem. SAGA 2003: 50-60 - 2002
- [j40]Carlos Domingo, Ricard Gavaldà, Osamu Watanabe:
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. Data Min. Knowl. Discov. 6(2): 131-152 (2002) - [j39]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) - [j38]Osamu Watanabe, Arun Sharma:
Preface. Theor. Comput. Sci. 288(2): 195-196 (2002) - [c51]Osamu Watanabe:
Algorithmic Aspects of Boosting. Progress in Discovery Science 2002: 349-359 - [c50]Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe:
A Probabilistic 3-SAT Algorithm Further Improved. STACS 2002: 192-202 - [c49]Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe:
Games with a Uniqueness Property. STACS 2002: 396-407 - 2001
- [c48]José L. Balcázar, Yang Dai, Osamu Watanabe:
A Random Sampling Technique for Training Support Vector Machines. ALT 2001: 119-134 - [c47]Kyoichi Okamoto, Osamu Watanabe:
Deterministic Application of Grover's Quantum Search Algorithm. COCOON 2001: 493-501 - [c46]José L. Balcázar, Yang Dai, Osamu Watanabe:
Provably Fast Training Algorithms for Support Vector Machines. ICDM 2001: 43-50 - [c45]Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe:
On a Generalized Ruin Problem. RANDOM-APPROX 2001: 181-191 - [c44]Ricard Gavaldà, Osamu Watanabe:
Sequential Sampling Algorithms: Unified Analysis and Lower Bounds. SAGA 2001: 173-188 - [c43]Osamu Watanabe:
How Can Computer Science Contribute to Knowledge Discovery? SOFSEM 2001: 136-151 - [c42]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 - 2000
- [j37]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) - [j36]Wolfgang Lindner, Rainer Schuler, Osamu Watanabe:
Resource-Bounded Measure and Learnability. Theory Comput. Syst. 33(2): 151-170 (2000) - [c41]Osamu Watanabe:
Sequential Sampling Techniques for Algorithmic Learning Theory. ALT 2000: 27-40 - [c40]Carlos Domingo, Osamu Watanabe:
MadaBoost: A Modification of AdaBoost. COLT 2000: 180-189 - [c39]Carlos Domingo, Osamu Watanabe:
Scaling Up a Boosting-Based Learner via Adaptive Sampling. PAKDD 2000: 317-328 - [e2]Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito:
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 [contents] - [i6]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. TR00 (2000)
1990 – 1999
- 1999
- [c38]Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe:
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. COCOON 1999: 210-220 - [c37]Carlos Domingo, Ricard Gavaldà, Osamu Watanabe:
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms. Discovery Science 1999: 172-183 - [c36]Osamu Watanabe:
From Computational Learning Theory to Discovery Science. ICALP 1999: 134-148 - [e1]Osamu Watanabe, Takashi Yokomori:
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 [contents] - [i5]Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe:
Polynomial-Time Multi-Selectivity. CoRR cs.CC/9907034 (1999) - [i4]Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe:
Boolean Operations, Joins, and the Extended Low Hierarchy. CoRR cs.CC/9907037 (1999) - 1998
- [j35]Johannes Köbler, Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput. 28(1): 311-324 (1998) - [j34]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) - [c35]Wolfgang Lindner, Rainer Schuler, Osamu Watanabe:
Resource Bounded Measure and Learnability. CCC 1998: 261- - [c34]Carlos Domingo, Ricard Gavaldà, Osamu Watanabe:
Practical Algorithms for On-line Sampling. Discovery Science 1998: 150-161 - [c33]Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki:
A Role of Constraint in Self-Organization. RANDOM 1998: 307-318 - [i3]Satoshi Horie, Osamu Watanabe:
Hard instance generation for SAT. CoRR cs.CC/9809117 (1998) - [i2]Carlos Domingo, Ricard Gavaldà, Osamu Watanabe:
Practical algorithms for on-line sampling. CoRR cs.LG/9809122 (1998) - [i1]Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki:
A role of constraint in self-organization. CoRR cs.NE/9809123 (1998) - 1997
- [j33]Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe:
Partial Occam's Razor and its Applications. Inf. Process. Lett. 64(4): 179-185 (1997) - [j32]Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe:
Polynomial-Time Multi-Selectivity. J. Univers. Comput. Sci. 3(3): 197-229 (1997) - [c32]Carlos Domingo, Tatsuie Tsukiji, Osamu Watanabe:
Partial Occam's Razor and Its Applications. ALT 1997: 85-99 - [c31]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 - [c30]Satoshi Horie, Osamu Watanabe:
Hard Instance Generation for SAT (Extended Abstract). ISAAC 1997: 22-31 - 1996
- [j31]Ronald V. Book, Osamu Watanabe:
On Random Hard Sets for NP. Inf. Comput. 125(1): 70-76 (1996) - [j30]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-Selective Sets. RAIRO Theor. Informatics Appl. 30(2): 135-154 (1996) - [j29]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) - [j28]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA. J. Univers. Comput. Sci. 2(3): 97-112 (1996) - [j27]Hoong Chuin Lau, Osamu Watanabe:
Randomized Approximation of the Constraint Satisfaction Problem. Nord. J. Comput. 3(4): 405-424 (1996) - [c29]Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe:
The Join Can Lower Complexity. COCOON 1996: 260-267 - [c28]Osamu Watanabe, Osamu Yamashita:
An Improvement of the Digital Cash Protocol of Okamoto and Ohta. ISAAC 1996: 436-445 - [c27]Hoong Chuin Lau, Osamu Watanabe:
Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract). SWAT 1996: 76-87 - 1995
- [j26]Luc Longpré, Osamu Watanabe:
On Symmetry of Information and Polynomial Time Invertibility. Inf. Comput. 121(1): 14-22 (1995) - [c26]Rainer Schuler, Osamu Watanabe:
Towards Average-Case Complexity Analysis of NP Optimization Problems. SCT 1995: 148-159 - [c25]Johannes Köbler, Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits. ICALP 1995: 196-207 - 1994
- [j25]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of GapP. Comput. Complex. 4: 242-261 (1994) - [j24]Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe:
Upward Separation for FewP and Related Classes. Inf. Process. Lett. 52(4): 175-180 (1994) - [j23]Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe:
Instance Complexity. J. ACM 41(1): 96-121 (1994) - [j22]Osamu Watanabe:
A Framework for Polynomial-Time Query Learnability. Math. Syst. Theory 27(3): 211-229 (1994) - [j21]Osamu Watanabe, Ricard Gavaldà:
Structural Analysis of Polynomial-Time Query Learnability. Math. Syst. Theory 27(3): 231-256 (1994) - [j20]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
The Query Complexity of Learning DFA. New Gener. Comput. 12(4): 337-358 (1994) - [c24]Osamu Watanabe:
Test Instance Generation for Promise NP Search Problems. SCT 1994: 205-216 - [c23]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA. COLT 1994: 208-217 - [c22]Ronald V. Book, Osamu Watanabe:
On Random Hard Sets for NP. ISAAC 1994: 47-55 - [c21]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-selective Sets. STACS 1994: 427-438 - 1993
- [j19]Osamu Watanabe, Seinosuke Toda:
Structural Analysis of the Complexity of Inverse Functions. Math. Syst. Theory 26(2): 203-214 (1993) - [j18]Ricard Gavaldà, Osamu Watanabe:
On the Computational Complexity of Small Descriptions. SIAM J. Comput. 22(6): 1257-1275 (1993) - [c20]Mitsunori Ogiwara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Closure Properties of #P in the Context of PF°#P. SCT 1993: 139-146 - [p1]Ronald V. Book, Osamu Watanabe:
A View of Structural Complexity Theory. Current Trends in Theoretical Computer Science 1993: 451-468 - 1992
- [j17]Osamu Watanabe:
On Polynomial Time One-Truth-Table Reducibility to a Sparse Set. J. Comput. Syst. Sci. 44(3): 500-516 (1992) - [j16]Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets. SIAM J. Comput. 21(3): 521-539 (1992) - [j15]Osamu Watanabe, Shouwen Tang:
On Polynomial-Time Turing and Many-One Completeness in PSPACE. Theor. Comput. Sci. 97(2): 199-215 (1992) - [j14]Seinosuke Toda, Osamu Watanabe:
Polynomial Time 1-Turing Reductions from #PH to #P. Theor. Comput. Sci. 100(1): 205-221 (1992) - [c19]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 - [c18]Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
How Hard Are Sparse Sets? SCT 1992: 222-238 - [c17]Luc Longpré, Osamu Watanabe:
On Symmetry of Information and Polynomial Time Invertibility. ISAAC 1992: 410-419 - [c16]Kaoru Kurosawa, Osamu Watanabe:
Computational and Statistical Indistinguishabilities. ISAAC 1992: 430-438 - [c15]Osamu Watanabe:
On the Complexity of Small Description and Related Topics. MFCS 1992: 82-94 - 1991
- [j13]Osamu Watanabe:
On Intractability of the Class UP. Math. Syst. Theory 24(1): 1-10 (1991) - [j12]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) - [j11]Osamu Watanabe:
On the p-Isomorphism Conjecture. Theor. Comput. Sci. 83(2): 337-343 (1991) - [c14]Ricard Gavaldà, Osamu Watanabe:
On the Computational Complexity of Small Descriptions. SCT 1991: 89-101 - [c13]Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets. SCT 1991: 220-229 - 1990
- [j10]Eric Allender, Osamu Watanabe:
Kolmogorov Complexity and Degrees of Tally Sets. Inf. Comput. 86(2): 160-178 (1990) - [c12]Mitsunori Ogiwara, Osamu Watanabe:
On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract). SCT 1990: 2 - [c11]Osamu Watanabe:
A Formal Study of Learning via Queries. ICALP 1990: 139-152 - [c10]Ricard Gavaldà, Leen Torenvliet, Osamu Watanabe, José L. Balcázar:
Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract). MFCS 1990: 269-276 - [c9]Osamu Watanabe, Seinosuke Toda:
Structural Analyses on the Complexity of Inverting Functions. SIGAL International Symposium on Algorithms 1990: 31-38 - [c8]Mitsunori Ogiwara, Osamu Watanabe:
On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. STOC 1990: 457-467
1980 – 1989
- 1989
- [j9]Ronald V. Book, Osamu Watanabe:
A view of structural complexity theory. Bull. EATCS 39: 122-138 (1989) - [j8]Shouwen Tang, Osamu Watanabe:
On Tally Relativizations of BP-Complexity Classes. SIAM J. Comput. 18(3): 449-462 (1989) - [c7]Osamu Watanabe, Shouwen Tang:
On Polynomial Time Turing and Many-One Completeness in PSPACE. SCT 1989: 15-23 - 1988
- [j7]Osamu Watanabe:
On Hardness of One-Way Functions. Inf. Process. Lett. 27(3): 151-157 (1988) - [j6]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) - [c6]Shouwen Tang, Osamu Watanabe:
On tally relativizations of BP-complexity classes. SCT 1988: 10-18 - [c5]Eric Allender, Osamu Watanabe:
Kolmogorov complexity and degrees of tally sets. SCT 1988: 102-111 - [c4]Osamu Watanabe:
On ≤1-ttp-Sparseness and Nondeterministic Complexity Classes (Extended Abstract). ICALP 1988: 697-709 - 1987
- [b1]Osamu Watanabe:
On the structure of interactable complexity classes. Tokyo Inst. of Techn., 1987, pp. I-IV, 1-115 - [j5]Osamu Watanabe:
A Comparison of Polynomial Time Completeness Notions. Theor. Comput. Sci. 54: 249-265 (1987) - [c3]Osamu Watanabe:
Polynomial time reducibility to a set of small density. SCT 1987: 138-146 - 1986
- [c2]Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe:
What Is a Hard Instance of a Computational Problem?. SCT 1986: 197-217 - [c1]Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe:
On Exponential Lowness. ICALP 1986: 40-49 - 1985
- [j4]Osamu Watanabe:
On One-One Polynomial Time Equivalence Relations. Theor. Comput. Sci. 38: 157-165 (1985) - 1983
- [j3]Osamu Watanabe:
The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines. Theor. Comput. Sci. 24: 105-117 (1983) - 1981
- [j2]Osamu Watanabe:
A Fast Algorithm for Finding all Shortest Paths. Inf. Process. Lett. 13(1): 1-3 (1981) - 1980
- [j1]Osamu Watanabe:
Another Application of Recursion Introduction. Inf. Process. Lett. 10(3): 116-119 (1980)
Coauthor Index
Lane A. Hemaspaandra
aka: Lane A. Hemachandra
aka: Lane A. Hemachandra
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-20 00:42 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
