×
Compute Distance To:
Author ID: watanabe.osamu Recent zbMATH articles by "Watanabe, Osamu"
Published as: Watanabe, Osamu; Watanabe, O.
all top 5

Co-Authors

34 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

Publications by Year

Citations contained in zbMATH Open

81 Publications have been cited 377 times in 315 Documents Cited by Year
On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. Zbl 0741.68049
Ogiwara, Mitsunori; Watanabe, Osamu
33
1991
Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P. Zbl 0779.68037
Toda, Seinosuke; Watanabe, Osamu
22
1992
A comparison of polynomial time completeness notions. Zbl 0635.68035
Watanabe, Osamu
17
1987
Instance complexity. Zbl 0807.68035
Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu
17
1994
New collapse consequences of NP having small circuits. Zbl 0920.03052
Köbler, Johannes; Watanabe, Osamu
17
1998
A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
16
2002
On one-one polynomial time equivalence relations. Zbl 0582.68016
Watanabe, Osamu
15
1985
Limits of minimum circuit size problem as oracle. Zbl 1380.68240
Hirahara, Shuichi; Watanabe, Osamu
12
2016
On hardness of one-way functions. Zbl 0635.68037
Watanabe, Osamu
12
1988
Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Zbl 0944.68074
Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu
11
1999
Upward separation for FewP and related classes. Zbl 0938.68662
Rao, Rajesh P. N.; Rothe, Jörg; Watanabe, Osamu
9
1994
Relating equivalence and reducibility to sparse sets. Zbl 0761.68039
Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu
8
1992
Internal time, general internal variable, and multi-yield-surface theories of plasticity and creep: A unification of concepts. Zbl 0618.73038
Watanabe, O.; Atluri, S. N.
8
1986
On tally relativizations of BP-complexity classes. Zbl 0678.68046
Tang, Showen; Watanabe, Osamu
7
1989
Distributions in the Ehrenfest process. Zbl 1092.60502
Balaji, Srinivasan; Mahmoud, Hosam M.; Watanabe, Osamu
7
2006
Crystal plasticity: Micro-shear banding in polycrystals using Voronoi tessellation. Zbl 0969.74015
Watanabe, Osamu; Zbib, Hussein M.; Takenouchi, Eiji
7
1998
Adaptive sampling methods for scaling up knowledge discovery algorithms. Zbl 1009.68036
Domingo, Carlos; Gavaldà, Ricard; Watanabe, Osamu
7
2002
A new endochronic approach to computational elastoplasticity: Example of a cyclically loaded cracked plate. Zbl 0587.73044
Watanabe, O.; Atluri, S. N.
6
1985
On symmetry of information and polynomial time invertibility. Zbl 0832.68059
Longpré, Luc; Watanabe, Osamu
6
1995
A formal study of learning via queries. Zbl 0765.68060
Watanabe, Osamu
5
1990
Constitutive modeling of cyclic plasticity and creep, using an internal time concept. Zbl 0618.73039
Watanabe, O.; Atluri, S. N.
5
1986
Substring search and repeat search using factor oracles. Zbl 1173.68466
Kato, Ryoichi; Watanabe, Osamu
5
2005
A framework for polynomial-time query learnability. Zbl 0809.68097
Watanabe, Osamu
5
1994
Structural analysis of polynomial-time query learnability. Zbl 0809.68098
Watanabe, Osamu; Gavaldà, Ricard
5
1994
\(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196
Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu
5
2014
Generalized Kolmogorov complexity in relativized separations. Zbl 0825.68428
Gavaldà, Ricard; Torenvliet, Leen; Watanabe, Osamu; Balcázar, José L.
4
1990
Structural analysis of the complexity inverse functions. Zbl 0771.68070
Watanabe, Osamu; Toda, Seinosuke
4
1993
Kolmogorov complexity and degrees of tally sets. Zbl 0704.03023
Allender, Eric; Watanabe, Osamu
4
1990
On the computational complexity of small descriptions. Zbl 0799.68085
Gavaldà, Ricard; Watanabe, Osamu
4
1993
Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu
4
1998
On sets bounded truth-table reducible to P-selective sets. Zbl 0941.03541
Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
4
1994
Interval graph representation with given interval and intersection lengths. Zbl 1336.05134
Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu
4
2015
Is Valiant-Vazirani’s isolation probability improvable? Zbl 1286.68167
Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu
4
2013
Weighted random popular matchings. Zbl 1213.05211
Itoh, Toshiya; Watanabe, Osamu
3
2010
The time-precision tradeoff problem on on-line probabilistic Turing machines. Zbl 0509.68045
Watanabe, Osamu
3
1983
On intractability of the Class UP. Zbl 0715.68032
Watanabe, Osamu
3
1991
Randomized algorithms for 3-SAT. Zbl 1109.68133
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
3
2007
On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\). Zbl 0859.68030
Ogihara, Mitsunori; Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
3
1996
Algorithms for learning finite automata from queries: A unified view. Zbl 0874.68260
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
3
1997
On the optimality of lattices for the Coppersmith technique. Zbl 1401.94136
Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu
3
2018
Resource-bounded measure and learnability. Zbl 1008.68061
Lindner, W.; Schuler, R.; Watanabe, O.
3
2000
Propagation connectivity of random hypergraphs. Zbl 1244.05158
Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu
3
2012
On polynomial time one-truth-table reducibility to a sparse set. Zbl 0746.68036
Watanabe, Osamu
2
1992
Kolmogorov complexity and computational complexity. Zbl 0755.68017
2
1992
Lowness properties of sets in the exponential-time hierarchy. Zbl 0652.68059
Book, R.; Orponen, P.; Russo, D.; Watanabe, O.
2
1988
A simple message passing algorithm for graph partitioning problems. Zbl 1135.68523
Onsjö, Mikael; Watanabe, Osamu
2
2006
What is a hard instance of a computational problem? Zbl 0617.68048
Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu
2
1986
Average-case analysis for the MAX-2SAT problem. Zbl 1185.68658
Watanabe, Osamu; Yamamoto, Masaki
2
2006
Randomized approximations of the constraint satisfaction problem. Zbl 0870.68107
Lau, Hoong Chuin; Watanabe, Osamu
2
1996
Partial Occam’s razor and its applications. Zbl 0887.68081
Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu
2
1997
A random sampling technique for training support vector machines for primal-form maximal-margin classifiers. Zbl 1050.68117
Balcázar, Jose; Dai, Yang; Watanabe, Osamu
2
2001
Polynomial-time multi-selectivity. Zbl 0960.68078
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu
2
1997
On the optimality of lattices for the Coppersmith technique. Zbl 1308.94058
Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu
2
2012
Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Zbl 1228.68006
2
2011
A short implicant of a CNF formula with many satisfying assignments. Zbl 1355.68122
Kane, Daniel; Watanabe, Osamu
1
2016
Pseudo expectation: a tool for analyzing local search algorithms. Zbl 1160.90498
Watanabe, Osamu
1
2005
A fast algorithm for finding all shortest paths. Zbl 0469.68070
Watanabe, Osamu
1
1981
On nonadaptive reductions to the set of random strings and its dense subsets. Zbl 1440.68142
Hirahara, Shuichi; Watanabe, Osamu
1
2020
On polynomial-time Turing and many-one completeness in PSPACE. Zbl 0773.68033
Watanabe, Osamu; Tang, Shouwen
1
1992
On the complexity of kings. Zbl 1135.68517
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu
1
2007
On the p-isomorphism conjecture. Zbl 0724.68041
Watanabe, Osamu
1
1991
Scale free interval graphs. Zbl 1143.68507
Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu
1
2008
Provably fast training algorithms for support vector machines. Zbl 1140.68055
Balcázar, José L.; Dai, Yang; Tanaka, Junichi; Watanabe, Osamu
1
2008
The query complexity of learning DFA. Zbl 0812.68107
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1994
On closure properties of GapP. Zbl 0812.68074
Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
1
1994
Partial Occam’s Razor and its applications. Zbl 0900.68354
Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu
1
1997
Analysis of a randomized local search algorithm for LDPCC decoding problem. Zbl 1161.68786
Watanabe, Osamu; Sawai, Takeshi; Takahashi, Hayato
1
2003
Average-case analysis for the MAX-2SAT problem. Zbl 1191.68058
Watanabe, Osamu; Yamamoto, Masaki
1
2010
Propagation connectivity of random hypergraphs. Zbl 1305.68135
Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu
1
2010
Scale free interval graphs. Zbl 1187.68350
Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu
1
2009
New collapse consequences of NP having small circuits. Zbl 1412.68067
Köbler, Johannes; Watanabe, Osamu
1
1995
On a generalized ruin problem. Zbl 1018.91013
Amano, Kazuyuki; Tromp, John; Vitányi, Paul M. B.; Watanabe, Osamu
1
2001
On proving circuit lower bounds against the polynomial-time hierarchy. Zbl 1105.68041
Cai, Jin-Yi; Watanabe, Osamu
1
2004
The orientation selectivity problem: an approach from theoretical computer science. Zbl 0979.68563
Watanabe, 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.68160
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1998
Algorithmic aspects of boosting. Zbl 1052.68705
Watanabe, Osamu
1
2002
An optimal parallel algorithm for learning DFA. Zbl 0960.68789
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1996
An improved randomized algorithm for 3-SAT. Zbl 0991.68742
Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu
1
2001
The query complexity of witness finding. Zbl 1379.68169
Kawachi, Akinori; Rossman, Benjamin; Watanabe, Osamu
1
2014
Interval graph representation with given interval and intersection lengths. Zbl 1260.05103
Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu
1
2012
On nonadaptive reductions to the set of random strings and its dense subsets. Zbl 1440.68142
Hirahara, Shuichi; Watanabe, Osamu
1
2020
On the optimality of lattices for the Coppersmith technique. Zbl 1401.94136
Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu
3
2018
Limits of minimum circuit size problem as oracle. Zbl 1380.68240
Hirahara, Shuichi; Watanabe, Osamu
12
2016
A short implicant of a CNF formula with many satisfying assignments. Zbl 1355.68122
Kane, Daniel; Watanabe, Osamu
1
2016
Interval graph representation with given interval and intersection lengths. Zbl 1336.05134
Köbler, Johannes; Kuhnert, Sebastian; Watanabe, Osamu
4
2015
\(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability. Zbl 1426.68196
Asano, Tetsuo; Kirkpatrick, David; Nakagawa, Kotaro; Watanabe, Osamu
5
2014
The query complexity of witness finding. Zbl 1379.68169
Kawachi, Akinori; Rossman, Benjamin; Watanabe, Osamu
1
2014
Is Valiant-Vazirani’s isolation probability improvable? Zbl 1286.68167
Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu
4
2013
Propagation connectivity of random hypergraphs. Zbl 1244.05158
Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu
3
2012
On the optimality of lattices for the Coppersmith technique. Zbl 1308.94058
Aono, Yoshinori; Agrawal, Manindra; Satoh, Takakazu; Watanabe, Osamu
2
2012
Interval graph representation with given interval and intersection lengths. Zbl 1260.05103
Kö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.05211
Itoh, Toshiya; Watanabe, Osamu
3
2010
Average-case analysis for the MAX-2SAT problem. Zbl 1191.68058
Watanabe, Osamu; Yamamoto, Masaki
1
2010
Propagation connectivity of random hypergraphs. Zbl 1305.68135
Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu
1
2010
Scale free interval graphs. Zbl 1187.68350
Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu
1
2009
Scale free interval graphs. Zbl 1143.68507
Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu
1
2008
Provably fast training algorithms for support vector machines. Zbl 1140.68055
Balcázar, José L.; Dai, Yang; Tanaka, Junichi; Watanabe, Osamu
1
2008
Randomized algorithms for 3-SAT. Zbl 1109.68133
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
3
2007
On the complexity of kings. Zbl 1135.68517
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Tantau, Till; Watanabe, Osamu
1
2007
Distributions in the Ehrenfest process. Zbl 1092.60502
Balaji, Srinivasan; Mahmoud, Hosam M.; Watanabe, Osamu
7
2006
A simple message passing algorithm for graph partitioning problems. Zbl 1135.68523
Onsjö, Mikael; Watanabe, Osamu
2
2006
Average-case analysis for the MAX-2SAT problem. Zbl 1185.68658
Watanabe, Osamu; Yamamoto, Masaki
2
2006
Substring search and repeat search using factor oracles. Zbl 1173.68466
Kato, Ryoichi; Watanabe, Osamu
5
2005
Pseudo expectation: a tool for analyzing local search algorithms. Zbl 1160.90498
Watanabe, Osamu
1
2005
On proving circuit lower bounds against the polynomial-time hierarchy. Zbl 1105.68041
Cai, Jin-Yi; Watanabe, Osamu
1
2004
Analysis of a randomized local search algorithm for LDPCC decoding problem. Zbl 1161.68786
Watanabe, Osamu; Sawai, Takeshi; Takahashi, Hayato
1
2003
A probabilistic 3-SAT algorithm further improved. Zbl 1054.68138
Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
16
2002
Adaptive sampling methods for scaling up knowledge discovery algorithms. Zbl 1009.68036
Domingo, Carlos; Gavaldà, Ricard; Watanabe, Osamu
7
2002
Algorithmic aspects of boosting. Zbl 1052.68705
Watanabe, Osamu
1
2002
A random sampling technique for training support vector machines for primal-form maximal-margin classifiers. Zbl 1050.68117
Balcázar, Jose; Dai, Yang; Watanabe, Osamu
2
2001
On a generalized ruin problem. Zbl 1018.91013
Amano, Kazuyuki; Tromp, John; Vitányi, Paul M. B.; Watanabe, Osamu
1
2001
An improved randomized algorithm for 3-SAT. Zbl 0991.68742
Schuler, Rainer; Schöning, Uwe; Watanabe, Osamu
1
2001
Resource-bounded measure and learnability. Zbl 1008.68061
Lindner, W.; Schuler, R.; Watanabe, O.
3
2000
Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Zbl 0944.68074
Miltersen, 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.03052
Köbler, Johannes; Watanabe, Osamu
17
1998
Crystal plasticity: Micro-shear banding in polycrystals using Voronoi tessellation. Zbl 0969.74015
Watanabe, Osamu; Zbib, Hussein M.; Takenouchi, Eiji
7
1998
Boolean operations, joins, and the extended low hierarchy. Zbl 0913.68077
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Jörg; Watanabe, Osamu
4
1998
The orientation selectivity problem: an approach from theoretical computer science. Zbl 0979.68563
Watanabe, Osamu; Yamazaki, Tadashi
1
1998
An optimal parallel algorithm for learning DFA. Zbl 0956.68160
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1998
Algorithms for learning finite automata from queries: A unified view. Zbl 0874.68260
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
3
1997
Partial Occam’s razor and its applications. Zbl 0887.68081
Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu
2
1997
Polynomial-time multi-selectivity. Zbl 0960.68078
Hemaspaandra, Lane A.; Jiang, Zhigen; Rothe, Joerg; Watanabe, Osamu
2
1997
Partial Occam’s Razor and its applications. Zbl 0900.68354
Domingo, Carlos; Tsukiji, Tatsuie; Watanabe, Osamu
1
1997
On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\). Zbl 0859.68030
Ogihara, Mitsunori; Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
3
1996
Randomized approximations of the constraint satisfaction problem. Zbl 0870.68107
Lau, Hoong Chuin; Watanabe, Osamu
2
1996
An optimal parallel algorithm for learning DFA. Zbl 0960.68789
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1996
On symmetry of information and polynomial time invertibility. Zbl 0832.68059
Longpré, Luc; Watanabe, Osamu
6
1995
New collapse consequences of NP having small circuits. Zbl 1412.68067
Köbler, Johannes; Watanabe, Osamu
1
1995
Instance complexity. Zbl 0807.68035
Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu
17
1994
Upward separation for FewP and related classes. Zbl 0938.68662
Rao, Rajesh P. N.; Rothe, Jörg; Watanabe, Osamu
9
1994
A framework for polynomial-time query learnability. Zbl 0809.68097
Watanabe, Osamu
5
1994
Structural analysis of polynomial-time query learnability. Zbl 0809.68098
Watanabe, Osamu; Gavaldà, Ricard
5
1994
On sets bounded truth-table reducible to P-selective sets. Zbl 0941.03541
Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
4
1994
The query complexity of learning DFA. Zbl 0812.68107
Balcázar, José L.; Díaz, Josep; Gavaldà, Ricard; Watanabe, Osamu
1
1994
On closure properties of GapP. Zbl 0812.68074
Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu
1
1994
Structural analysis of the complexity inverse functions. Zbl 0771.68070
Watanabe, Osamu; Toda, Seinosuke
4
1993
On the computational complexity of small descriptions. Zbl 0799.68085
Gavaldà, Ricard; Watanabe, Osamu
4
1993
Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P. Zbl 0779.68037
Toda, Seinosuke; Watanabe, Osamu
22
1992
Relating equivalence and reducibility to sparse sets. Zbl 0761.68039
Allender, Eric; Hemachandra, Lane A.; Ogiwara, Mitsunori; Watanabe, Osamu
8
1992
On polynomial time one-truth-table reducibility to a sparse set. Zbl 0746.68036
Watanabe, Osamu
2
1992
Kolmogorov complexity and computational complexity. Zbl 0755.68017
2
1992
On polynomial-time Turing and many-one completeness in PSPACE. Zbl 0773.68033
Watanabe, Osamu; Tang, Shouwen
1
1992
On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. Zbl 0741.68049
Ogiwara, Mitsunori; Watanabe, Osamu
33
1991
On intractability of the Class UP. Zbl 0715.68032
Watanabe, Osamu
3
1991
On the p-isomorphism conjecture. Zbl 0724.68041
Watanabe, Osamu
1
1991
A formal study of learning via queries. Zbl 0765.68060
Watanabe, Osamu
5
1990
Generalized Kolmogorov complexity in relativized separations. Zbl 0825.68428
Gavaldà, Ricard; Torenvliet, Leen; Watanabe, Osamu; Balcázar, José L.
4
1990
Kolmogorov complexity and degrees of tally sets. Zbl 0704.03023
Allender, Eric; Watanabe, Osamu
4
1990
On tally relativizations of BP-complexity classes. Zbl 0678.68046
Tang, Showen; Watanabe, Osamu
7
1989
On hardness of one-way functions. Zbl 0635.68037
Watanabe, Osamu
12
1988
Lowness properties of sets in the exponential-time hierarchy. Zbl 0652.68059
Book, R.; Orponen, P.; Russo, D.; Watanabe, O.
2
1988
A comparison of polynomial time completeness notions. Zbl 0635.68035
Watanabe, Osamu
17
1987
Internal time, general internal variable, and multi-yield-surface theories of plasticity and creep: A unification of concepts. Zbl 0618.73038
Watanabe, O.; Atluri, S. N.
8
1986
Constitutive modeling of cyclic plasticity and creep, using an internal time concept. Zbl 0618.73039
Watanabe, O.; Atluri, S. N.
5
1986
What is a hard instance of a computational problem? Zbl 0617.68048
Ko, Ker-I; Orponen, Pekka; Schöning, Uwe; Watanabe, Osamu
2
1986
On one-one polynomial time equivalence relations. Zbl 0582.68016
Watanabe, Osamu
15
1985
A new endochronic approach to computational elastoplasticity: Example of a cyclically loaded cracked plate. Zbl 0587.73044
Watanabe, O.; Atluri, S. N.
6
1985
The time-precision tradeoff problem on on-line probabilistic Turing machines. Zbl 0509.68045
Watanabe, Osamu
3
1983
A fast algorithm for finding all shortest paths. Zbl 0469.68070
Watanabe, Osamu
1
1981
all top 5

Cited by 438 Authors

26 Hemaspaandra, Lane A.
24 Watanabe, Osamu
12 Allender, Eric W.
10 Köbler, Johannes
8 Arvind, Vikraman
8 Pavan, Aduri
8 Rothe, Jörg-Matthias
7 Hemaspaandra, Edith
7 Hitchcock, John M.
7 Lutz, Jack H.
6 Glaßer, Christian
6 Ogihara, Mitsunori
6 Toda, Seinosuke
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 Book, Ronald Vernon
4 Fortnow, Lance J.
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 Homer, Steven
3 Ilango, Rahul
3 Kawachi, Akinori
3 Lozano, Antoni
3 Takayasu, Atsushi
3 Tamaki, Suguru
3 Torán, Jacobo
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 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
2 Sengupta, Samik
2 Silvestri, Riccardo
...and 338 more Authors
all top 5

Cited in 75 Serials

70 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

Citations by Year