Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarOsamu Watanabe 0001
Person information
- affiliation: Tokyo Institute of Technology, Japan
Other persons with the same name
- Osamu Watanabe
- 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
showing all ?? records
2010 – today
- 2018
[j65]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)- [c77]Tong Qin, Osamu Watanabe:
An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. WALCOM 2018: 93-105 - 2017
- [j64]Suguru Tamaki, Osamu Watanabe:
Local Restrictions from the Furst-Saxe-Sipser Paper. Theory Comput. Syst. 60(1): 20-32 (2017) - [j63]Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
The Query Complexity of Witness Finding. Theory Comput. Syst. 61(2): 305-321 (2017) - [i22]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) - [i21]Tong Qin, Osamu Watanabe:
An improvement of the algorithm of Hertli for the unique 3SAT problem. Electronic Colloquium on Computational Complexity (ECCC) 24: 140 (2017) - 2016
- [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 - [i20]Ryuhei Mori, Osamu Watanabe:
Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges. CoRR abs/1506.00718 (2015) - [i19]Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe:
Generalized Shortest Path Kernel on Graphs. CoRR abs/1510.06492 (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. Electronic Colloquium on Computational Complexity (ECCC) 21: 71 (2014) - 2013
- [j61]
- [j60]Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe:
Is Valiant-Vazirani's isolation probability improvable? Computational Complexity 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. IEEE Conference on Computational Complexity 2013: 277-286 - [i15]Daniel M. Kane, Osamu Watanabe:
A Short Implicant of CNFs with Relatively Many Satisfying Assignments. Electronic Colloquium on Computational Complexity (ECCC) 20: 176 (2013) - 2012
- [j59]Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe:
Propagation Connectivity of Random Hypergraphs. Electr. J. Comb. 19(1): P17 (2012) - [j58]Akinori Kawachi, Hidetoki Tanaka, Osamu Watanabe:
Estimating the Gowers Norm of Modulo Functions over Prime Fields. IEICE Transactions 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? IEEE Conference on Computational Complexity 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. Electronic Colloquium on Computational Complexity (ECCC) 19: 2 (2012) - [i13]Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. Electronic Colloquium on Computational Complexity (ECCC) 19: 32 (2012) - [i12]Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe:
On the Optimality of Lattices for the Coppersmith Technique. IACR Cryptology ePrint Archive 2012: 108 (2012) - 2011
- [j57]Tomonori Ando, Yoshiyuki Kabashima, Hisanao Takahashi, Osamu Watanabe, Masaki Yamamoto:
Spectral Analysis of Random Sparse Matrices. IEICE Transactions 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? Electronic Colloquium on Computational Complexity (ECCC) 18: 151 (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. Intellig. and AI in 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]
- [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. IEEE Conference on Computational Complexity 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. Electronic Colloquium on Computational Complexity (ECCC) 16: 19 (2009) - [i9]Akinori Kawachi, Osamu Watanabe:
Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems. Electronic Colloquium on Computational Complexity (ECCC) 16: 23 (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]
- [c60]Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
On the Complexity of Kings. FCT 2007: 328-340 - [i8]
- 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]
- 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]
- [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]
- [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]
- [c51]
- [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]
- [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]
- [c40]
- [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. Electronic Colloquium on Computational Complexity (ECCC) 7(81) (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]
- [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. IEEE Conference on Computational Complexity 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]
- [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. UCS 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]
- [j30]Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
On Sets Bounded Truth-Table Reducible to P-Selective Sets. ITA 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. UCS 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. Structure in Complexity Theory Conference 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. Computational Complexity 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. Mathematical Systems Theory 27(3): 211-229 (1994) - [j21]Osamu Watanabe, Ricard Gavaldà:
Structural Analysis of Polynomial-Time Query Learnability. Mathematical Systems 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 Generation Comput. 12(4): 337-358 (1994) - [c24]Osamu Watanabe:
Test Instance Generation for Promise NP Search Problems. Structure in Complexity Theory Conference 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]
- [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. Mathematical Systems Theory 26(2): 203-214 (1993) - [j18]