Kazuo Iwama
#123,366
Most Influential Person Now
Japanese computer scientist
Kazuo Iwama 's AcademicInfluence.com Rankings
Kazuo Iwama mathematics Degrees
Mathematics
#7521
World Rank
#10212
Historical Rank
Complexity Theory
#16
World Rank
#16
Historical Rank
Measure Theory
#2871
World Rank
#3413
Historical Rank
Download Badge
Computer Science Mathematics
Kazuo Iwama 's Degrees
- Bachelors Mathematics Kyoto University
- Masters Mathematics Kyoto University
- PhD Mathematics Kyoto University
Similar Degrees You Can Earn
Why Is Kazuo Iwama Influential?
(Suggest an Edit or Addition)According to Wikipedia, Kazuo Iwama is a Japanese computer scientist who works at Kyoto University. Topics in his research include stable marriage, quantum circuits, the Boolean satisfiability problem, and algorithms on graphs.
Kazuo Iwama 's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Hard variants of stable marriage (2002) (313)
- Greedily Finding a Dense Subgraph (1996) (239)
- Transformation rules for designing CNOT-based quantum circuits (2002) (200)
- Stable Marriage with Incomplete Lists and Ties (1999) (193)
- A Survey of the Stable Marriage Problem and Its Variants (2008) (158)
- Quantum Network Coding (2006) (150)
- Twenty Lectures on Algorithmic Game Theory (2016) (147)
- CONNECTIVITY (1996) (143)
- Improved upper bounds for 3-SAT (2004) (126)
- Complexity of finding dense subgraphs (2002) (122)
- Removable Online Knapsack Problems (2002) (99)
- CNF Satisfiability Test by Counting and Polynomial Average Time (1989) (96)
- Editor's Foreword (2008) (92)
- Random generation of test instances with controlled attributes (1993) (89)
- SAT-Varible Complexity of Hard Combinatorial Problems (1994) (86)
- Approximability results for stable marriage problems with ties (2003) (84)
- An Explicit Lower Bound of 5n - o(n) for Boolean Circuits (2002) (82)
- Local Search Algorithms for Partial MAXSAT (1997) (78)
- Adding New Clauses for Faster Local Search (1996) (73)
- Improved approximation results for the stable marriage problem (2007) (69)
- Undecidability on quantum finite automata (1999) (63)
- Average-Case Competitive Analyses for Ski-Rental Problems (2002) (63)
- Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas (1995) (61)
- A 1.875: approximation algorithm for the stable marriage problem (2006) (60)
- An Improved Exact Algorithm for Cubic Graph TSP (2007) (56)
- (4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits (2006) (51)
- Randomized approximation of the stable marriage problem (2003) (50)
- Intractability of read-once resolution (1995) (49)
- Quantum Identification of Boolean Oracles (2004) (49)
- The Hospitals/Residents Problem with Lower Quotas (2014) (47)
- Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs (2000) (47)
- Online independent sets (2000) (44)
- A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties (2010) (39)
- Complexity of Finding Short Resolution Proofs (1997) (39)
- ASPACE(o(log log n)) is Regular (1993) (36)
- The Hospitals/Residents Problem with Quota Lower Bounds (2011) (36)
- Enumeration of isolated cliques and pseudo-cliques (2009) (36)
- Linear-Time Enumeration of Isolated Cliques (2005) (34)
- Approximation algorithms for the sex-equal stable marriage problem (2007) (34)
- Average-case competitive analyses for one-way trading (2008) (30)
- Optimal Resource Augmentations for Online Knapsack (2007) (30)
- Improved approximation bounds for the Student-Project Allocation problem with preferences over projects (2011) (30)
- Improved Approximation of the Stable Marriage Problem (2003) (29)
- A (2-c(log N/N))-Approximation Algorithm for the Stable Marriage Problem (2004) (28)
- A (2-c*(1/sqrt(N)))-Approximation Algorithm for the Stable Marriage Problem (2005) (27)
- Worst-Case Upper Bounds for kSAT (Column: Algorithmics) (2004) (27)
- Harmonic algorithm for 3-dimensional strip packing problem (2007) (26)
- Random Generation of Test Instances for Logic Optimizers (1994) (26)
- Online Removable Square Packing (2005) (26)
- A family of NFAs which need 2n- deterministic states (2003) (25)
- Improved Randomized Algorithms for 3-SAT (2010) (25)
- Online knapsack with resource augmentation (2010) (24)
- Database Queries as Combinatorial Optimization Problems (1996) (24)
- Single backup table schemes for shortest-path routing (2005) (22)
- Strip Packing vs. Bin Packing (2006) (22)
- An improved approximation lower bound for finding almost stable maximum matchings (2009) (21)
- Improved algorithms for quantum identification of Boolean oracles (2006) (21)
- Routing Problems on the Mesh of Buses (1992) (20)
- Unbounded-Error One-Way Classical and Quantum Communication Complexity (2007) (20)
- A ( $2-c\frac{1}{\sqrt{N}}$ )-Approximation Algorithm for the Stable Marriage Problem (2008) (20)
- Stable Marriage with Ties and Incomplete Lists (2008) (19)
- Quantum Network Coding for General Graphs (2006) (18)
- A Harmonic Algorithm for the 3D Strip Packing Problem (2013) (17)
- Polynomial-Time Computable Backup Tables for Shortest-Path Routing (2003) (17)
- Inapproximability Results on Stable Marriage Problems (2002) (17)
- Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle (1999) (17)
- A Simpler Parallel Algorithm for Graph Conectivity (1994) (17)
- Quantum counterfeit coin problems (2010) (16)
- Approximating vertex cover on dense graphs (2005) (16)
- Reconstructing Strings from Substrings with Quantum Queries (2012) (14)
- Avoiding Routing Loops on the Internet (2003) (14)
- Exponential Lower Bounds for the Tree-Like Hajós Calculus (1995) (13)
- Random benchmark circuits with controlled attributes (1997) (12)
- Efficient parallel and distributed topological sort algorithms (1997) (11)
- Unique decomposability of shuffled strings: A formal treatment of asynchronous time-multiplexed communication (1983) (11)
- New Bounds for Oblivious Mesh Routing (1998) (11)
- Averaging Techniques for Competitive Auctions (2010) (10)
- A Faster Parallel Algorithm for k-Connectivity (1997) (10)
- The orthogonal CNN problem (2004) (10)
- An O( N ) oblivious routing algorithm for 2-D meshes of constant queue-size (1999) (10)
- Parameterized Testability (2017) (9)
- A (2 - clog N/N)-Approximation Algorithm for the Stable Marriage Problem (2006) (9)
- Complementary Approaches to CNF Boolean Equations (1987) (9)
- A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties (2015) (9)
- 08431 Open Problems - Moderately Exponential Time Algorithms (2008) (9)
- Finite-State Online Algorithms and Their Automated Competitive Analysis (2006) (9)
- Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size (2009) (9)
- Transformation rules for CNOT-based quantum circuits and their applications (2003) (8)
- A randomized algorithm for two servers in cross polytope spaces (2007) (8)
- Random Generation of Satisfiable and Unsatisfiable CNF Predicates (1992) (8)
- Quantum Query Complexity of Boolean Functions with Small On-Sets (2008) (8)
- A (2.954 + ε)n oblivious routing algorithm on 2D meshes (2000) (8)
- Density condensation of Boolean formulas (2003) (8)
- Parallel complexity hierarchies based on PRAMs and DLOGTLME-uniform circuits (1996) (8)
- Theory of Quantum Computation, Communication, and Cryptography, Third Workshop, TQC 2008, Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers (2008) (7)
- Quantum Queries on Permutations with a Promise (2009) (7)
- The Axis-bound CNN Problem (2004) (7)
- Using Generalized Forecasts for Online Currency Conversion (1999) (7)
- Improved Average Complexity for Comparison-Based Sorting (2017) (7)
- The universe problem for unrestricted flow languages (1983) (7)
- An O(log n) Parallel Connectivity Algorithm on the Mesh of Buses (1989) (7)
- General Bounds for Quantum Biased Oracles (2005) (7)
- A Family of NFA's Which Need 2n -alpha Deterministic States (2000) (6)
- Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms (2018) (6)
- Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 9135 (2015) (6)
- Finding Dense Subgraphs (1995) (6)
- Compact routing with stretch factor of less than three (brief announcement) (2000) (6)
- Parallelizing local search for CNF satisfiability using vectorization and PVM (2000) (6)
- 08431 Abstracts Collection - Moderately Exponential Time Algorithms (2008) (6)
- Stable Matching Problems (2006) (6)
- Three-Dimensional Meshes are Less Powerful than Two-Dimensional Ones in Oblivious Routing (1997) (6)
- Quantum lower bounds for the Goldreich-Levin problem (2006) (5)
- Negation-Limited Complexity of Parity and Inverters (2006) (5)
- Inclusion-exclusion for k-CNF formulas (2003) (5)
- Compact Routing with Stretch Factor of Less Than Three (2005) (5)
- Compact Routing for Flat Networks (2003) (5)
- Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists (2013) (5)
- Polynomial-Time Construction of Linear Network Coding (2008) (5)
- The complexity of the Hajós calculus for planar graphs (2010) (5)
- Oblivious routing algorithms on the mesh of buses (1997) (5)
- Recent developments in mesh routing algorithms (2000) (4)
- Unbounded-Error Classical and Quantum Communication Complexity (2007) (4)
- A (2-c(logN)/N)-Approximation Algorithm for the Stable Marriage Problem( Invited Papers from New Horizons in Computing) (2006) (4)
- Optimizing OBDDs Is Still Intractable for Monotone Functions (1998) (4)
- Stable Nash Equilibria in the Gale-Shapley Matching Game (2015) (4)
- Properties of Symmetric Incentive Compatible Auctions (2007) (4)
- A parallel algorithm for k-minimum spanning trees (1997) (4)
- Approximate strip packing: Revisited (2016) (4)
- Online chasing problems for regular polygons (2008) (4)
- Approximated Two Choices in Randomized Load Balancing (2004) (4)
- An Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size (2001) (3)
- Exploiting partial knowledge of satisfying assignments (2001) (3)
- Randomized Competitive Analysis for Two-Server Problems (2008) (3)
- Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs (2011) (3)
- Parameterized testability (2014) (3)
- A complete set of transformation rules for quantum Boolean circuits with CNOT gates (2002) (3)
- On equations including string variables (1982) (3)
- A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes (2001) (3)
- Local Search Algorithms for kSAT (2008) (3)
- On Two Dimensional Orthogonal Knapsack Problem (2008) (3)
- Improved Time and Space Hierarchies of One-Tape Off-Line TMs (1998) (3)
- alpha-Connectivity: A Gradually Nonparallel Graph Problem (1996) (3)
- Approximated Vertex Cover for Graphs with Perfect Matchings (2004) (2)
- Time Lower Bounds do not Exist for CRCW PRAMs (1996) (2)
- Satisfiability of 3CNF formulas with small clause/variable-ratio (1996) (2)
- Automata, Languages, and Programming (2015) (2)
- Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations (2002) (2)
- Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity (1994) (2)
- Quantum Evaluation of Multi-Valued Boolean Functions (2003) (2)
- The Delayed k-Server Problem (2005) (2)
- Compact routing for average-case networks (2002) (2)
- The Train Delivery Problem Revisited (2013) (2)
- Flow Time Minimization under Energy Constraints (2007) (2)
- The Hospitals / Residents Problem ( 1962 ; Gale , Shapley ) (2007) (2)
- A (2-c-)-Approximation Algorithm for the Stable Marriage Problem (2006) (2)
- Reputation games for undirected graphs (2012) (2)
- Proceedings of the Third International Symposium on Algorithms and Computation (1992) (1)
- The Locker Problem with Empty Lockers (2009) (1)
- Quantum Biased Oracles (2005) (1)
- Hierarchical path QoS on a QoS-based multicast protocol SRSVP (2002) (1)
- Query Complexity of Quantum Biased Oracles (2006) (1)
- Enumeration of Tsume-Shogi Diagrams by the Reverse Method (2008) (1)
- Guest Editorial: Special Issue on Matching Under Preferences (2010) (1)
- Better Approximations of Non-Hamiltonian Graphs (1998) (1)
- Axis-bound CNN Problem (Mathematical Optimization Theory and its Algorithm) (2001) (1)
- Randomized Competitive Analysis for Two Server Problems (2008) (1)
- Quantum Sampling for Balanced Allocations (2003) (1)
- Total Stability in Stable Matching Games (2016) (1)
- Reductions for monotone Boolean circuits (2006) (1)
- New Graph Calculi for Planar Non-3-Colorable Graphs (2008) (1)
- Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing (1999) (1)
- Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs (2004) (1)
- Partially Autonomous Automata, Two-Input/Output-Pair Automata and Their Application to the LABOLINK Network Development (1980) (1)
- Efficient randomized routing algorithms on the two-dimensional mesh of buses (1998) (1)
- Separating Oblivious and Non-oblivious BPs (2001) (1)
- A new quantum claw-finding algorithm for three functions (2003) (1)
- Collection Moderately Exponential Time Algorithms Dagstuhl Seminar (2008) (1)
- A harmonic algorithm for the 3 D strip packing problem (2013) (1)
- Tight Competitive Analyses of Online Car-Sharing Problems (2021) (1)
- Read-Once Branching Programs for Tree Evaluation Problems (2018) (1)
- Editors' Introduction to Special Section on Discrete Algorithms and Complexity (1991) (1)
- Classic and quantum network coding (2005) (1)
- Parameterized Complexity and the Understanding, Design, and Analysis of Heuristics (NII Shonan Meeting 2013-2) (2013) (1)
- Quantum Query Complexity of Almost All Functions with Fixed On-set Size (2016) (1)
- Drawing Borders Efficiently (2007) (1)
- 08431 Executive Summary - Moderately Exponential Time Algorithms (2008) (0)
- Correction: Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts. Algorithms 2014, 7, 166-185 (2014) (0)
- An Improvement of the Soundness of a 3-bit PCP (Theoretical Computer Science and Its Applications) (2009) (0)
- Noise-Tolerant Quantum Oracles (New Aspects of Theoretical Computer Science) (2003) (0)
- Recovering Strings in Oracles: Quantum and Classic (2012) (0)
- Exponential Speedup by Vector Operations (1987) (0)
- FOREWORD(Special Section on Discrete Mathematics and Its Applications) (1996) (0)
- Title A ( 2-c log N / N )-Approximation Algorithm for the StableMarriage Problem (2020) (0)
- Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications) (2005) (0)
- A pr 2 00 3 Quantum Evaluation of Multi-Valued Boolean Functions (2008) (0)
- A Canonical Form of Vector Machines (1998) (0)
- Automated Competitive Analysis of Online Problems (Evolutionary Advancement in Fundamental Theories of Computer Science) (2004) (0)
- Towards an Optimal Oblivious Routing Algorithm on 2D Meshes (Algorithm Engineering as a New Paradigm) (2001) (0)
- Book Introduction by the Authors (2014) (0)
- Online bin packing with (1,1) and (2,$$R$$R) bins (2013) (0)
- Finding Witnesses for Stability in the Hospitals/Residents Problem (2015) (0)
- Title The Hospitals/Residents Problem with Lower Quotas (2018) (0)
- Online Chasing Problems for Regular n-Gons (2007) (0)
- Low-Level Tradeoffs between Reversals and Alternations (1993) (0)
- Computing and Combinatorics (2001) (0)
- Algorithmics ofMatching Under Preferences∗ (2014) (0)
- Generating Random Benchmark Circuits with Restricted Fan-Ins (Special Issue on Synthesis and Verification of Hardware Design) (1997) (0)
- Improving the Bounds of the Online Dynamic Power Management Problem (2022) (0)
- Rs-vector algorithms for combinational problems (1993) (0)
- Approximating Vertex Cover on Dense Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science) (2004) (0)
- LA-3 Minimum Fragments for Deciding Probe Sequences for DNA Strands (2002) (0)
- DS-1-4 Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus (2010) (0)
- DS-1-2 Packing Squares with Profits into a Rectangle (2006) (0)
- Condensation of Boolean Formulas (2003) (0)
- QUANTUM QUERY COMPLEXITIES (2005) (0)
- Exact Algorithms for k SAT Based on Local Search (2016) (0)
- Random Benchmarks for Evaluating Logic Optimizers (1995) (0)
- Approximation of coNP Sets by NP-complete Sets (1995) (0)
- Efficient Methods for Determining DNA Probe Orders (2006) (0)
- Max-Stretch Reduction for Tree Spanners (2005) (0)
- Random Generation of Test Instances for Evaluating Logic Optimizers (1993) (0)
- Low-Level Tradeoffs between Cross And Alternation(Algorithms : Mathematical Foundations and Applications) (1986) (0)
- Title Improved Approximation Bounds for the Student-ProjectAllocation Problem with Preferences over Projects (2019) (0)
- Imperfectness of Data for STS-Based Physical Mapping (2004) (0)
- LETTER TO THE EDITOR (2011) (0)
- DS-1-3 1.8-Approximation Algorithm for the Stable Marriage Problem (2007) (0)
- On the NP-Completeness of weakly stable marriage (1998) (0)
- Unsatisfiable 3SAT Formulas With Each Literal Appearing Twice (1995) (0)
- Stateless Auto-configuration of IPv6 Site-local Addresses (2002) (0)
- Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs (2007) (0)
- PDCAT 2014 Organizing Committee (2014) (0)
- New Upper Bounds on The Approximability of 3D Strip Packing (2006) (0)
- Approximation of coNP sets by NP-complete sets and its applications (1999) (0)
- A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties (2012) (0)
- Letter to the Editor (2004) (0)
- Randomized Scheduling for the Online Car-sharing Problem (2021) (0)
- Efficient Transmission of Information on the Quantum Network(New Trends in Theory of Computation and Algorithm) (2006) (0)
- The Hospitals/Residents Problem with Lower Quotas (2014) (0)
- The Principle of the Right to Life According to Need: Fifty Years after the Asahi Suit (2008) (0)
- Fast Oblivious Routing Algorithms on Meshes (2000) (0)
- On the Complexity of Subproblems of SAT (New Developments of Theory of Computation and Algorithms) (2001) (0)
- Some Extensions of Preference Lists (2019) (0)
- Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits (2000) (0)
- Letter to the Editor (2002) (0)
- Title An improved approximation lower bound for finding almoststable maximum matchings (2018) (0)
- Call for papers (1985) (0)
- Inapproximability of Stable Marriage Problems (2001) (0)
- 1-E-2 Online Chasing Problems for Regular n-Gons (2007) (0)
- Towards an Optimal Oblivious Routing Algorithm on $2\mathrm{D}$ Meshes (2008) (0)
- THOUGHT AND SOCIETY IN THE MING PERIOD (1985) (0)
- Small Complexity Gaps for Comparison-Based Sorting (2018) (0)
- Algorithms and Computation (1992) (0)
- SAT, UNSAT and Coloring (2008) (0)
- Demonstrating Programs against Adversaries (1995) (0)
- NII Shonan Meeting on: Parameterized Complexity and the Understanding, Design and Analysis of Heuristics (2013) (0)
- A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs (1999) (0)
- Improved Upper and Lower Bounds of the Size of Tree-Like Resolution for the Pigeonhole Principle (Algorithm Engineering as a New Paradigm) (1999) (0)
- Approximability of Stable Matching Problems (2012) (0)
- A (2.954 epsilon)n oblivious routing algorithm on 2D meshes. (2000) (0)
- Letter from the Editor (2003) (0)
- The Planar Hajós Calculus for Bounded Degree Graphs (2010) (0)
- Haj\'os Calculus on Planar Graphs (2005) (0)
- Letter to the Editor (2013) (0)
- Brief Announcement: Compact Routing for Average-Case Networks (2000) (0)
- Oblivious Routing on the Three Dimensional Mesh Computers (1997) (0)
- A Rich Hierarchy on the Time Complexity of Uniform PRAMs (1988) (0)
- DS-1-11 Reconstructing Strings from Substrings with Quantum Query (2011) (0)
- On the size of the tree-like resolution for the pigeonhole principle (1999) (0)
- Letter from the Bulletin Editor (2014) (0)
- Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications) (2005) (0)
This paper list is powered by the following services:
Other Resources About Kazuo Iwama
What Schools Are Affiliated With Kazuo Iwama ?
Kazuo Iwama is affiliated with the following schools:
