Osamu Watanabe

According to our database1, Osamu Watanabe authored at least 135 papers between 1980 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
An improvement of the algorithm of Hertli for the unique 3SAT problem.
Theor. Comput. Sci., 2020

Space Efficient Separator Algorithms for Planar Graphs.
Proceedings of the WALCOM: Algorithms and Computation - 14th International Conference, 2020

On Nonadaptive Security Reductions of Hitting Set Generators.
Proceedings of the Approximation, 2020

2019
A Space-Efficient Separator Algorithm for Planar Graphs.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2019

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Electron. Colloquium Comput. Complex., 2019

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.
Electron. Colloquium Comput. Complex., 2019

Polynomial size linear programs for problems in P.
Discret. Appl. Math., 2019

2018
On the optimality of lattices for the coppersmith technique.
Appl. Algebra Eng. Commun. Comput., 2018

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017
Local Restrictions from the Furst-Saxe-Sipser Paper.
Theory Comput. Syst., 2017

The Query Complexity of Witness Finding.
Theory Comput. Syst., 2017

2016
A Short Implicant of a CNF Formula with Many Satisfying Assignments.
Algorithmica, 2016

Relating Sublinear Space Computability Among Graph Connectivity and Related Problems.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

2015
Limits of Minimum Circuit Size Problem as Oracle.
Electron. Colloquium Comput. Complex., 2015

Peeling Algorithm on Random Hypergraphs with Superlinear Number of Hyperedges.
CoRR, 2015

Generalized Shortest Path Kernel on Graphs.
Proceedings of the Discovery Science - 18th International Conference, 2015

2014
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem.
Electron. Colloquium Comput. Complex., 2014

Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets.
CoRR, 2014

Polynomial size linear programs for non-bipartite matching problems and other problems in P.
CoRR, 2014

Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013
A Short Implicant of CNFs with Relatively Many Satisfying Assignments.
Electron. Colloquium Comput. Complex., 2013

Is Valiant-Vazirani's isolation probability improvable?
Comput. Complex., 2013

Message Passing Algorithms for MLS-3LIN Problem.
Algorithmica, 2013

An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.
Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, 2013

2012
Estimating the Gowers Norm of Modulo Functions over Prime Fields.
IEICE Trans. Inf. Syst., 2012

Interval graph representation with given interval and intersection lengths.
Electron. Colloquium Comput. Complex., 2012

Query Complexity and Error Tolerance of Witness Finding Algorithms.
Electron. Colloquium Comput. Complex., 2012

Propagation Connectivity of Random Hypergraphs.
Electron. J. Comb., 2012

2011
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques.
J. Graph Algorithms Appl., 2011

Spectral Analysis of Random Sparse Matrices.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2011

Is the Valiant-Vazirani Isolation Lemma Improvable?
Electron. Colloquium Comput. Complex., 2011

Evaluations of Hash Distributed A* in Optimal Sequence Alignment.
Proceedings of the IJCAI 2011, 2011

2010
Average-case analysis for the MAX-2SAT problem.
Theor. Comput. Sci., 2010

On the complexity of kings.
Theor. Comput. Sci., 2010

Evaluating Root Parallelization in Go.
IEEE Trans. Comput. Intell. AI Games, 2010

Weighted random popular matchings.
Random Struct. Algorithms, 2010

2009
Scale free interval graphs.
Theor. Comput. Sci., 2009

Finding Most Likely Solutions.
Theory Comput. Syst., 2009

Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions.
Theory Comput. Syst., 2009

Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems.
Electron. Colloquium Comput. Complex., 2009

One-Way Functions and the Isomorphism Conjecture.
Electron. Colloquium Comput. Complex., 2009

A Replacement Model for a Scale-Free Property of Cliques.
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

One-Way Functions and the Berman-Hartmanis Conjecture.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
Provably Fast Training Algorithms for Support Vector Machines.
Theory Comput. Syst., 2008

2007
Randomized Algorithms for 3-SAT.
Theory Comput. Syst., 2007

2006
Random Access to Advice Strings and Collapsing Results.
Algorithmica, 2006

A Simple Message Passing Algorithm for Graph Partitioning Problems.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005
Sequential sampling techniques for algorithmic learning theory.
Theor. Comput. Sci., 2005

Substring search and repeat search using factor oracles.
Inf. Process. Lett., 2005

The Complexity of Kings
CoRR, 2005

Some Heuristic Analysis of Local Search Algorithms for SAT Problems.
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2005

2004
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.
SIAM J. Comput., 2004

Games with Uniqueness Properties.
Theory Comput. Syst., 2004

Relativized collapsing between BPP and PH under stringent oracle access.
Inf. Process. Lett., 2004

Learning r-of-k Functions by Boosting.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003
Analysis of Randomized Local Search Algorithm for LDPCC Decoding Problem.
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

Stringent Relativization.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002
Preface
Theor. Comput. Sci., 2002

Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Data Min. Knowl. Discov., 2002

A Probabilistic 3-SAT Algorithm Further Improved.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Games with a Uniqueness Property.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Algorithmic Aspects of Boosting.
Proceedings of the Progress in Discovery Science, 2002

2001
How Can Computer Science Contribute to Knowledge Discovery?
Proceedings of the SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics Piestany, Slovak Republic, November 24, 2001

Sequential Sampling Algorithms: Unified Analysis and Lower Bounds.
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

On a Generalized Ruin Problem.
Proceedings of the Approximation, 2001

Provably Fast Training Algorithms for Support Vector Machines.
Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November, 2001

Deterministic Application of Grover's Quantum Search Algorithm.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

A Random Sampling Technique for Training Support Vector Machines.
Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

2000
Resource-Bounded Measure and Learnability.
Theory Comput. Syst., 2000

Corrigendum to "Upward separation for FewP and related classes".
Inf. Process. Lett., 2000

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems
Electron. Colloquium Comput. Complex., 2000

Scaling Up a Boosting-Based Learner via Adaptive Sampling.
Proceedings of the Knowledge Discovery and Data Mining, 2000

MadaBoost: A Modification of AdaBoost.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999
From Computational Learning Theory to Discovery Science.
Proceedings of the Automata, 1999

Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
Boolean Operations, Joins, and the Extended Low Hierarchy.
Theor. Comput. Sci., 1998

New Collapse Consequences of NP Having Small Circuits.
SIAM J. Comput., 1998

Hard instance generation for SAT
CoRR, 1998

A Role of Constraint in Self-Organization.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Practical Algorithms for On-line Sampling.
Proceedings of the Discovery Science, 1998

1997
Polynomial-Time Multi-Selectivity.
J. UCS, 1997

Partial Occam's Razor and its Applications.
Inf. Process. Lett., 1997

Hard Instance Generation for SAT (Extended Abstract).
Proceedings of the Algorithms and Computation, 8th International Symposium, 1997

Coding Complexity: The Computational Complexity of Succinct Descriptions.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996
Randomized Approximation of the Constraint Satisfaction Problem.
Nord. J. Comput., 1996

An Optimal Parallel Algorithm for Learning DFA.
J. UCS, 1996

On Closure Properties of #P in the Context of PF ° #P.
J. Comput. Syst. Sci., 1996

On Sets Bounded Truth-Table Reducible to P-Selective Sets.
RAIRO Theor. Informatics Appl., 1996

On Random Hard Sets for NP.
Inf. Comput., 1996

Randomized Approximation of the Constraint Satisfaction Problem (Extended Abstract).
Proceedings of the Algorithm Theory, 1996

An Improvement of the Digital Cash Protocol of Okamoto and Ohta.
Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

The Join Can Lower Complexity.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
On Symmetry of Information and Polynomial Time Invertibility
Inf. Comput., August, 1995

Towards Average-Case Complexity Analysis of NP Optimization Problems.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
The Query Complexity of Learning DFA.
New Gener. Comput., 1994

Structural Analysis of Polynomial-Time Query Learnability.
Math. Syst. Theory, 1994

A Framework for Polynomial-Time Query Learnability.
Math. Syst. Theory, 1994

Instance Complexity.
J. ACM, 1994

Upward Separation for FewP and Related Classes.
Inf. Process. Lett., 1994

On Closure Properties of GapP.
Comput. Complex., 1994

Test Instance Generation for Promise NP Search Problems.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
A View of Structural Complexity Theory.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On the Computational Complexity of Small Descriptions.
SIAM J. Comput., 1993

Structural Analysis of the Complexity of Inverse Functions.
Math. Syst. Theory, 1993

1992
On Polynomial-Time Turing and Many-One Completeness in PSPACE.
Theor. Comput. Sci., 1992

Polynomial Time 1-Turing Reductions from #PH to #P.
Theor. Comput. Sci., 1992

Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput., 1992

On Polynomial Time One-Truth-Table Reducibility to a Sparse Set.
J. Comput. Syst. Sci., 1992

On the Complexity of Small Description and Related Topics.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Computational and Statistical Indistinguishabilities.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

How Hard Are Sparse Sets?
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

A Note on the Query Complexity of Learning DFA (Extended Abstract).
Proceedings of the Algorithmic Learning Theory, Third Workshop, 1992

1991
On the p-Isomorphism Conjecture.
Theor. Comput. Sci., 1991

On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets.
SIAM J. Comput., 1991

On Intractability of the Class UP.
Math. Syst. Theory, 1991

1990
Kolmogorov Complexity and Degrees of Tally Sets
Inf. Comput., June, 1990

Structural Analyses on the Complexity of Inverting Functions.
Proceedings of the Algorithms, 1990

Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

A Formal Study of Learning via Queries.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract).
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
On Tally Relativizations of BP-Complexity Classes.
SIAM J. Comput., 1989

A view of structural complexity theory.
Bull. EATCS, 1989

1988
Lowness Properties of Sets in the Exponential-Time Hierarchy.
SIAM J. Comput., 1988

On Hardness of One-Way Functions.
Inf. Process. Lett., 1988

On ≤<sub>1-tt</sub><sup>p</sup>-Sparseness and Nondeterministic Complexity Classes (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987
A Comparison of Polynomial Time Completeness Notions.
Theor. Comput. Sci., 1987

Polynomial time reducibility to a set of small density.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

On the structure of interactable complexity classes.
PhD thesis, 1987

1986
On Exponential Lowness.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

What Is a Hard Instance of a Computational Problem?.
Proceedings of the Structure in Complexity Theory, 1986

1985
On One-One Polynomial Time Equivalence Relations.
Theor. Comput. Sci., 1985

1983
The Time-Precision Tradeoff Problem on On-Line Probabilistic Turing Machines.
Theor. Comput. Sci., 1983

1981
A Fast Algorithm for Finding all Shortest Paths.
Inf. Process. Lett., 1981

1980
Another Application of Recursion Introduction.
Inf. Process. Lett., 1980


  Loading...