We stand with Ukraine

We stand with Ukraine

Kazuo Iwama

Orcid: 0000-0002-5339-0669

Affiliations:

Kyoto University, Japan

According to our database¹, Kazuo Iwama authored at least 192 papers between 1977 and 2023.

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of two.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

Online presence:

On csauthors.net:

Bibliography

2023

Marriage and Roommate.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

Int. J. Found. Comput. Sci., November, 2023

2022

Tight competitive analyses of online car-sharing problems.

[BibT_eX]

[DOI]

,

,

,

,

Chung-Shou Liao

Theor. Comput. Sci., 2022

Bounded Hanoi.

[BibT_eX]

[DOI]

,

Am. Math. Mon., 2022

Improving the Bounds of the Online Dynamic Power Management Problem.

[BibT_eX]

[DOI]

,

,

Chung-Shou Liao

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

Randomized Scheduling for the Online Car-sharing Problem.

[BibT_eX]

[DOI]

,

,

,

,

Chung-Shou Liao

CoRR, 2021

Tight Competitive Analyses of Online Car-Sharing Problems.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

2020

Improved average complexity for comparison-based sorting.

[BibT_eX]

[DOI]

,

Junichi Teruyama

Theor. Comput. Sci., 2020

2019

Read-Once Branching Programs for Tree Evaluation Problems.

[BibT_eX]

[DOI]

,

ACM Trans. Comput. Theory, 2019

Letter from the Editor.

[BibT_eX]

[DOI]

Bull. EATCS, 2019

2018

Parameterized Testability.

[BibT_eX]

[DOI]

,

ACM Trans. Comput. Theory, 2018

Letter from the Bulletin Editor.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms.

[BibT_eX]

[DOI]

,

Junichi Teruyama

,

Shuntaro Tsuyama

CoRR, 2018

Small Complexity Gaps for Comparison-Based Sorting.

[BibT_eX]

[DOI]

,

,

Junichi Teruyama

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Twenty Lectures on Algorithmic Game Theory.

[BibT_eX]

[DOI]

Tim Roughgarden

,

Bull. EATCS, 2017

2016

Stable Marriage with Ties and Incomplete Lists.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

Encyclopedia of Algorithms, 2016

Exact Algorithms for <i>k</i> SAT Based on Local Search.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Approximate strip packing: Revisited.

[BibT_eX]

[DOI]

,

,

,

Inf. Comput., 2016

Quantum Query Complexity of Almost All Functions with Fixed On-set Size.

[BibT_eX]

[DOI]

Andris Ambainis

,

,

Masaki Nakanishi

,

Harumichi Nishimura

,

,

,

Shigeru Yamashita

Comput. Complex., 2016

Preface.

[BibT_eX]

[DOI]

,

,

Balt. J. Mod. Comput., 2016

The Hospitals/Residents Problem with Lower Quotas.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

Algorithmica, 2016

Total Stability in Stable Matching Games.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

2015

Finding Witnesses for Stability in the Hospitals/Residents Problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

J. Inf. Process., 2015

Online bin packing with (1, 1) and (2, R) bins.

[BibT_eX]

[DOI]

,

,

,

J. Comb. Optim., 2015

Stable Nash Equilibria in the Gale-Shapley Matching Game.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

CoRR, 2015

A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties.

[BibT_eX]

[DOI]

Chien-Chung Huang

,

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

Proceedings of the Approximation, 2015

2014

Reputation games for undirected graphs.

[BibT_eX]

[DOI]

,

,

Discret. Appl. Math., 2014

Correction: Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. <i>Algorithms </i>2014, <i>7</i>, 166-185.

[BibT_eX]

[DOI]

Algorithms, 2014

A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

Algorithmica, 2014

2013

A Harmonic Algorithm for the 3D Strip Packing Problem.

[BibT_eX]

[DOI]

,

,

,

Maxim Sviridenko

,

SIAM J. Comput., 2013

Parameterized Complexity and the Understanding, Design, and Analysis of Heuristics (NII Shonan Meeting 2013-2).

[BibT_eX]

[DOI]

Gregory Z. Gutin

,

,

Dimitrios M. Thilikos

NII Shonan Meet. Rep., 2013

Recovering Strings in Oracles: Quantum and Classic.

[BibT_eX]

[DOI]

,

Harumichi Nishimura

Int. J. Found. Comput. Sci., 2013

Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists.

[BibT_eX]

[DOI]

,

Robert W. Irving

,

,

Shuichi Miyazaki

,

Algorithms, 2013

The Train Delivery Problem Revisited.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012

Quantum counterfeit coin problems.

[BibT_eX]

[DOI]

,

Harumichi Nishimura

,

,

Junichi Teruyama

Theor. Comput. Sci., 2012

Improved approximation bounds for the Student-Project Allocation problem with preferences over projects.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

J. Discrete Algorithms, 2012

Approximability of Stable Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation - 6th International Workshop, 2012

Reconstructing Strings from Substrings with Quantum Queries.

[BibT_eX]

[DOI]

,

,

François Le Gall

,

Harumichi Nishimura

,

,

Junichi Teruyama

,

Shigeru Yamashita

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Recovering Strings in Oracles: Quantum and Classic.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

2011

A randomized algorithm for two servers in cross polytope spaces.

[BibT_eX]

[DOI]

Wolfgang W. Bein

,

,

,

Lawrence L. Larmore

,

James A. Oravec

Theor. Comput. Sci., 2011

Average-case competitive analyses for one-way trading.

[BibT_eX]

[DOI]

Hiroshi Fujiwara

,

,

Yoshiyuki Sekiguchi

J. Comb. Optim., 2011

Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs.

[BibT_eX]

[DOI]

,

,

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

The Hospitals/Residents Problem with Quota Lower Bounds.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

Proceedings of the Algorithms - ESA 2011, 2011

2010

The complexity of the Hajós calculus for planar graphs.

[BibT_eX]

[DOI]

,

,

Theor. Comput. Sci., 2010

Approximation algorithms for the sex-equal stable marriage problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

ACM Trans. Algorithms, 2010

Online knapsack with resource augmentation.

[BibT_eX]

[DOI]

,

Inf. Process. Lett., 2010

The Planar Hajós Calculus for Bounded Degree Graphs.

[BibT_eX]

[DOI]

,

,

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2010

Guest Editorial: Special Issue on Matching Under Preferences.

[BibT_eX]

[DOI]

David F. Manlove

,

Robert W. Irving

,

Algorithmica, 2010

Improved Randomized Algorithms for 3-SAT.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Averaging Techniques for Competitive Auctions.

[BibT_eX]

[DOI]

Takayuki Ichiba

,

Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics, 2010

2009

Enumeration of isolated cliques and pseudo-cliques.

[BibT_eX]

[DOI]

,

ACM Trans. Algorithms, 2009

Drawing Borders Efficiently.

[BibT_eX]

[DOI]

,

,

Theory Comput. Syst., 2009

An improved approximation lower bound for finding almost stable maximum matchings.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

Inf. Process. Lett., 2009

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

[BibT_eX]

[DOI]

Andris Ambainis

,

,

Masaki Nakanishi

,

Harumichi Nishimura

,

,

,

Shigeru Yamashita

CoRR, 2009

Negation-Limited Complexity of Parity and Inverters.

[BibT_eX]

[DOI]

,

Hiroki Morizumi

,

Algorithmica, 2009

Quantum Queries on Permutations with a Promise.

[BibT_eX]

[DOI]

Rusins Freivalds

,

Proceedings of the Implementation and Application of Automata, 2009

2008

Stable Marriage with Ties and Incomplete Lists.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Local Search Algorithms for kSAT.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Reductions for monotone Boolean circuits.

[BibT_eX]

[DOI]

,

Hiroki Morizumi

,

Theor. Comput. Sci., 2008

Online Removable Square Packing.

[BibT_eX]

[DOI]

,

,

Theory Comput. Syst., 2008

Online chasing problems for regular polygons.

[BibT_eX]

[DOI]

Hiroshi Fujiwara

,

,

Inf. Process. Lett., 2008

New Graph Calculi for Planar Non-3-Colorable Graphs.

[BibT_eX]

[DOI]

Youichi Hanatani

,

Takashi Horiyama

,

,

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2008

The Complexity of the Hajos Calculus for Planar Graphs.

[BibT_eX]

[DOI]

,

Electron. Colloquium Comput. Complex., 2008

On Two Dimensional Orthogonal Knapsack Problem

[BibT_eX]

[DOI]

,

,

CoRR, 2008

Editor's Foreword.

[BibT_eX]

[DOI]

Algorithms, 2008

Randomized Competitive Analysis for Two Server Problems.

[BibT_eX]

[DOI]

Wolfgang W. Bein

,

,

Algorithms, 2008

A (2-<i>c</i>(1/sqrt(N)))-Approximation Algorithm for the Stable Marriage Problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Algorithmica, 2008

Max-Stretch Reduction for Tree Spanners.

[BibT_eX]

[DOI]

,

,

Algorithmica, 2008

SAT, UNSAT and Coloring.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2008

Quantum Query Complexity of Boolean Functions with Small On-Sets.

[BibT_eX]

[DOI]

Andris Ambainis

,

,

Masaki Nakanishi

,

Harumichi Nishimura

,

,

,

Shigeru Yamashita

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Polynomial-Time Construction of Linear Network Coding.

[BibT_eX]

[DOI]

,

Harumichi Nishimura

,

,

,

Shigeru Yamashita

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.

[BibT_eX]

[DOI]

,

,

,

,

,

,

,

Johan M. M. van Rooij

,

Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

08431 Executive Summary - Moderately Exponential Time Algorithms.

[BibT_eX]

[DOI]

,

,

Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

08431 Abstracts Collection - Moderately Exponential Time Algorithms.

[BibT_eX]

[DOI]

,

,

Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

2007

Improved algorithms for quantum identification of Boolean oracles.

[BibT_eX]

[DOI]

Andris Ambainis

,

,

Akinori Kawachi

,

,

Shigeru Yamashita

Theor. Comput. Sci., 2007

Improved approximation results for the stable marriage problem.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

ACM Trans. Algorithms, 2007

Exploiting partial knowledge of satisfying assignments.

[BibT_eX]

[DOI]

,

Discret. Appl. Math., 2007

A 1.875: approximation algorithm for the stable marriage problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Harmonic algorithm for 3-dimensional strip packing problem.

[BibT_eX]

[DOI]

,

,

,

Maxim Sviridenko

,

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Online Chasing Problems for Regular n-Gons.

[BibT_eX]

[DOI]

Hiroshi Fujiwara

,

,

Proceedings of the 2007 IEEE International Conference on Research, 2007

Unbounded-Error Classical and Quantum Communication Complexity.

[BibT_eX]

[DOI]

,

Harumichi Nishimura

,

,

Shigeru Yamashita

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Unbounded-Error One-Way Classical and Quantum Communication Complexity.

[BibT_eX]

[DOI]

,

Harumichi Nishimura

,

,

Shigeru Yamashita

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

An Improved Exact Algorithm for Cubic Graph TSP.

[BibT_eX]

[DOI]

,

Takuya Nakashima

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

Properties of Symmetric Incentive Compatible Auctions.

[BibT_eX]

[DOI]

,

,

,

,

Toyotaka Tasaka

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

Flow Time Minimization under Energy Constraints.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the 12th Conference on Asia South Pacific Design Automation, 2007

Optimal Resource Augmentations for Online Knapsack.

[BibT_eX]

[DOI]

,

Proceedings of the Approximation, 2007

Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs.

[BibT_eX]

[DOI]

,

,

,

Proceedings of the Algorithmic Aspects in Information and Management, 2007

2006

Quantum lower bounds for the Goldreich-Levin problem.

[BibT_eX]

[DOI]

,

,

,

Raymond H. Putra

,

Shigeru Yamashita

Inf. Process. Lett., 2006

A (2 - <i>c</i>log <i>N</i>/<i>N</i>)-Approximation Algorithm for the Stable Marriage Problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

IEICE Trans. Inf. Syst., 2006

Efficient Methods for Determining DNA Probe Orders.

[BibT_eX]

[DOI]

,

,

Takeyuki Tamura

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2006

Approximated Vertex Cover for Graphs with Perfect Matchings.

[BibT_eX]

[DOI]

Tomokazu Imamura

,

,

Tatsuie Tsukiji

IEICE Trans. Inf. Syst., 2006

Strip Packing vs. Bin Packing.

[BibT_eX]

[DOI]

,

,

,

Electron. Colloquium Comput. Complex., 2006

Density condensation of Boolean formulas.

[BibT_eX]

[DOI]

Youichi Hanatani

,

Takashi Horiyama

,

Discret. Appl. Math., 2006

New Upper Bounds on The Approximability of 3D Strip Packing

[BibT_eX]

[DOI]

,

,

CoRR, 2006

Classic and Quantum Network Coding.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2006

Reductions for Monotone Boolean Circuits.

[BibT_eX]

[DOI]

,

Hiroki Morizumi

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

(4, 1)-Quantum Random Access Coding Does Not Exist.

[BibT_eX]

[DOI]

Masahito Hayashi

,

,

Harumichi Nishimura

,

,

Shigeru Yamashita

Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Stable Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Finite-State Online Algorithms and Their Automated Competitive Analysis.

[BibT_eX]

[DOI]

Takashi Horiyama

,

,

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Quantum Network Coding.

[BibT_eX]

[DOI]

Masahito Hayashi

,

,

Harumichi Nishimura

,

,

Shigeru Yamashita

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

Single backup table schemes for shortest-path routing.

[BibT_eX]

[DOI]

,

,

,

Takuya Yoshihiro

Theor. Comput. Sci., 2005

Quantum Sampling for Balanced Allocations.

[BibT_eX]

[DOI]

,

Akinori Kawachi

,

Shigeru Yamashita

IEICE Trans. Inf. Syst., 2005

Compact Routing with Stretch Factor of Less Than Three.

[BibT_eX]

[DOI]

,

Akinori Kawachi

IEICE Trans. Inf. Syst., 2005

Average-Case Competitive Analyses for Ski-Rental Problems.

[BibT_eX]

[DOI]

Hiroshi Fujiwara

,

Algorithmica, 2005

Approximating vertex cover on dense graphs.

[BibT_eX]

[DOI]

Tomokazu Imamura

,

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

A (2-c*(1/sqrt(N)))-Approximation Algorithm for the Stable Marriage Problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

The Delayed <i>k</i>-Server Problem.

[BibT_eX]

[DOI]

Wolfgang W. Bein

,

,

Lawrence L. Larmore

,

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Linear-Time Enumeration of Isolated Cliques.

[BibT_eX]

[DOI]

,

,

Proceedings of the Algorithms, 2005

2004

Randomized approximation of the stable marriage problem.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

Theor. Comput. Sci., 2004

Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs.

[BibT_eX]

[DOI]

Toshiyuki Fujiwara

,

,

J. Parallel Distributed Comput., 2004

The orthogonal CNN problem.

[BibT_eX]

[DOI]

,

Inf. Process. Lett., 2004

Worst-Case Upper Bounds for kSAT (Column: Algorithmics).

[BibT_eX]

Bull. EATCS, 2004

A (2-c(log N/N))-Approximation Algorithm for the Stable Marriage Problem.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

,

Proceedings of the Algorithm Theory, 2004

Quantum Identification of Boolean Oracles.

[BibT_eX]

[DOI]

Andris Ambainis

,

,

Akinori Kawachi

,

Hiroyuki Masuda

,

Raymond H. Putra

,

Shigeru Yamashita

Proceedings of the STACS 2004, 2004

Approximated Two Choices in Randomized Load Balancing.

[BibT_eX]

[DOI]

,

Akinori Kawachi

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Imperfectness of Data for STS-Based Physical Mapping.

[BibT_eX]

[DOI]

,

,

Takeyuki Tamura

Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003

A family of NFAs which need 2n- deterministic states.

[BibT_eX]

[DOI]

,

Akihiro Matsuura

,

Theor. Comput. Sci., 2003

Approximability results for stable marriage problems with ties.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

Robert W. Irving

,

,

David F. Manlove

,

Shuichi Miyazaki

,

Yasufumi Morita

,

Theor. Comput. Sci., 2003

Transformation Rules for CNOT-based Quantum Circuits and Their Applications.

[BibT_eX]

[DOI]

,

Shigeru Yamashita

New Gener. Comput., 2003

A New Quantum Claw-finding Algorithm for Three Functions.

[BibT_eX]

[DOI]

,

Akinori Kawachi

New Gener. Comput., 2003

Avoiding Routing Loops on the Internet.

[BibT_eX]

[DOI]

,

,

,

Takuya Yoshihiro

Theory Comput. Syst., 2003

Inclusion-exclusion for k-CNF formulas.

[BibT_eX]

[DOI]

,

,

,

,

Akihiro Matsuura

Inf. Process. Lett., 2003

Improved Upper Bounds for 3-SAT

[BibT_eX]

[DOI]

,

Electron. Colloquium Comput. Complex., 2003

Compact Routing for Flat Networks.

[BibT_eX]

[DOI]

,

Proceedings of the Distributed Computing, 17th International Conference, 2003

Polynomial-Time Computable Backup Tables for Shortest-Path Routing.

[BibT_eX]

,

,

,

Takuya Yoshihiro

Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

Improved Approximation of the Stable Marriage Problem.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

,

Shuichi Miyazaki

,

Hiroki Yanagisawa

Proceedings of the Algorithms, 2003

2002

Hard variants of stable marriage.

[BibT_eX]

[DOI]

David F. Manlove

,

Robert W. Irving

,

,

Shuichi Miyazaki

,

Yasufumi Morita

Theor. Comput. Sci., 2002

Online independent sets.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

,

Shuichi Miyazaki

,

Theor. Comput. Sci., 2002

Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM.

[BibT_eX]

[DOI]

,

,

Shuichi Miyazaki

,

,

ACM J. Exp. Algorithmics, 2002

Complexity of finding dense subgraphs.

[BibT_eX]

[DOI]

,

,

Discret. Appl. Math., 2002

Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations.

[BibT_eX]

[DOI]

,

,

Raymond H. Putra

Proceedings of the Unconventional Models of Computation, Third International Conference, 2002

Compact routing for average-case networks.

[BibT_eX]

[DOI]

,

Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

An Explicit Lower Bound of 5n - o(n) for Boolean Circuits.

[BibT_eX]

[DOI]

,

Hiroki Morizumi

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Inapproximability Results on Stable Marriage Problems.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

,

,

Shuichi Miyazaki

,

Yasufumi Morita

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Removable Online Knapsack Problems.

[BibT_eX]

[DOI]

,

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Transformation rules for designing CNOT-based quantum circuits.

[BibT_eX]

[DOI]

,

Yahiko Kambayashi

,

Shigeru Yamashita

Proceedings of the 39th Design Automation Conference, 2002

2001

Efficient randomized routing algorithms on the two-dimensional mesh of buses.

[BibT_eX]

[DOI]

,

,

,

Theor. Comput. Sci., 2001

New Bounds for Oblivious Mesh Routing.

[BibT_eX]

[DOI]

,

Yahiko Kambayashi

,

J. Graph Algorithms Appl., 2001

An Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size.

[BibT_eX]

[DOI]

,

J. Algorithms, 2001

A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes.

[BibT_eX]

[DOI]

,

J. Algorithms, 2001

Separating Oblivious and Non-oblivious BPs.

[BibT_eX]

[DOI]

,

,

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000

Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs.

[BibT_eX]

[DOI]

,

Yahiko Kambayashi

,

Theor. Comput. Sci., 2000

Oblivious Routing Algorithms on the Mesh of Buses.

[BibT_eX]

[DOI]

,

J. Parallel Distributed Comput., 2000

Greedily Finding a Dense Subgraph.

[BibT_eX]

[DOI]

,

,

,

Takeshi Tokuyama

J. Algorithms, 2000

A (2.954 epsilon)n oblivious routing algorithm on 2D meshes.

[BibT_eX]

[DOI]

,

Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

Compact routing with stretch factor of less than three (brief announcement).

[BibT_eX]

[DOI]

,

Akinori Kawachi

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

A Family of NFA's Which Need 2<sup>n</sup> -<i>alpha</i> Deterministic States.

[BibT_eX]

[DOI]

,

Akihiro Matsuura

,

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.

[BibT_eX]

[DOI]

,

Magnús M. Halldórsson

,

,

Takeshi Matsuda

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

1999

Approximation of coNP sets by NP-complete sets and its applications.

[BibT_eX]

[DOI]

Shuichi Miyazaki

,

Syst. Comput. Jpn., 1999

Undecidability on Quantum Finite Automata.

[BibT_eX]

[DOI]

,

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

An O(N) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size.

[BibT_eX]

[DOI]

,

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

Stable Marriage with Incomplete Lists and Ties.

[BibT_eX]

[DOI]

,

David F. Manlove

,

Shuichi Miyazaki

,

Yasufumi Morita

Proceedings of the Automata, 1999

Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing.

[BibT_eX]

[DOI]

,

Proceedings of the Algorithms, 1999

Using Generalized Forecasts for Online Currency Conversion.

[BibT_eX]

[DOI]

,

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

A Canonical Form of Vector Machines.

[BibT_eX]

[DOI]

,

Inf. Comput., 1998

Better Approximations of Non-Hamiltonian Graphs.

[BibT_eX]

[DOI]

,

Discret. Appl. Math., 1998

Optimizing OBDDs Is Still Intractable for Monotone Functions.

[BibT_eX]

[DOI]

,

Mitsushi Nouzoe

,

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Improved Time and Space Hierarchies of One-Tape Off-Line TMs.

[BibT_eX]

[DOI]

,

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

A Faster Parallel Algorithm for k-Connectivity.

[BibT_eX]

[DOI]

,

,

Inf. Process. Lett., 1997

Complexity of Finding Short Resolution Proofs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Three-Dimensional Meshes are Less Powerful than Two-Dimensional Ones in Oblivious Routing.

[BibT_eX]

[DOI]

,

Proceedings of the Algorithms, 1997

Tight Bounds on the Number of States of DFA's That Are Equivalent to n-state NFA's.

[BibT_eX]

,

Proceedings of the 3rd International Conference Developments in Language Theory, 1997

Random benchmark circuits with controlled attributes.

[BibT_eX]

[DOI]

,

,

Hiroyuki Kurokawa

,

Proceedings of the European Design and Test Conference, 1997

Local Search Algorithms for Partial MAXSAT.

[BibT_eX]

[DOI]

,

,

Yahiko Kambayashi

,

Shuichi Miyazaki

Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, 1997

1996

Time Lower Bounds do not Exist for CRCW PRAMs.

[BibT_eX]

[DOI]

,

,

Theor. Comput. Sci., 1996

Routing Problems on the Mesh of Buses.

[BibT_eX]

[DOI]

,

,

Yahiko Kambayashi

J. Algorithms, 1996

alpha-Connectivity: A Gradually Nonparallel Graph Problem.

[BibT_eX]

,

J. Algorithms, 1996

Satisfiability of 3CNF formulas with small clause/variable-ratio.

[BibT_eX]

[DOI]

,

Proceedings of the Satisfiability Problem: Theory and Applications, 1996

Database Queries as Combinatorial Optimization Problems.

[BibT_eX]

Shuichi Miyazaki

,

,

Yahiko Kambayashi

Proceedings of the International Symposium on Cooperative Database Systems for Advanced Applications, 1996

Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits.

[BibT_eX]

[DOI]

,

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Adding New Clauses for Faster Local Search.

[BibT_eX]

[DOI]

,

Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, 1996

1995

Exponential Lower Bounds for the Tree-Like Hajós Calculus.

[BibT_eX]

[DOI]

,

Toniann Pitassi

Inf. Process. Lett., 1995

Finding Dense Subgraphs.

[BibT_eX]

[DOI]

,

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas.

[BibT_eX]

[DOI]

,

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

Approximation of coNP Sets by NP-complete Sets.

[BibT_eX]

[DOI]

,

Shuichi Miyazaki

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

Intractability of Read-Once Resolution.

[BibT_eX]

[DOI]

,

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

A Simpler Parallel Algorithm for Graph Conectivity.

[BibT_eX]

[DOI]

,

Yahiko Kambayashi

J. Algorithms, 1994

Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity.

[BibT_eX]

[DOI]

,

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

SAT-Varible Complexity of Hard Combinatorial Problems.

[BibT_eX]

,

Shuichi Miyazaki

Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

Random Generation of Test Instances for Logic Optimizers.

[BibT_eX]

[DOI]

,

Proceedings of the 31st Conference on Design Automation, 1994

1993

ASPACE(o(log log n)) is Regular.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

Rs-vector algorithms for combinational problems.

[BibT_eX]

[DOI]

,

Syst. Comput. Jpn., 1993

Low-Level Tradeoffs between Reversals and Alternations.

[BibT_eX]

Proceedings of the Developments in Language Theory, 1993

Random generation of test instances with controlled attributes.

[BibT_eX]

[DOI]

,

,

Proceedings of the Cliques, 1993

1992

Routing Problems on the Mesh of Buses.

[BibT_eX]

[DOI]

,

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Random Generation of Satisfiable and Unsatisfiable CNF Predicates.

[BibT_eX]

,

Hidetoshi Abeta

,

Proceedings of the Algorithms, Software, Architecture, 1992

1989

CNF Satisfiability Test by Counting and Polynomial Average Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

An O(log n) Parallel Connectivity Algorithm on the Mesh of Buses.

[BibT_eX]

,

Yahiko Kambayashi

Proceedings of the Information Processing 89, Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28, 1989

1983

The Universe Problem for Unrestricted Flow Languages.

[BibT_eX]

[DOI]

Acta Informatica, 1983

Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

On Equations Including String Variables

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1977

Labolink: An Optically Linked Laboratory Computer Network.

[BibT_eX]

[DOI]

,

Yahiko Kambayashi

,

,

Computer, 1977

Loading...