 | 2009 |
|---|
| 137 |       | Osamu Watanabe,
Thomas Zeugmann:
Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA 2009, Sapporo, Japan, October 26-28, 2009. Proceedings
Springer 2009 |
| 136 | | Takeya Shigezumi,
Yushi Uno,
Osamu Watanabe:
A Replacement Model for a Scale-Free Property of Cliques.
CTW 2009: 285-289 |
| 2008 |
|---|
| 135 | | Naoto Miyoshi,
Takeya Shigezumi,
Ryuhei Uehara,
Osamu Watanabe:
Scale Free Interval Graphs.
AAIM 2008: 292-303 |
| 134 | | Hitoshi Kiya,
Masahiro Iwahashi,
Osamu Watanabe:
A new structure of lifting wavelet for reducing rounding error.
ISCAS 2008: 2881-2884 |
| 133 | | Osamu Watanabe,
Rui Ito,
Toshiya Mitomo,
Shigehito Saigusa,
Tadashi Arai,
Takehiko Toyoda:
A Triple-Band WCDMA Direct Conversion Receiver IC with Reduced Number of Off-Chip Components and Digital Baseband Control Signals.
IEICE Transactions 91-C(6): 837-843 (2008) |
| 132 | | 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) |
| 2007 |
|---|
| 131 | | Osamu Watanabe,
Mikael Onsjö:
Finding Most Likely Solutions.
CiE 2007: 758-767 |
| 130 | | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Till Tantau,
Osamu Watanabe:
On the Complexity of Kings.
FCT 2007: 328-340 |
| 129 | | Toshiya Itoh,
Osamu Watanabe:
Weighted Random Popular Matchings
CoRR abs/0710.5338: (2007) |
| 128 | | Toshiya Mitomo,
Osamu Watanabe,
Ryuichi Fujimoto,
Shunji Kawaguchi:
A Quadrature Demodulator for WCDMA Receiver Using Common-Base Input Stage with Robustness to Transmitter Leakage.
IEICE Transactions 90-C(6): 1241-1246 (2007) |
| 127 | | Osamu Watanabe,
Rui Ito,
Shigehito Saigusa,
Tadashi Arai,
Tetsuro Itakura:
A Fast fc Automatic Tuning Circuit with Wide Tuning Range for WCDMA Direct Conversion Receiver Systems.
IEICE Transactions 90-C(6): 1247-1252 (2007) |
| 126 | | Thomas Hofmeister,
Uwe Schöning,
Rainer Schuler,
Osamu Watanabe:
Randomized Algorithms for 3-SAT.
Theory Comput. Syst. 40(3): 249-262 (2007) |
| 2006 |
|---|
| 125 | | Masaaki Fujiyoshi,
Wataru Saitou,
Osamu Watanabe,
Hitoshi Kiya:
Hierarchical Encryption of Multimedia Contents for Access Control.
ICIP 2006: 1977-1980 |
| 124 | | Osamu Watanabe:
A Neural Model for Stereo Transparency with the Population of the Disparity Energy Models.
ICONIP (1) 2006: 165-174 |
| 123 | | Akio Kawana,
Shinya Tsuzuki,
Osamu Watanabe:
Analysis of Dynamics of Cultured Neuronal Networks Using I&F Model.
ICONIP (1) 2006: 547-553 |
| 122 | | Mikael Onsjö,
Osamu Watanabe:
A Simple Message Passing Algorithm for Graph Partitioning Problems.
ISAAC 2006: 507-516 |
| 121 | | Osamu Watanabe,
Masaki Yamamoto:
Average-Case Analysis for the MAX-2SAT Problem.
SAT 2006: 277-282 |
| 120 | | Jin-yi Cai,
Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results.
Algorithmica 46(1): 43-57 (2006) |
| 2005 |
|---|
| 119 | | Shoko Imaizumi,
Osamu Watanabe,
Masaaki Fujiyoshi,
Hitoshi Kiya:
Generalized hierarchical encryption of JPEG 2000 codestreams for access control.
ICIP (2) 2005: 1094-1097 |
| 118 | | Osamu Watanabe,
Akiko Nakazaki,
Hitoshi Kiya:
A scalable encryption method allowing backward compatibility with JPEG2000 images.
ISCAS (6) 2005: 6324-6327 |
| 117 | | Osamu Watanabe:
Some Heuristic Analysis of Local Search Algorithms for SAT Problems.
SAGA 2005: 14-25 |
| 116 | | Edith Hemaspaandra,
Lane A. Hemaspaandra,
Osamu Watanabe:
The Complexity of Kings
CoRR abs/cs/0506055: (2005) |
| 115 | | Masaaki Fujiyoshi,
Osamu Watanabe,
Hitoshi Kiya:
A Method of Guaranteeing Image-Quality for Quantization-Based Watermarking Using a Nonorthogonal Transformation.
IEICE Transactions 88-A(6): 1434-1442 (2005) |
| 114 | | Toshiya Mitomo,
Osamu Watanabe,
Shoji Otaka,
Ryuichi Fujimoto,
Shunji Kawaguchi:
A Low LO Leakage and Low Power LO Buffer for Direct-Conversion Quadrature Demodulator.
IEICE Transactions 88-C(6): 1212-1217 (2005) |
| 113 | | Ryoichi Kato,
Osamu Watanabe:
Substring search and repeat search using factor oracles.
Inf. Process. Lett. 93(6): 269-274 (2005) |
| 112 | | Osamu Watanabe,
Masayuki Kikuchi:
Nonlinearity of the population activity to transparent motion.
Neural Networks 18(1): 15-22 (2005) |
| 111 | | Osamu Watanabe:
Sequential sampling techniques for algorithmic learning theory.
Theor. Comput. Sci. 348(1): 3-14 (2005) |
| 2004 |
|---|
| 110 | | Kohei Hatano,
Osamu Watanabe:
Learning r-of-k Functions by Boosting.
ALT 2004: 114-126 |
| 109 |  | Osamu Watanabe,
Akiko Nakazaki,
Hitoshi Kiya:
A fast image-scramble method using public-key encryption allowing backward compatibility with jpeg2000.
ICIP 2004: 3435-3438 |
| 108 | | Jin-yi Cai,
Osamu Watanabe:
Random Access to Advice Strings and Collapsing Results.
ISAAC 2004: 209-220 |
| 107 | | Jin-yi Cai,
Osamu Watanabe:
Relativized collapsing between BPP and PH under stringent oracle access.
Inf. Process. Lett. 90(3): 147-154 (2004) |
| 106 | | Jin-yi Cai,
Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.
SIAM J. Comput. 33(4): 984-1009 (2004) |
| 105 | | Shin Aida,
Marcel Crâsmaru,
Kenneth W. Regan,
Osamu Watanabe:
Games with Uniqueness Properties.
Theory Comput. Syst. 37(1): 29-47 (2004) |
| 2003 |
|---|
| 104 | | Jin-yi Cai,
Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.
COCOON 2003: 202-211 |
| 103 | | Jin-yi Cai,
Osamu Watanabe:
Stringent Relativization.
FSTTCS 2003: 408-419 |
| 102 | | Hitoshi Kiya,
Shoko Imaizumi,
Osamu Watanabe:
Partial-scrambling of images encoded using JPEG2000 without generating marker codes.
ICIP (3) 2003: 205-208 |
| 101 | | Osamu Watanabe,
Hitoshi Kiya:
ROI-based scalability for progressive transmission in JPEG2000 coding.
ISCAS (2) 2003: 416-419 |
| 100 | | Osamu Watanabe,
Takeshi Sawai,
Hayato Takahashi:
Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem.
SAGA 2003: 50-60 |
| 99 | | Osamu Watanabe,
Masanori Idesawa:
Computational model for neural representation of multiple disparities.
Neural Networks 16(1): 25-37 (2003) |
| 2002 |
|---|
| 98 | | Osamu Watanabe,
Hitoshi Kiya:
An extension of ROI-based scalability for progressive transmission in JPEG2000 coding.
APCCAS (1) 2002: 535-540 |
| 97 | | Osamu Watanabe:
Algorithmic Aspects of Boosting.
Progress in Discovery Science 2002: 349-359 |
| 96 | | Thomas Hofmeister,
Uwe Schöning,
Rainer Schuler,
Osamu Watanabe:
A Probabilistic 3-SAT Algorithm Further Improved.
STACS 2002: 192-202 |
| 95 | | Shin Aida,
Marcel Crâsmaru,
Kenneth W. Regan,
Osamu Watanabe:
Games with a Uniqueness Property.
STACS 2002: 396-407 |
| 94 | | Carlos Domingo,
Ricard Gavaldà,
Osamu Watanabe:
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Data Min. Knowl. Discov. 6(2): 131-152 (2002) |
| 93 | | Osamu Watanabe,
Arun Sharma:
Preface
Theor. Comput. Sci. 288(2): 195-196 (2002) |
| 92 | | 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) |
| 2001 |
|---|
| 91 | | José L. Balcázar,
Yang Dai,
Osamu Watanabe:
A Random Sampling Technique for Training Support Vector Machines.
ALT 2001: 119-134 |
| 90 | | Kyoichi Okamoto,
Osamu Watanabe:
Deterministic Application of Grover's Quantum Search Algorithm.
COCOON 2001: 493-501 |
| 89 | | José L. Balcázar,
Yang Dai,
Osamu Watanabe:
Provably Fast Training Algorithms for Support Vector Machines.
ICDM 2001: 43-50 |
| 88 | | Kazuyuki Amano,
John Tromp,
Paul M. B. Vitányi,
Osamu Watanabe:
On a Generalized Ruin Problem.
RANDOM-APPROX 2001: 181-191 |
| 87 | | Ricard Gavaldà,
Osamu Watanabe:
Sequential Sampling Algorithms: Unified Analysis and Lower Bounds.
SAGA 2001: 173-188 |
| 86 | | Osamu Watanabe:
How Can Computer Science Contribute to Knowledge Discovery?
SOFSEM 2001: 136-151 |
| 85 | | 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 |
|---|
| 84 | | 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
Springer 2000 |
| 83 | | Osamu Watanabe:
Sequential Sampling Techniques for Algorithmic Learning Theory.
ALT 2000: 27-40 |
| 82 | | Carlos Domingo,
Osamu Watanabe:
MadaBoost: A Modification of AdaBoost.
COLT 2000: 180-189 |
| 81 | | Carlos Domingo,
Osamu Watanabe:
Scaling Up a Boosting-Based Learner via Adaptive Sampling.
PAKDD 2000: 317-328 |
| 80 | | Shin Aida,
Rainer Schuler,
Tatsuie Tsukiji,
Osamu Watanabe:
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems
Electronic Colloquium on Computational Complexity (ECCC) 7(81): (2000) |
| 79 | | 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) |
| 78 | | Wolfgang Lindner,
Rainer Schuler,
Osamu Watanabe:
Resource-Bounded Measure and Learnability.
Theory Comput. Syst. 33(2): 151-170 (2000) |
| 1999 |
|---|
| 77 | | Osamu Watanabe,
Takashi Yokomori:
Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 6-8, 1999, Proceedings
Springer 1999 |
| 76 | | Peter Bro Miltersen,
N. V. Vinodchandran,
Osamu Watanabe:
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.
COCOON 1999: 210-220 |
| 75 | | Carlos Domingo,
Ricard Gavaldà,
Osamu Watanabe:
Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Discovery Science 1999: 172-183 |
| 74 | | Osamu Watanabe:
From Computational Learning Theory to Discovery Science.
ICALP 1999: 134-148 |
| 73 | | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Polynomial-Time Multi-Selectivity
CoRR cs.CC/9907034: (1999) |
| 72 | | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Boolean Operations, Joins, and the Extended Low Hierarchy
CoRR cs.CC/9907037: (1999) |
| 71 | | Osamu Watanabe,
Kunihiko Fukushima:
Stereo algorithm that extracts a depth cue from interocularly unpaired points.
Neural Networks 12(4-5): 569-578 (1999) |
| 1998 |
|---|
| 70 | | Carlos Domingo,
Ricard Gavaldà,
Osamu Watanabe:
Practical Algorithms for On-line Sampling.
Discovery Science 1998: 150-161 |
| 69 | | Wolfgang Lindner,
Rainer Schuler,
Osamu Watanabe:
Resource Bounded Measure and Learnability.
IEEE Conference on Computational Complexity 1998: 261- |
| 68 | | Carlos Domingo,
Osamu Watanabe,
Tadashi Yamazaki:
A Role of Constraint in Self-Organization.
RANDOM 1998: 307-318 |
| 67 | | Satoshi Horie,
Osamu Watanabe:
Hard instance generation for SAT
CoRR cs.CC/9809117: (1998) |
| 66 | | Carlos Domingo,
Ricard Gavaldà,
Osamu Watanabe:
Practical algorithms for on-line sampling
CoRR cs.LG/9809122: (1998) |
| 65 | | Carlos Domingo,
Osamu Watanabe,
Tadashi Yamazaki:
A role of constraint in self-organization
CoRR cs.NE/9809123: (1998) |
| 64 | | Johannes Köbler,
Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput. 28(1): 311-324 (1998) |
| 63 | | 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) |
| 1997 |
|---|
| 62 | | Carlos Domingo,
Tatsuie Tsukiji,
Osamu Watanabe:
Partial Occam's Razor and Its Applications.
ALT 1997: 85-99 |
| 61 | | 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 |
| 60 | | Satoshi Horie,
Osamu Watanabe:
Hard Instance Generation for SAT (Extended Abstract).
ISAAC 1997: 22-31 |
| 59 | | Carlos Domingo,
Tatsuie Tsukiji,
Osamu Watanabe:
Partial Occam's Razor and its Applications.
Inf. Process. Lett. 64(4): 179-185 (1997) |
| 58 | | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
Polynomial-Time Multi-Selectivity.
J. UCS 3(3): 197-229 (1997) |
| 1996 |
|---|
| 57 | | Lane A. Hemaspaandra,
Zhigen Jiang,
Jörg Rothe,
Osamu Watanabe:
The Join Can Lower Complexity.
COCOON 1996: 260-267 |
| 56 | | Osamu Watanabe,
Osamu Yamashita:
An Improvement of the Digital Cash Protocol of Okamoto and Ohta.
ISAAC 1996: 436-445 |
| 55 | | Hoong Chuin Lau,
Osamu Watanabe:
Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract).
SWAT 1996: 76-87 |
| 54 | | Thomas Thierauf,
Seinosuke Toda,
Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-Selective Sets.
ITA 30(2): 135-154 (1996) |
| 53 | | Ronald V. Book,
Osamu Watanabe:
On Random Hard Sets for NP.
Inf. Comput. 125(1): 70-76 (1996) |
| 52 | | 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) |
| 51 | | José L. Balcázar,
Josep Díaz,
Ricard Gavaldà,
Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA.
J. UCS 2(3): 97-112 (1996) |
| 50 | | Hoong Chuin Lau,
Osamu Watanabe:
Randomized Approximation of the Constraint Satisfaction Problem.
Nord. J. Comput. 3(4): 405-424 (1996) |
| 1995 |
|---|
| 49 | | Johannes Köbler,
Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits.
ICALP 1995: 196-207 |
| 48 | | Rainer Schuler,
Osamu Watanabe:
Towards Average-Case Complexity Analysis of NP Optimization Problems.
Structure in Complexity Theory Conference 1995: 148-159 |
| 47 | | Luc Longpré,
Osamu Watanabe:
On Symmetry of Information and Polynomial Time Invertibility
Inf. Comput. 121(1): 14-22 (1995) |
| 1994 |
|---|
| 46 | | José L. Balcázar,
Josep Díaz,
Ricard Gavaldà,
Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA.
COLT 1994: 208-217 |
| 45 | | Ronald V. Book,
Osamu Watanabe:
On Random Hard Sets for NP.
ISAAC 1994: 47-55 |
| 44 | | Thomas Thierauf,
Seinosuke Toda,
Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-selective Sets.
STACS 1994: 427-438 |
| 43 | | Osamu Watanabe:
Test Instance Generation for Promise NP Search Problems.
Structure in Complexity Theory Conference 1994: 205-216 |
| 42 | | Thomas Thierauf,
Seinosuke Toda,
Osamu Watanabe:
On Closure Properties of GapP.
Computational Complexity 4: 242-261 (1994) |
| 41 | | Rajesh P. N. Rao,
Jörg Rothe,
Osamu Watanabe:
Upward Separation for FewP and Related Classes.
Inf. Process. Lett. 52(4): 175-180 (1994) |
| 40 | | Pekka Orponen,
Ker-I Ko,
Uwe Schöning,
Osamu Watanabe:
Instance Complexity.
J. ACM 41(1): 96-121 (1994) |
| 39 | | Osamu Watanabe:
A Framework for Polynomial-Time Query Learnability.
Mathematical Systems Theory 27(3): 211-229 (1994) |
| 38 | | Osamu Watanabe,
Ricard Gavaldà:
Structural Analysis of Polynomial-Time Query Learnability.
Mathematical Systems Theory 27(3): 231-256 (1994) |
| 37 | | José L. Balcázar,
Josep Díaz,
Ricard Gavaldà,
Osamu Watanabe:
The Query Complexity of Learning DFA.
New Generation Comput. 12(4): 337-358 (1994) |
| 1993 |
|---|
| 36 | | Mitsunori Ogiwara,
Thomas Thierauf,
Seinosuke Toda,
Osamu Watanabe:
On Closure Properties of #P in the Context of PF°#P.
Structure in Complexity Theory Conference 1993: 139-146 |
| 35 | | Osamu Watanabe,
Seinosuke Toda:
Structural Analysis of the Complexity of Inverse Functions.
Mathematical Systems Theory 26(2): 203-214 (1993) |
| 34 | | Ricard Gavaldà,
Osamu Watanabe:
On the Computational Complexity of Small Descriptions.
SIAM J. Comput. 22(6): 1257-1275 (1993) |
| 1992 |
|---|
| 33 | | 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 |
| 32 | | Luc Longpré,
Osamu Watanabe:
On Symmetry of Information and Polynomial Time Invertibility.
ISAAC 1992: 410-419 |
| 31 | | Kaoru Kurosawa,
Osamu Watanabe:
Computational and Statistical Indistinguishabilities.
ISAAC 1992: 430-438 |
| 30 | | Osamu Watanabe:
On the Complexity of Small Description and Related Topics.
MFCS 1992: 82-94 |
| 29 | | Lane A. Hemachandra,
Mitsunori Ogiwara,
Osamu Watanabe:
How Hard Are Sparse Sets?
Structure in Complexity Theory Conference 1992: 222-238 |
| 28 | | Osamu Watanabe:
On Polynomial Time One-Truth-Table Reducibility to a Sparse Set.
J. Comput. Syst. Sci. 44(3): 500-516 (1992) |
| 27 | | Eric Allender,
Lane A. Hemachandra,
Mitsunori Ogiwara,
Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput. 21(3): 521-539 (1992) |
| 26 | | Seinosuke Toda,
Osamu Watanabe:
Polynomial Time 1-Turing Reductions from #PH to #P.
Theor. Comput. Sci. 100(1): 205-221 (1992) |
| 25 | | Osamu Watanabe,
Shouwen Tang:
On Polynomial-Time Turing and Many-One Completeness in PSPACE.
Theor. Comput. Sci. 97(2): 199-215 (1992) |
| 1991 |
|---|
| 24 | | Eric Allender,
Lane A. Hemachandra,
Mitsunori Ogiwara,
Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets.
Structure in Complexity Theory Conference 1991: 220-229 |
| 23 | | Ricard Gavaldà,
Osamu Watanabe:
On the Computational Complexity of Small Descriptions.
Structure in Complexity Theory Conference 1991: 89-101 |
| 22 | | Osamu Watanabe:
On Intractability of the Class UP.
Mathematical Systems Theory 24(1): 1-10 (1991) |
| 21 | | 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) |
| 20 | | Osamu Watanabe:
On the p-Isomorphism Conjecture.
Theor. Comput. Sci. 83(2): 337-343 (1991) |
| 1990 |
|---|
| 19 | | Osamu Watanabe:
A Formal Study of Learning via Queries.
ICALP 1990: 139-152 |
| 18 | | Ricard Gavaldà,
Leen Torenvliet,
Osamu Watanabe,
José L. Balcázar:
Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract).
MFCS 1990: 269-276 |
| 17 | | Osamu Watanabe,
Seinosuke Toda:
Structural Analyses on the Complexity of Inverting Functions.
SIGAL International Symposium on Algorithms 1990: 31-38 |
| 16 | | Mitsunori Ogiwara,
Osamu Watanabe:
On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
STOC 1990: 457-467 |
| 15 | | Mitsunori Ogiwara,
Osamu Watanabe:
On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract).
Structure in Complexity Theory Conference 1990: 2 |
| 14 | | Eric Allender,
Osamu Watanabe:
Kolmogorov Complexity and Degrees of Tally Sets
Inf. Comput. 86(2): 160-178 (1990) |
| 1989 |
|---|
| 13 | | Osamu Watanabe,
Shouwen Tang:
On Polynomial Time Turing and Many-One Completeness in PSPACE.
Structure in Complexity Theory Conference 1989: 15-23 |
| 12 | | Ronald V. Book,
Osamu Watanabe:
A view of structural complexity theory.
Bulletin of the EATCS 39: 122-138 (1989) |
| 11 | | Shouwen Tang,
Osamu Watanabe:
On Tally Relativizations of BP-Complexity Classes.
SIAM J. Comput. 18(3): 449-462 (1989) |
| 1988 |
|---|
| 10 | | Osamu Watanabe:
On <=^P_{1-tt}-Sparseness and Nondeterministic Complexity Classes (Extended Abstract).
ICALP 1988: 697-709 |
| 9 | | Osamu Watanabe:
On Hardness of One-Way Functions.
Inf. Process. Lett. 27(3): 151-157 (1988) |
| 8 | | 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) |
| 1987 |
|---|
| 7 | | Osamu Watanabe:
A Comparison of Polynomial Time Completeness Notions.
Theor. Comput. Sci. 54: 249-265 (1987) |
| 1986 |
|---|
| 6 | | Ronald V. Book,
Pekka Orponen,
David A. Russo,
Osamu Watanabe:
On Exponential Lowness.
ICALP 1986: 40-49 |
| 5 | | Ker-I Ko,
Pekka Orponen,
Uwe Schöning,
Osamu Watanabe:
What Is a Hard Instance of a Computational Problem?.
Structure in Complexity Theory Conference 1986: 197-217 |
| 1985 |
|---|
| 4 | | Osamu Watanabe:
On One-One Polynomial Time Equivalence Relations.
Theor. Comput. Sci. 38: 157-165 (1985) |
| 1983 |
|---|
| 3 | | Osamu Watanabe:
The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines.
Theor. Comput. Sci. 24: 105-117 (1983) |
| 1981 |
|---|
| 2 | | Osamu Watanabe:
A Fast Algorithm for Finding all Shortest Paths.
Inf. Process. Lett. 13(1): 1-3 (1981) |
| 1980 |
|---|
| 1 | | Osamu Watanabe:
Another Application of Recursion Introduction.
Inf. Process. Lett. 10(3): 116-119 (1980) |
