Edit Profile (opens in new tab) Watanabe, Osamu Compute Distance To: Compute Author ID: watanabe.osamu Published as: Watanabe, Osamu; Watanabe, O. Documents Indexed: 138 Publications since 1976 8 Contributions as Editor Co-Authors: 95 Co-Authors with 110 Joint Publications 2,381 Co-Co-Authors all top 5 Co-Authors 35 single-authored 10 Gavaldà, Ricard 8 Balcázar, José Luis 7 Hemaspaandra, Lane A. 7 Schuler, Rainer 6 Cai, Jin-Yi 6 Toda, Seinosuke 5 Book, Ronald Vernon 5 Onsjö, Mikael 5 Schöning, Uwe 4 Aida, Shin 4 Atluri, Satya N. 4 Díaz, Josep 4 Hemaspaandra, Edith 4 Köbler, Johannes 4 Orponen, Pekka 4 Shigezumi, Takeya 4 Thierauf, Thomas 4 Tsukiji, Tatsuie 3 Domingo, Carlos 3 Rothe, Jörg-Matthias 2 Agrawal, Manindra 2 Allender, Eric W. 2 Aono, Yoshinori 2 Coja-Oghlan, Amin 2 Crasmaru, Marcel 2 Dai, Yang 2 Hirahara, Shuichi 2 Hofmeister, Thomas 2 Jiang, Zhigen 2 Kane, Daniel M. 2 Kawachi, Akinori 2 Ko, Ker-I 2 Kuhnert, Sebastian 2 Lau, Hoong Chuin 2 Lindner, Wolfgang 2 Longpré, Luc 2 Miyoshi, Naoto 2 Ogiwara, Mitsunori 2 Qin, Tong 2 Regan, Kenneth W. 2 Rossman, Benjamin 2 Russo, David A. 2 Satoh, Takakazu 2 Spakowski, Holger 2 Tantau, Till 2 Uehara, Ryuhei 2 Uno, Yushi 2 Yamamoto, Masaki 1 Amano, Kazuyuki 1 Asano, Takao 1 Asano, Tetsuo 1 Avis, David M. 1 Balaji, Srinivasan 1 Bremner, David 1 Bro Miltersen, Peter 1 Dell, Holger 1 Hagiya, Masami 1 Hatano, Kohei 1 Im, Seyoung 1 Imai, Tatsuya 1 Ito, Takayasu 1 Itoh, Toshiya 1 Kabanets, Valentine 1 Kato, Ryoichi 1 Kirkpatrick, David G. 1 Koshiba, Takeshi 1 Kurosawa, Kaoru 1 Mahmoud, Hosam M. 1 Mosses, Peter D. 1 Nakagawa, Kotaro 1 Nakano, Shin-ichi 1 Ogihara, Mitsunori 1 Okamoto, Kyoichi 1 Okamoto, Yoshio 1 Rao, Rajesh P. N. 1 Sawai, Takeshi 1 Sharma, Arun K. 1 Takahashi, Hayato 1 Takenouchi, Eiji 1 Tamaki, Suguru 1 Tanaka, Junichi 1 Tang, Shouwen 1 Tang, Showen 1 Tiwary, Hans Raj 1 Torenvliet, Leen 1 Tromp, John T. 1 Van Leeuwen, Jan 1 van Melkebeek, Dieter 1 Vinodchandran, N. Variyam 1 Vitányi, Paul M. B. 1 Yamamoto, Youichi 1 Yamazaki, Tadashi 1 Yokomori, Takashi 1 Zbib, Hussein M. 1 Zeugmann, Thomas all top 5 Serials 13 Theoretical Computer Science 9 Theory of Computing Systems 7 SIAM Journal on Computing 6 Information Processing Letters 5 RIMS Kokyuroku 4 Journal of Mathematics of Kyoto University 4 Mathematical Systems Theory 4 Lecture Notes in Computer Science 3 International Journal of Plasticity 3 Algorithmica 3 Information and Computation 3 Computational Complexity 3 Bulletin of Aichi University of Education. Natural Science 2 Journal of Computer and System Sciences 2 Journal of Universal Computer Science 1 Discrete Applied Mathematics 1 International Journal of Mechanical Sciences 1 Journal of Applied Mechanics 1 Journal of the Association for Computing Machinery 1 Statistics & Probability Letters 1 Sūgaku 1 New Generation Computing 1 Bulletin of the European Association for Theoretical Computer Science (EATCS) 1 Random Structures & Algorithms 1 RAIRO. Informatique Théorique et Applications 1 Applicable Algebra in Engineering, Communication and Computing 1 Nordic Journal of Computing 1 The Electronic Journal of Combinatorics 1 Journal of Graph Algorithms and Applications 1 Data Mining and Knowledge Discovery 1 Journal of Discrete Algorithms 1 EATCS Monographs on Theoretical Computer Science all top 5 Fields 125 Computer science (68-XX) 20 Mathematical logic and foundations (03-XX) 15 Combinatorics (05-XX) 7 General and overarching topics; collections (00-XX) 6 Mechanics of deformable solids (74-XX) 6 Information and communication theory, circuits (94-XX) 5 Operations research, mathematical programming (90-XX) 4 Algebraic geometry (14-XX) 4 Functions of a complex variable (30-XX) 3 Probability theory and stochastic processes (60-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Dynamical systems and ergodic theory (37-XX) 1 Number theory (11-XX) 1 Numerical analysis (65-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 83 Publications have been cited 389 times in 321 Documents Cited by ▼ Year ▼ On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. Zbl 0741.68049Ogiwara, Mitsunori; Watanabe, Osamu 34 1991 Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P. Zbl 0779.68037Toda, Seinosuke; Watanabe, Osamu 22 1992 New collapse consequences of NP having small circuits. Zbl 0920.03052Köbler, Johannes; Watanabe, Osamu 17 1998 Instance complexity. Zbl 0807.68035Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu 17 1994 A comparison of polynomial time completeness notions. Zbl 0635.68035Watanabe, Osamu 17 1987 On one-one polynomial time equivalence relations. Zbl 0582.68016Watanabe, Osamu 17 1985 A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu 16 2002 On hardness of one-way functions. Zbl 0635.68037Watanabe, Osamu 12 1988 Limits of minimum circuit size problem as oracle. Zbl 1380.68240Hirahara, Shuichi; Watanabe, Osamu 12 2016 Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Zbl 0944.68074Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu 11 1999 Upward separation for FewP and related classes. Zbl 0938.68662Rao, Rajesh P. N.; Rothe, Jörg; Watanabe, Osamu 9 1994 Internal time, general internal variable, and multi-yield-surface theories of plasticity and creep: A unification of concepts. Zbl 0618.73038Watanabe, O.; Atluri, S. N. 8 1986 Relating equivalence and reducibility to sparse sets. Zbl 0761.68039Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu 8 1992 Crystal plasticity: Micro-shear banding in polycrystals using Voronoi tessellation. Zbl 0969.74015Watanabe, Osamu; Zbib, Hussein M.; Takenouchi, Eiji 7 1998 Distributions in the Ehrenfest process. Zbl 1092.60502Balaji, Srinivasan; Mahmoud, Hosam M.; Watanabe, Osamu 7 2006 Adaptive sampling methods for scaling up knowledge discovery algorithms. Zbl 1009.68036Domingo, Carlos; Gavaldà, Ricard; Watanabe, Osamu 7 2002 On tally relativizations of BP-complexity classes. Zbl 0678.68046Tang, Showen; Watanabe, Osamu 7 1989 A new endochronic approach to computational elastoplasticity: Example of a cyclically loaded cracked plate. Zbl 0587.73044Watanabe, O.; Atluri, S. N. 6 1985 On symmetry of information and polynomial time invertibility. Zbl 0832.68059Longpré, Luc; Watanabe, Osamu 6 1995 A formal study of learning via queries. Zbl 0765.68060Watanabe, Osamu 6 1990 A framework for polynomial-time query learnability. Zbl 0809.68097Watanabe, Osamu 6 1994 Structural analysis of polynomial-time query learnability. Zbl 0809.68098Watanabe, Osamu; Gavaldà, Ricard 6 1994 Substring search and repeat search using factor oracles. Zbl 1173.68466Kato, Ryoichi; Watanabe, Osamu 5 2005 Constitutive modeling of cyclic plasticity and creep, using an internal time concept. Zbl 0618.73039Watanabe, O.; Atluri, S. N. 5 1986 On the computational complexity of small descriptions. Zbl 0799.68085Gavaldà, Ricard; Watanabe, Osamu 5 1993 Kolmogorov complexity and degrees of tally sets. Zbl 0704.03023Allender, Eric; Watanabe, Osamu 5 1990 \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu 5 2014 Interval graph representation with given interval and intersection lengths. Zbl 1336.05134Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu 4 2015 Generalized Kolmogorov complexity in relativized separations. Zbl 0825.68428Gavaldà, Ricard; Torenvliet, Leen; Watanabe, Osamu; Balcázar, José L. 4 1990 Structural analysis of the complexity inverse functions. Zbl 0771.68070Watanabe, Osamu; Toda, Seinosuke 4 1993 On sets bounded truth-table reducible to P-selective sets. Zbl 0941.03541Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 4 1994 Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu 4 1998 Is Valiant-Vazirani’s isolation probability improvable? Zbl 1286.68167Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu 4 2013 Kolmogorov complexity and computational complexity. Zbl 0755.68017 3 1992 On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\). Zbl 0859.68030Ogihara, Mitsunori; Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 3 1996 Resource-bounded measure and learnability. Zbl 1008.68061Lindner, W.; Schuler, R.; Watanabe, O. 3 2000 Algorithms for learning finite automata from queries: A unified view. Zbl 0874.68260Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 3 1997 Weighted random popular matchings. Zbl 1213.05211Itoh, Toshiya; Watanabe, Osamu 3 2010 Randomized algorithms for 3-SAT. Zbl 1109.68133Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu 3 2007 The time-precision tradeoff problem on on-line probabilistic Turing machines. Zbl 0509.68045Watanabe, Osamu 3 1983 On intractability of the Class UP. Zbl 0715.68032Watanabe, Osamu 3 1991 Propagation connectivity of random hypergraphs. Zbl 1244.05158Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu 3 2012 On the optimality of lattices for the Coppersmith technique. Zbl 1401.94136Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu 3 2018 What is a hard instance of a computational problem? Zbl 0617.68048Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu 2 1986 On polynomial time one-truth-table reducibility to a sparse set. Zbl 0746.68036Watanabe, Osamu 2 1992 Polynomial-time multi-selectivity. Zbl 0960.68078Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu 2 1997 Randomized approximations of the constraint satisfaction problem. Zbl 0870.68107Lau, Hoong Chuin; Watanabe, Osamu 2 1996 Partial Occam’s razor and its applications. Zbl 0887.68081Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu 2 1997 A random sampling technique for training support vector machines for primal-form maximal-margin classifiers. Zbl 1050.68117Balcázar, Jose; Dai, Yang; Watanabe, Osamu 2 2001 A simple message passing algorithm for graph partitioning problems. Zbl 1135.68523Onsjö, Mikael; Watanabe, Osamu 2 2006 Average-case analysis for the MAX-2SAT problem. Zbl 1185.68658Watanabe, Osamu; Yamamoto, Masaki 2 2006 Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Zbl 1228.68006 2 2011 Lowness properties of sets in the exponential-time hierarchy. Zbl 0652.68059Book, R.; Orponen, P.; Russo, D.; Watanabe, O. 2 1988 On \(\leq ^ p_{1-tt}\)-sparseness and nondeterministic complexity classes. Zbl 0672.68021Watanabe, Osamu 2 1988 On the optimality of lattices for the Coppersmith technique. Zbl 1308.94058Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu 2 2012 On nonadaptive reductions to the set of random strings and its dense subsets. Zbl 1440.68142Hirahara, Shuichi; Watanabe, Osamu 1 2020 Analysis of a randomized local search algorithm for LDPCC decoding problem. Zbl 1161.68786Watanabe, Osamu; Sawai, Takeshi; Takahashi, Hayato 1 2003 Scale free interval graphs. Zbl 1187.68350Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu 1 2009 On proving circuit lower bounds against the polynomial-time hierarchy. Zbl 1105.68041Cai, Jin-Yi; Watanabe, Osamu 1 2004 The query complexity of witness finding. Zbl 1379.68169Kawachi, Akinori; Rossman, Benjamin; Watanabe, Osamu 1 2014 On polynomial-time Turing and many-one completeness in PSPACE. Zbl 0773.68033Watanabe, Osamu; Tang, Shouwen 1 1992 The orientation selectivity problem: an approach from theoretical computer science. Zbl 0979.68563Watanabe, Osamu; Yamazaki, Tadashi 1 1998 Algorithmic learning theory. 10th international conference, ALT ’99, Tokyo, Japan, December 6–8, 1999. Proceedings. Zbl 0929.00070 1 1999 An optimal parallel algorithm for learning DFA. Zbl 0956.68160Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1998 A fast algorithm for finding all shortest paths. Zbl 0469.68070Watanabe, Osamu 1 1981 An optimal parallel algorithm for learning DFA. Zbl 0960.68789Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1996 Partial Occam’s Razor and its applications. Zbl 0900.68354Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu 1 1997 The query complexity of learning DFA. Zbl 0812.68107Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1994 On closure properties of GapP. Zbl 0812.68074Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 1 1994 An improved randomized algorithm for 3-SAT. Zbl 0991.68742Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu 1 2001 Average-case analysis for the MAX-2SAT problem. Zbl 1191.68058Watanabe, Osamu; Yamamoto, Masaki 1 2010 Algorithmic aspects of boosting. Zbl 1052.68705Watanabe, Osamu 1 2002 On the complexity of kings. Zbl 1135.68517Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu 1 2007 Provably fast training algorithms for support vector machines. Zbl 1140.68055Balcázar, José L.; Dai, Yang; Tanaka, Junichi; Watanabe, Osamu 1 2008 Scale free interval graphs. Zbl 1143.68507Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu 1 2008 Pseudo expectation: a tool for analyzing local search algorithms. Zbl 1160.90498Watanabe, Osamu 1 2005 On a generalized ruin problem. Zbl 1018.91013Amano, Kazuyuki; Tromp, John; Vitányi, Paul M. B.; Watanabe, Osamu 1 2001 On the p-isomorphism conjecture. Zbl 0724.68041Watanabe, Osamu 1 1991 Interval graph representation with given interval and intersection lengths. Zbl 1260.05103Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu 1 2012 A short implicant of a CNF formula with many satisfying assignments. Zbl 1355.68122Kane, Daniel; Watanabe, Osamu 1 2016 New collapse consequences of NP having small circuits. Zbl 1412.68067Köbler, Johannes; Watanabe, Osamu 1 1995 Propagation connectivity of random hypergraphs. Zbl 1305.68135Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu 1 2010 On the complexity of small description and related topics. Zbl 07573126Watanabe, Osamu 1 1992 On nonadaptive reductions to the set of random strings and its dense subsets. Zbl 1440.68142Hirahara, Shuichi; Watanabe, Osamu 1 2020 On the optimality of lattices for the Coppersmith technique. Zbl 1401.94136Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu 3 2018 Limits of minimum circuit size problem as oracle. Zbl 1380.68240Hirahara, Shuichi; Watanabe, Osamu 12 2016 A short implicant of a CNF formula with many satisfying assignments. Zbl 1355.68122Kane, Daniel; Watanabe, Osamu 1 2016 Interval graph representation with given interval and intersection lengths. Zbl 1336.05134Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu 4 2015 \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu 5 2014 The query complexity of witness finding. Zbl 1379.68169Kawachi, Akinori; Rossman, Benjamin; Watanabe, Osamu 1 2014 Is Valiant-Vazirani’s isolation probability improvable? Zbl 1286.68167Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu 4 2013 Propagation connectivity of random hypergraphs. Zbl 1244.05158Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu 3 2012 On the optimality of lattices for the Coppersmith technique. Zbl 1308.94058Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu 2 2012 Interval graph representation with given interval and intersection lengths. Zbl 1260.05103Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu 1 2012 Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Zbl 1228.68006 2 2011 Weighted random popular matchings. Zbl 1213.05211Itoh, Toshiya; Watanabe, Osamu 3 2010 Average-case analysis for the MAX-2SAT problem. Zbl 1191.68058Watanabe, Osamu; Yamamoto, Masaki 1 2010 Propagation connectivity of random hypergraphs. Zbl 1305.68135Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu 1 2010 Scale free interval graphs. Zbl 1187.68350Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu 1 2009 Provably fast training algorithms for support vector machines. Zbl 1140.68055Balcázar, José L.; Dai, Yang; Tanaka, Junichi; Watanabe, Osamu 1 2008 Scale free interval graphs. Zbl 1143.68507Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu 1 2008 Randomized algorithms for 3-SAT. Zbl 1109.68133Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu 3 2007 On the complexity of kings. Zbl 1135.68517Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu 1 2007 Distributions in the Ehrenfest process. Zbl 1092.60502Balaji, Srinivasan; Mahmoud, Hosam M.; Watanabe, Osamu 7 2006 A simple message passing algorithm for graph partitioning problems. Zbl 1135.68523Onsjö, Mikael; Watanabe, Osamu 2 2006 Average-case analysis for the MAX-2SAT problem. Zbl 1185.68658Watanabe, Osamu; Yamamoto, Masaki 2 2006 Substring search and repeat search using factor oracles. Zbl 1173.68466Kato, Ryoichi; Watanabe, Osamu 5 2005 Pseudo expectation: a tool for analyzing local search algorithms. Zbl 1160.90498Watanabe, Osamu 1 2005 On proving circuit lower bounds against the polynomial-time hierarchy. Zbl 1105.68041Cai, Jin-Yi; Watanabe, Osamu 1 2004 Analysis of a randomized local search algorithm for LDPCC decoding problem. Zbl 1161.68786Watanabe, Osamu; Sawai, Takeshi; Takahashi, Hayato 1 2003 A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu 16 2002 Adaptive sampling methods for scaling up knowledge discovery algorithms. Zbl 1009.68036Domingo, Carlos; Gavaldà, Ricard; Watanabe, Osamu 7 2002 Algorithmic aspects of boosting. Zbl 1052.68705Watanabe, Osamu 1 2002 A random sampling technique for training support vector machines for primal-form maximal-margin classifiers. Zbl 1050.68117Balcázar, Jose; Dai, Yang; Watanabe, Osamu 2 2001 An improved randomized algorithm for 3-SAT. Zbl 0991.68742Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu 1 2001 On a generalized ruin problem. Zbl 1018.91013Amano, Kazuyuki; Tromp, John; Vitányi, Paul M. B.; Watanabe, Osamu 1 2001 Resource-bounded measure and learnability. Zbl 1008.68061Lindner, W.; Schuler, R.; Watanabe, O. 3 2000 Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Zbl 0944.68074Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu 11 1999 Algorithmic learning theory. 10th international conference, ALT ’99, Tokyo, Japan, December 6–8, 1999. Proceedings. Zbl 0929.00070 1 1999 New collapse consequences of NP having small circuits. Zbl 0920.03052Köbler, Johannes; Watanabe, Osamu 17 1998 Crystal plasticity: Micro-shear banding in polycrystals using Voronoi tessellation. Zbl 0969.74015Watanabe, Osamu; Zbib, Hussein M.; Takenouchi, Eiji 7 1998 Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu 4 1998 The orientation selectivity problem: an approach from theoretical computer science. Zbl 0979.68563Watanabe, Osamu; Yamazaki, Tadashi 1 1998 An optimal parallel algorithm for learning DFA. Zbl 0956.68160Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1998 Algorithms for learning finite automata from queries: A unified view. Zbl 0874.68260Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 3 1997 Polynomial-time multi-selectivity. Zbl 0960.68078Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu 2 1997 Partial Occam’s razor and its applications. Zbl 0887.68081Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu 2 1997 Partial Occam’s Razor and its applications. Zbl 0900.68354Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu 1 1997 On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\). Zbl 0859.68030Ogihara, Mitsunori; Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 3 1996 Randomized approximations of the constraint satisfaction problem. Zbl 0870.68107Lau, Hoong Chuin; Watanabe, Osamu 2 1996 An optimal parallel algorithm for learning DFA. Zbl 0960.68789Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1996 On symmetry of information and polynomial time invertibility. Zbl 0832.68059Longpré, Luc; Watanabe, Osamu 6 1995 New collapse consequences of NP having small circuits. Zbl 1412.68067Köbler, Johannes; Watanabe, Osamu 1 1995 Instance complexity. Zbl 0807.68035Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu 17 1994 Upward separation for FewP and related classes. Zbl 0938.68662Rao, Rajesh P. N.; Rothe, Jörg; Watanabe, Osamu 9 1994 A framework for polynomial-time query learnability. Zbl 0809.68097Watanabe, Osamu 6 1994 Structural analysis of polynomial-time query learnability. Zbl 0809.68098Watanabe, Osamu; Gavaldà, Ricard 6 1994 On sets bounded truth-table reducible to P-selective sets. Zbl 0941.03541Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 4 1994 The query complexity of learning DFA. Zbl 0812.68107Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu 1 1994 On closure properties of GapP. Zbl 0812.68074Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu 1 1994 On the computational complexity of small descriptions. Zbl 0799.68085Gavaldà, Ricard; Watanabe, Osamu 5 1993 Structural analysis of the complexity inverse functions. Zbl 0771.68070Watanabe, Osamu; Toda, Seinosuke 4 1993 Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P. Zbl 0779.68037Toda, Seinosuke; Watanabe, Osamu 22 1992 Relating equivalence and reducibility to sparse sets. Zbl 0761.68039Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu 8 1992 Kolmogorov complexity and computational complexity. Zbl 0755.68017 3 1992 On polynomial time one-truth-table reducibility to a sparse set. Zbl 0746.68036Watanabe, Osamu 2 1992 On polynomial-time Turing and many-one completeness in PSPACE. Zbl 0773.68033Watanabe, Osamu; Tang, Shouwen 1 1992 On the complexity of small description and related topics. Zbl 07573126Watanabe, Osamu 1 1992 On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. Zbl 0741.68049Ogiwara, Mitsunori; Watanabe, Osamu 34 1991 On intractability of the Class UP. Zbl 0715.68032Watanabe, Osamu 3 1991 On the p-isomorphism conjecture. Zbl 0724.68041Watanabe, Osamu 1 1991 A formal study of learning via queries. Zbl 0765.68060Watanabe, Osamu 6 1990 Kolmogorov complexity and degrees of tally sets. Zbl 0704.03023Allender, Eric; Watanabe, Osamu 5 1990 Generalized Kolmogorov complexity in relativized separations. Zbl 0825.68428Gavaldà, Ricard; Torenvliet, Leen; Watanabe, Osamu; Balcázar, José L. 4 1990 On tally relativizations of BP-complexity classes. Zbl 0678.68046Tang, Showen; Watanabe, Osamu 7 1989 On hardness of one-way functions. Zbl 0635.68037Watanabe, Osamu 12 1988 Lowness properties of sets in the exponential-time hierarchy. Zbl 0652.68059Book, R.; Orponen, P.; Russo, D.; Watanabe, O. 2 1988 On \(\leq ^ p_{1-tt}\)-sparseness and nondeterministic complexity classes. Zbl 0672.68021Watanabe, Osamu 2 1988 A comparison of polynomial time completeness notions. Zbl 0635.68035Watanabe, Osamu 17 1987 Internal time, general internal variable, and multi-yield-surface theories of plasticity and creep: A unification of concepts. Zbl 0618.73038Watanabe, O.; Atluri, S. N. 8 1986 Constitutive modeling of cyclic plasticity and creep, using an internal time concept. Zbl 0618.73039Watanabe, O.; Atluri, S. N. 5 1986 What is a hard instance of a computational problem? Zbl 0617.68048Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu 2 1986 On one-one polynomial time equivalence relations. Zbl 0582.68016Watanabe, Osamu 17 1985 A new endochronic approach to computational elastoplasticity: Example of a cyclically loaded cracked plate. Zbl 0587.73044Watanabe, O.; Atluri, S. N. 6 1985 The time-precision tradeoff problem on on-line probabilistic Turing machines. Zbl 0509.68045Watanabe, Osamu 3 1983 A fast algorithm for finding all shortest paths. Zbl 0469.68070Watanabe, Osamu 1 1981 all cited Publications top 5 cited Publications all top 5 Cited by 442 Authors 26 Hemaspaandra, Lane A. 25 Watanabe, Osamu 12 Allender, Eric W. 10 Köbler, Johannes 8 Arvind, Vikraman 8 Lutz, Jack H. 8 Pavan, Aduri 8 Rothe, Jörg-Matthias 7 Hemaspaandra, Edith 7 Hitchcock, John M. 6 Glaßer, Christian 6 Ogihara, Mitsunori 6 Toda, Seinosuke 5 Book, Ronald Vernon 5 Buhrman, Harry 5 Cai, Jin-Yi 5 Chakraborty, Sankardeep 5 Fu, Bin 5 Mahmoud, Hosam M. 5 Raman, Venkatesh 5 Selman, Alan Louis 5 Tang, Shouwen 5 Torenvliet, Leen 5 van Melkebeek, Dieter 5 Vinodchandran, N. Variyam 5 Vollmer, Heribert 5 Williams, Richard Ryan 4 Agrawal, Manindra 4 Balcázar, José Luis 4 Fortnow, Lance J. 4 Homer, Steven 4 Kabanets, Valentine 4 Ko, Ker-I 4 Mundhenk, Martin 4 Satti, Srinivasa Rao 3 Ambos-Spies, Klaus 3 Dell, Holger 3 Du, Ding-Zhu 3 Gavaldà, Ricard 3 Grochow, Joshua A. 3 Guijarro, David 3 Hempel, Harald 3 Hirahara, Shuichi 3 Homan, Christopher M. 3 Ilango, Rahul 3 Kawachi, Akinori 3 Lozano, Antoni 3 Takayasu, Atsushi 3 Tamaki, Suguru 3 Torán, Jacobo 3 Wagner, Klaus W. 3 Zhang, Liyu 3 Zhang, Panpan 3 Zimand, Marius 2 Arora, Jasbir S. 2 Bakibayev, Timur 2 Banerjee, Niranka 2 Beigel, Richard 2 Beyersdorff, Olaf 2 Borchert, Bernd 2 Brueggemann, Tobias 2 Cardinal, Jean 2 Castro, Jorge E. 2 Chakaravarthy, Venkatesan T. 2 Chen, Chen 2 Creignou, Nadia 2 Durand, Arnaud 2 Faliszewski, Piotr 2 Fazzinga, Bettina 2 Flesca, Sergio 2 Goldsmith, Judy 2 Harkins, Ryan C. 2 Hermann, Miki 2 Hermo, Montserrat 2 Hoene, Albrecht 2 Impagliazzo, Russell 2 Jonsson, Peter A. 2 Kern, Walter 2 Kinne, Jeff 2 Korándi, Dániel 2 Kunihiro, Noboru 2 Kurtz, Stuart A. 2 Li, Angsheng 2 Liu, Tian 2 Makino, Kazuhisa 2 Mayordomo, Elvira 2 Milovanov, Alexey 2 Moore, Cristopher 2 Morgan, Andrew 2 Mukherjee, Anish 2 Müller, Sebastian 2 Murray, Cody D. 2 Nummenpalo, Jerri 2 Ogiwara, Mitsunori 2 Ojeda-Aciego, Manuel 2 Peled, Yuval 2 Raghavan, Vijay V. 2 Roy, Sambuddha 2 Royer, James S. 2 Schöning, Uwe ...and 342 more Authors all top 5 Cited in 75 Serials 71 Theoretical Computer Science 27 Journal of Computer and System Sciences 17 Theory of Computing Systems 15 Information Processing Letters 15 Mathematical Systems Theory 14 Information and Computation 8 Computational Complexity 7 Algorithmica 6 Artificial Intelligence 5 International Journal of Plasticity 5 SIAM Journal on Computing 5 Computational Mechanics 4 International Journal of Foundations of Computer Science 4 RAIRO. Informatique Théorique et Applications 3 Statistics & Probability Letters 2 Acta Mechanica 2 Computer Methods in Applied Mechanics and Engineering 2 Discrete Applied Mathematics 2 Journal of Computer Science and Technology 2 SIAM Journal on Discrete Mathematics 2 Mathematical Logic Quarterly (MLQ) 2 Annals of Mathematics and Artificial Intelligence 2 Journal of Graph Algorithms and Applications 2 European Journal of Mechanics. A. Solids 2 Probability in the Engineering and Informational Sciences 2 Mathematics in Computer Science 1 International Journal of Engineering Science 1 Journal of Applied Mathematics and Mechanics 1 Physica A 1 Reports on Mathematical Physics 1 Annals of the Institute of Statistical Mathematics 1 Applied Mathematics and Computation 1 Fuzzy Sets and Systems 1 Information Sciences 1 Journal of Applied Probability 1 Journal of Soviet Mathematics 1 Proceedings of the American Mathematical Society 1 Transactions of the American Mathematical Society 1 Cybernetics 1 Applied Mathematics and Mechanics. (English Edition) 1 Annals of Pure and Applied Logic 1 Acta Mathematicae Applicatae Sinica. English Series 1 Graphs and Combinatorics 1 Probability Theory and Related Fields 1 New Generation Computing 1 Computers & Operations Research 1 Neural Networks 1 Annals of Operations Research 1 Random Structures & Algorithms 1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence 1 Communications in Statistics. Theory and Methods 1 European Journal of Operational Research 1 Pattern Recognition 1 Applicable Algebra in Engineering, Communication and Computing 1 New Zealand Journal of Mathematics 1 Journal of Logic, Language and Information 1 Journal of Heuristics 1 Science in China. Series E 1 Journal of Combinatorial Optimization 1 Chicago Journal of Theoretical Computer Science 1 Journal of the ACM 1 LMS Journal of Computation and Mathematics 1 Methodology and Computing in Applied Probability 1 Journal of Machine Learning Research (JMLR) 1 Natural Computing 1 ACM Transactions on Computational Logic 1 North American Actuarial Journal 1 Journal of Discrete Algorithms 1 International Journal of Fracture 1 Statistical Analysis and Data Mining 1 Vestnik Samarskogo Gosudarstvennogo Tekhnicheskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 1 ACM Transactions on Algorithms 1 Computer Science Review 1 ACM Transactions on Computation Theory 1 AIMS Mathematics all top 5 Cited in 22 Fields 262 Computer science (68-XX) 49 Mathematical logic and foundations (03-XX) 23 Mechanics of deformable solids (74-XX) 21 Combinatorics (05-XX) 18 Information and communication theory, circuits (94-XX) 11 Probability theory and stochastic processes (60-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Statistics (62-XX) 6 Operations research, mathematical programming (90-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 2 General algebraic systems (08-XX) 2 Number theory (11-XX) 2 Convex and discrete geometry (52-XX) 1 History and biography (01-XX) 1 Group theory and generalizations (20-XX) 1 Partial differential equations (35-XX) 1 Integral equations (45-XX) 1 Differential geometry (53-XX) 1 Algebraic topology (55-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Quantum theory (81-XX) 1 Biology and other natural sciences (92-XX) Citations by Year