Osamu Watanabe

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	The Robustness of LWPP and WPP, with an Application to Graph Reconstruction	2020	Edith Hemaspaandra Lane A. Hemaspaandra Holger Spakowski Osamu Watanabe
+	Optimizing Memory Layout of Hyperplane Ordering for Vector Supercomputer SX-Aurora TSUBASA	2019	Osamu Watanabe Yuta Hougi Kazuhiko Komatsu Masayuki Sato Akihiro Musa Hiroaki Kobayashi
+	Polynomial size linear programs for problems in P	2019	David Avis David Avis Hans Raj Tiwary Osamu Watanabe
+	The Robustness of LWPP and WPP, with an Application to Graph Reconstruction	2017	Edith Hemaspaandra Lane A. Hemaspaandra Holger Spakowski Osamu Watanabe
+	The Robustness of LWPP and WPP, with an Application to Graph Reconstruction	2017	Edith Hemaspaandra Lane A. Hemaspaandra Holger Spakowski Osamu Watanabe
+ PDF Chat	Generalized Shortest Path Kernel on Graphs	2015	Linus Hermansson Fredrik Johansson Osamu Watanabe
+	Generalized Shortest Path Kernel on Graphs	2015	Linus Hermansson Fredrik Johansson Osamu Watanabe
+	Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges	2015	Ryuhei Mori Osamu Watanabe
+	Polynomial size linear programs for non-bipartite matching problems and other problems in P.	2014	David Avis David Avis Hans Raj Tiwary Osamu Watanabe
+	Random Almost-Popular Matchings	2014	Suthee Ruangwises Osamu Watanabe
+	Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets	2014	Ryuhei Mori Takeshi Koshiba Osamu Watanabe Masaki Yamamoto
+	Polynomial size linear programs for problems in P	2014	David Avis David Avis Hans Raj Tiwary Osamu Watanabe
+	Visual statistical learning and the integration of shape and spatial information	2012	Osamu Watanabe Takada Takuya
+ PDF Chat	Estimating the Gowers Norm of Modulo Functions over Prime Fields	2012	Akinori Kawachi Hidetoki Tanaka Osamu Watanabe
+	A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques	2011	Takeya Shigezumi Yushi Uno Osamu Watanabe
+ PDF Chat	Spectral Analysis of Random Sparse Matrices	2011	Tomonori Ando Yoshiyuki Kabashima Hisanao Takahashi Osamu Watanabe Masaki Yamamoto
+ PDF Chat	Weighted random popular matchings: Weighted Random Popular Matchings	2010	Toshiya Itoh Osamu Watanabe
+	Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices	2010	Yoshiyuki Kabashima Hisanao Takahashi Osamu Watanabe
+	DS-1-7 On Coppersmith's Technique and its Limit	2010	Yoshinori Aono Manindra Agrawal Osamu Watanabe
+ PDF Chat	Weighted random popular matchings	2010	Toshiya Itoh Osamu Watanabe
+	Scale free interval graphs	2009	Naoto Miyoshi Takeya Shigezumi Ryuhei Uehara Osamu Watanabe
+	One-Way Functions and the Isomorphism Conjecture.	2009	Manindra Agrawal Osamu Watanabe
+	Scale Free Interval Graphs	2008	Naoto Miyoshi Takeya Shigezumi Ryuhei Uehara Osamu Watanabe
+	Generalized kolmogorov complexity in relativized separations	2005	Ricard Gavaldà Leen Torenvliet Osamu Watanabe José L. Balcázar
+	Distributions in the Ehrenfest process	2005	Srinivasan Balaji Hosam M. Mahmoud Osamu Watanabe
+	The Complexity of Kings	2005	Edith Hemaspaandra Lane A. Hemaspaandra Osamu Watanabe
+	The Complexity of Kings	2005	Edith Hemaspaandra Lane A. Hemaspaandra Osamu Watanabe
+	Stringent Relativization	2003	Jin‐Yi Cai Osamu Watanabe
+	On a Generalized Ruin Problem	2001	Kazuyuki Amano John Tromp Paul Vitányi Osamu Watanabe
+	Corrigendum to “Upward separation for FewP and related classes”, Information Processing Letters 52 (1994) 175–180	2000	Rajesh P. N. Rao Jörg Rothe Osamu Watanabe
+	Polynomial-Time Multi-Selectivity	1999	Lane A. Hemaspaandra Zhigen Jiang Joerg Rothe Osamu Watanabe
+	Boolean Operations, Joins, and the Extended Low Hierarchy	1999	Lane A. Hemaspaandra Zhigen Jiang Joerg Rothe Osamu Watanabe
+	Boolean operations, joins, and the extended low hierarchy	1998	Lane A. Hemaspaandra Zhigen Jiang Jörg Rothe Osamu Watanabe
+ PDF Chat	Practical Algorithms for On-Line Sampling	1998	Carlos Domingo Ricard Gavaldà Osamu Watanabe
+ PDF Chat	A Role of Constraint in Self-Organization	1998	Carlos Domingo Osamu Watanabe Tadashi Yamazaki
+	Practical algorithms for on-line sampling	1998	Carlos Domingo Ricard Gavaldà Osamu Watanabe
+	Hard instance generation for SAT	1998	Satoshi Horie Osamu Watanabe
+	A role of constraint in self-organization	1998	Carlos Domingo Osamu Watanabe Tadashi Yamazaki
+	Hard instance generation for SAT	1997	Satoshi Horie Osamu Watanabe
+	On Closure Properties of #P in the Context of PF∘#P	1996	Mitsunori Ogihara Thomas Thierauf Seinosuke Toda Osamu Watanabe
+ PDF Chat	On sets bounded truth-table reducible to P-selective sets	1994	Thomas Thierauf Seinosuke Toda Osamu Watanabe
+	Structural analysis of the complexity of inverse functions	1993	Osamu Watanabe Seinosuke Toda
+	On the p-isomorphism conjecture	1991	Osamu Watanabe
+	Kolmogorov complexity and degrees of tally sets	1990	Eric Allender Osamu Watanabe
+ PDF Chat	Notes on theta functions for open Riemann surfaces	1983	Osamu Watanabe
+ PDF Chat	Reproducing differentials and certain theta functions on open Riemann surfaces	1981	Osamu Watanabe
+ PDF Chat	Theory of meromorphic differentials with infinitely many poles on open Riemann surfaces	1977	Osamu Watanabe
+ PDF Chat	A decomposition of meromorphic differentials and its applications	1976	Osamu Watanabe

Common Coauthors

Coauthor	Papers Together
Lane A. Hemaspaandra	8
Edith Hemaspaandra	5
Carlos Domingo	4
Hans Raj Tiwary	3
Takeya Shigezumi	3
Holger Spakowski	3
David Avis	3
Seinosuke Toda	3
Zhigen Jiang	3
Ricard Gavaldà	3
Yoshiyuki Kabashima	2
Hisanao Takahashi	2
Joerg Rothe	2
Manindra Agrawal	2
Satoshi Horie	2
Jörg Rothe	2
Linus Hermansson	2
Ryuhei Mori	2
Fredrik Johansson	2
Tadashi Yamazaki	2
Masaki Yamamoto	2
Toshiya Itoh	2
Thomas Thierauf	2
Ryuhei Uehara	2
Naoto Miyoshi	2
Jin‐Yi Cai	1
Rajesh P. N. Rao	1
Leen Torenvliet	1
Mitsunori Ogihara	1
Akinori Kawachi	1
Paul Vitányi	1
Hidetoki Tanaka	1
Suthee Ruangwises	1
Akihiro Musa	1
John Tromp	1
Yushi Uno	1
José L. Balcázar	1
Kazuyuki Amano	1
Hosam M. Mahmoud	1
Kazuhiko Komatsu	1
Yoshinori Aono	1
Hiroaki Kobayashi	1
Tomonori Ando	1
Masayuki Sato	1
Srinivasan Balaji	1
Takeshi Koshiba	1
Yuta Hougi	1
Eric Allender	1
Takada Takuya	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	Gap-definable counting classes	1994	Stephen Fenner Lance Fortnow Stuart A. Kurtz	3
+ PDF Chat	A generalization of extension complexity that captures P	2015	David Avis Hans Raj Tiwary	3
+	A complexity theory for feasible closure properties	1993	Mitsunori Ogiwara Lane A. Hemachandra	3
+	Maximum matching and a polyhedron with 0,1-vertices	1965	Jack Edmonds	3
+ PDF Chat	The Structure and Function of Complex Networks	2003	Michael Newman	2
+	A note on the extension complexity of the knapsack polytope	2013	Sebastian Pokutta Mathieu Van Vyve	2
+ PDF Chat	On the complexity of graph reconstruction	1994	Dieter Kratsch Lane A. Hemaspaandra	2
+	Complexity results in graph reconstruction	2006	Edith Hemaspaandra Lane A. Hemaspaandra Stanisław Radziszowski Rahul Tripathi	2
+	An Overview Of Some Semantic And Syntactic Complexity Classes	2018	James Lee Cox Tayfun Pay	2
+ PDF Chat	Practical Algorithms for On-Line Sampling	1998	Carlos Domingo Ricard Gavaldà Osamu Watanabe	2
+	On the geometric interpretation of the nonnegative rank	2012	Nicolas Gillis François Glineur	2
+	Topics in graph automorphisms and reconstruction	2004	Josef Lauri Raffaele Scapellato	2
+	On polynomial-time truth-table reducibility of intractable sets to P-selective sets	1991	Seinosuke Toda	2
+ PDF Chat	Square integrable normal differentials on Riemann surfaces	1963	Yukio Kusunoki	2
+	Linear vs. semidefinite extended formulations	2012	Samuel Fiorini Serge Massar Sebastian Pokutta Hans Raj Tiwary Ronald de Wolf	2
+	The Power of Counting	1990	Uwe Schöning	2
+	THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS	1982	Anthony Mansfield	2
+	On some promise classes in structural complexity theory	1995	Jörg rer. nat. Rothe	2
+ PDF Chat	Exponential Lower Bounds for Polytopes in Combinatorial Optimization	2015	Samuel Fiorini Serge Massar Sebastian Pokutta Hans Raj Tiwary Ronald de Wolf	2
+ PDF Chat	Solving Multiclass Learning Problems via Error-Correcting Output Codes	1995	Tom Dietterich Ghulum Bakiri	2
+ PDF Chat	Emergence of Scaling in Random Networks	1999	Albert‐László Barabási Réka Albert	2
+	The complexity of computing the permanent	1979	Leslie G. Valiant	2
+	Graph reconstruction—a survey	1977	J. A. Bondy Robert L. Hemminger	2
+ PDF Chat	Approximate formulas for some functions of prime numbers	1962	J. Barkley Rosser Lowell Schoenfeld	2
+ PDF Chat	A Role of Constraint in Self-Organization	1998	Carlos Domingo Osamu Watanabe Tadashi Yamazaki	2
+	A Spectral Technique for Coloring Random 3-Colorable Graphs	1997	Noga Alon Nabil Kahalé	2
+ PDF Chat	On the extension complexity of combinatorial polytopes	2014	David Avis Hans Raj Tiwary	2
+	Complexity Limitations on Quantum Computation	1999	Lance Fortnow John D. Rogers	1
+	Probability and Computing: Randomized Algorithms and Probabilistic Analysis	2005	Michael Mitzenmacher Eli Upfal	1
+	Polynomial reducibilities and complete sets.	1977	Leonard Berman	1
+	Hard Functions for Low-Degree Polynomials over Prime Fields	2011	Andrej Bogdanov Akinori Kawachi Hidetoki Tanaka	1
+	The distribution of polynomials over finite fields, with applications to the Gowers norms	2007	Ben Green Terence Tao	1
+ PDF Chat	A decomposition of meromorphic differentials and its applications	1976	Osamu Watanabe	1
+ PDF Chat	The matching polytope has exponential extension complexity	2014	Thomas Rothvoß	1
+	Theory of Abelian differentials and relative extremal length with applications to extremal slit mappings	1968	Hisao Mizumoto	1
+ PDF Chat	Graphs whose minimal rank is two	2004	Wayne Barrett Hein van der Holst Raphael Loewy	1
+ PDF Chat	On the Hyperelliptic Riemann Surfaces of Infinite Genus with Absolutely Convergent Riemann’s Theta Functions	1968	Kenichi Tahara	1
+ PDF Chat	Tight Thresholds for Cuckoo Hashing via XORSAT	2010	Martin Dietzfelbinger Andreas Goerdt Michael Mitzenmacher Andrea Montanari Rasmus Pagh Michael Rink	1
+	Spectral techniques applied to sparse random graphs	2005	Uriel Feige E. O. Ofek	1
+ PDF Chat	Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems	1968	Krishna B. Athreya Samuel Karlin	1
+	Hard instance generation for SAT	1997	Satoshi Horie Osamu Watanabe	1
+	SUBEXPONENTIAL INTERVAL GRAPHS GENERATED BY IMMIGRATION–DEATH PROCESSES	2010	Naoto Miyoshi Mariko Ogura Takeya Shigezumi Ryuhei Uehara	1
+ PDF Chat	The Largest Eigenvalue of Sparse Random Graphs	2003	Michael Krivelevich Benny Sudakov	1
+ PDF Chat	Average path length in random networks	2004	Agata Fronczak Piotr Fronczak Janusz A. Hołyst	1
+ PDF Chat	Immunity and Simplicity for Exact Counting and Other Counting Classes	1999	Jörg Rothe	1
+	None	2011	J.L. Rami ́rez Alfonsi ́n Sándor Z. Kiss Imre Z. Ruzsa Carlos Vinuesa	1
+	Spectral redemption in clustering sparse networks	2013	Florent Krząkała Cristopher Moore Elchanan Mossel Joe Neeman Allan Sly Lenka Zdeborová Pan Zhang	1
+	On the second eigenvalue of random regular graphs	1989	Joel Friedman J. Kahn Endre Szemerédi	1
+	The Complexity of Finding Top-Toda-Equivalence-Class Members	2004	Lane A. Hemaspaandra Mitsunori Ogihara Mohammed J. Zaki Marius Zimand	1
+	Kings in k-partite tournaments	1991	Vojislav Petrović Carsten Thomassen	1