Osamu Watanabe

According to our database1, Osamu Watanabe authored at least 173 papers between 1980 and 2019.

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

2019
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Electronic Colloquium on Computational Complexity (ECCC), 2019

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Polynomial size linear programs for problems in P.
Discrete Applied Mathematics, 2019

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

An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem.
Proceedings of the WALCOM: Algorithms and Computation - 12th International Conference, 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

An improvement of the algorithm of Hertli for the unique 3SAT problem.
Electronic Colloquium on Computational Complexity (ECCC), 2017

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
CoRR, 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

Limits of Minimum Circuit Size Problem as Oracle.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Interval graph representation with given interval and intersection lengths.
J. Discrete Algorithms, 2015

Limits of Minimum Circuit Size Problem as Oracle.
Electronic Colloquium on Computational Complexity (ECCC), 2015

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

Generalized Shortest Path Kernel on Graphs.
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.
Electronic Colloquium on Computational Complexity (ECCC), 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

A Short Implicant of a CNF Formula with Many Satisfying Assignments.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

The Query Complexity of Witness Finding.
Proceedings of the Computer Science - Theory and Applications, 2014

2013
A Short Implicant of CNFs with Relatively Many Satisfying Assignments.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Is Valiant-Vazirani's isolation probability improvable?
Computational Complexity, 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, 2013

2012
Estimating the Gowers Norm of Modulo Functions over Prime Fields.
IEICE Transactions, 2012

On the Optimality of Lattices for the Coppersmith Technique.
IACR Cryptology ePrint Archive, 2012

Interval graph representation with given interval and intersection lengths.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Query Complexity and Error Tolerance of Witness Finding Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2012

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

Interval Graph Representation with Given Interval and Intersection Lengths.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Is Valiant-Vazirani's Isolation Probability Improvable?
Proceedings of the 27th Conference on Computational Complexity, 2012

On the Optimality of Lattices for the Coppersmith Technique.
Proceedings of the Information Security and Privacy - 17th Australasian Conference, 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 Transactions, 2011

Is the Valiant-Vazirani Isolation Lemma Improvable?
Electronic Colloquium on Computational Complexity (ECCC), 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. Intellig. and AI in Games, 2010

Weighted random popular matchings.
Random Struct. Algorithms, 2010

A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques.
Proceedings of the WALCOM: Algorithms and Computation, 4th International Workshop, 2010

Propagation Connectivity of Random Hypergraphs.
Proceedings of the Approximation, 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.
Electronic Colloquium on Computational Complexity (ECCC), 2009

One-Way Functions and the Isomorphism Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 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

Scale Free Interval Graphs.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

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

Weighted Random Popular Matchings
CoRR, 2007

On the Complexity of Kings.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Finding Most Likely Solutions.
Proceedings of the Computation and Logic in the Real World, 2007

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

Average-Case Analysis for the MAX-2SAT Problem.
Proceedings of the Theory and Applications of Satisfiability Testing, 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

Random Access to Advice Strings and Collapsing Results.
Proceedings of the Algorithms and Computation, 15th International Symposium, 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

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
Theory Comput. Syst., 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
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.
Proceedings of the STACS 2001, 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
Electronic Colloquium on Computational Complexity (ECCC), 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

Sequential Sampling Techniques for Algorithmic Learning Theory.
Proceedings of the Algorithmic Learning Theory, 11th International Conference, 2000

1999
Boolean Operations, Joins, and the Extended Low Hierarchy
CoRR, 1999

Polynomial-Time Multi-Selectivity
CoRR, 1999

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

Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Proceedings of the Discovery Science, 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

A role of constraint in self-organization
CoRR, 1998

Practical algorithms for on-line sampling
CoRR, 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

Resource Bounded Measure and Learnability.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 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

Partial Occam's Razor and Its Applications.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 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.
ITA, 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

New Collapse Consequences of NP Having Small Circuits.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 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 Generation Comput., 1994

Structural Analysis of Polynomial-Time Query Learnability.
Mathematical Systems Theory, 1994

A Framework for Polynomial-Time Query Learnability.
Mathematical Systems Theory, 1994

Instance Complexity.
J. ACM, 1994

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

On Closure Properties of GapP.
Computational Complexity, 1994

On Sets Bounded Truth-Table Reducible to P-selective Sets.
Proceedings of the STACS 94, 1994

On Random Hard Sets for NP.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

An Optimal Parallel Algorithm for Learning DFA.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 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.
Mathematical Systems Theory, 1993

On Closure Properties of #P in the Context of PF°#P.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 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

On Symmetry of Information and Polynomial Time Invertibility.
Proceedings of the Algorithms and Computation, Third International Symposium, 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.
Mathematical Systems Theory, 1991

On the Computational Complexity of Small Descriptions.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

Relating Equivalence and Reducibility to Sparse Sets.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

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

On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 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.
Bulletin of the EATCS, 1989

On Polynomial Time Turing and Many-One Completeness in PSPACE.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 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 ≤1-ttp-Sparseness and Nondeterministic Complexity Classes (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

On tally relativizations of BP-complexity classes.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Kolmogorov complexity and degrees of tally sets.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 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...