Basic Information

Faculty

• 工学部 情報学科

Academic Degree

• (Stanford University)
• (Stanford University)

Academic Resume (Graduate Schools)

• Stanford University, Operations　Research, 修了

Language of Instruction

• Japanese
• English
• French

ID,URL

• J-Global ID

  201401047671015970

Website(s) (URL(s))

• http://www.i.kyoto-u.ac.jp/~avis/

researchmap URL

• https://researchmap.jp/7000008853

Research

Research Topics, Overview of the research

• Research Topics

  Geometric computation, discrete optimization, and quantum information.

• Overview of the research

  Geometric structures, especially high dimensional polyhedra, have become essential components of models in many areas of engineering and science. Applications arise in such diverse areas as bio-mechanics, chemistry, embedded systems, game theory, physics, robotics, scheduling and wireless networks. They are also at the heart of discrete optimization, particularly linear and integer programming. Related computational problems are computationally hard, and many important practical problems are currently out of reach with present technology. Our goal is to create new theoretical methods for geometric computation and to implement them in efficient, easily usable software for end-users.

Papers

• Reputation games for undirected graphs

  David Avis; Kazuo Iwama; Daichi Paku

  DISCRETE APPLIED MATHEMATICS, Mar. 2014, Peer-reviewed

  
• Ground Metric Learning

  Marco Cuturi; Davis Avis

  JOURNAL OF MACHINE LEARNING RESEARCH, Feb. 2014, Peer-reviewed

  
• On the extension complexity of combinatorial polytopes

  D. Avis; H.R. Tiwary

  Mathematical Programming, 2014, Peer-reviewed

  
• Families of polytopal digraphs that do not satisfy the shelling property

  David Avis; Hiroyuki Miyata; Sonoko Moriyama

  COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, Apr. 2013, Peer-reviewed

  
• A portable parallel implementation of the lrs vertex enumeration code

  David Avis; Gary Roumanis

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed

  
• On the extension complexity of combinatorial polytopes

  D. Avis; H.R. Tiwary

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed

  
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes

  Yoshikazu Aoshima; David Avis; Theresa Deering; Yoshitake Matsumoto; Sonoko Moriyama

  DISCRETE APPLIED MATHEMATICS, Oct. 2012, Peer-reviewed

  
• Verifying Nash equilibria in PageRank games on undirected web graphs

  D. Avis; K. Iwama; D. Paku

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, Peer-reviewed

  
• Leggett-Garg inequalities and the geometry of the cut polytope

  David Avis; Patrick Hayden; Mark M. Wilde

  PHYSICAL REVIEW A, Sep. 2010, Peer-reviewed

  
• Enumeration of Nash equilibria for two-player games

  David Avis; Gabriel D. Rosenberg; Rahul Savani; Bernhard von Stengel

  ECONOMIC THEORY, Jan. 2010, Peer-reviewed

  
• From Bell Inequalities to Tsirelson's Theorem

  David Avis; Sonoko Moriyama; Masaki Owari

  IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, May 2009, Peer-reviewed

  
• Enumeration of optimal pin-jointed bistable compliant mechanisms with non-crossing members

  M. Ohsaki; N. Katoh; T. Kinoshita; S. Tanigawa; D. Avis; I. Streinu

  STRUCTURAL AND MULTIDISCIPLINARY OPTIMIZATION, Feb. 2009, Peer-reviewed

  Access this paper :

  
• The locker problem with empty lockers

  D. Avis; L. Devroye; K. Iwama

  World Academy of Science, Engineering and Technology, 2009, Peer-reviewed

  
• Computing monotone disjoint paths on polytopes

  David Avis; Bohdan Kaluzny

  JOURNAL OF COMBINATORIAL OPTIMIZATION, Nov. 2008, Peer-reviewed

  
• Enumerating constrained non-crossing minimally rigid frameworks

  David Avis; Naoki Katoh; Makoto Ohsaki; Ileana Streinu; Shin-ichi Tanigawa

  DISCRETE & COMPUTATIONAL GEOMETRY, Jul. 2008, Peer-reviewed

  Access this paper :

  
• Generating facets for the cut polytope of a graph by triangular elimination

  David Avis; Hiroshi Imai; Tsuyoshi Ito

  MATHEMATICAL PROGRAMMING, Apr. 2008, Peer-reviewed

  
• Visualizing and constructing cycles in the simplex method

  David Avis; Bohdan Kaluzny; David Titley-Peloquin

  OPERATIONS RESEARCH, Mar. 2008, Peer-reviewed

  
• Distributed compression and multiparty squashed entanglement

  David Avis; Patrick Hayden; Ivan Savov

  JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, Mar. 2008, Peer-reviewed

  
• New classes of facets of the cut polytope and tightness of Imm22 Bell inequalities

  David Avis; Tsuyoshi Ito

  DISCRETE APPLIED MATHEMATICS, Aug. 2007, Peer-reviewed

  
• A list heuristic for vertex cover

  David Avis; Tomokazu Imamura

  OPERATIONS RESEARCH LETTERS, Mar. 2007, Peer-reviewed

  
• Enumerating non-crossing minimally rigid frameworks

  David Avis; Naoki Katoh; Makoto Ohsaki; Ileana Streinu; Shin-ichi Tanigawa

  GRAPHS AND COMBINATORICS, 2007, Peer-reviewed

  Access this paper :

  
• Vasek Chvatal: A very short introduction

  David Avis; Adrian Bondy; William Cook; Bruce Reed

  GRAPHS AND COMBINATORICS, 2007, Peer-reviewed

  
• Graphs and Combinatorics: Preface

  D. Avis

  Graphs and Combinatorics, 2007, Peer-reviewed

  
• On the relationship between convex bodies related to correlation experiments with dichotomic observables

  David Avis; Hiroshi Imai; Tsuyoshi Ito

  JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, Sep. 2006, Peer-reviewed

  
• A quantum protocol to win the graph colouring game on all hadamard graphs

  David Avis; Jun Hasegawa; Yosuke Kikuchi; Yuuya Sasaki

  IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, May 2006, Peer-reviewed

  
• Bell inequalities stronger than the Clauser-Horne-Shimony-Holt inequality for three-level isotropic states

  T Ito; H Imai; D Avis

  PHYSICAL REVIEW A, Apr. 2006, Peer-reviewed

  
• Enumerating non-crossing minimally rigid frameworks

  D. Avis; N. Katoh; M. Ohsaki; I. Streinu; S.-I. Tanigawa

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2006, Peer-reviewed

  
• Un des "problèmes plaisans et délectables" de Claude Berge

  D. Avis; A. Deza

  Discrete Mathematics, 2006, Peer-reviewed

  
• Two-party Bell inequalities derived from combinatorics via triangular elimination

  David Avis; Hiroshi Imai; Tsuyoshi Ito; Yuuya Sasaki

  JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, Dec. 2005, Peer-reviewed

  
• On the fractional chromatic index of a graph and its complement

  D Avis; C De Simone; B Reed

  OPERATIONS RESEARCH LETTERS, Jul. 2005, Peer-reviewed

  
• Graph theory and combinatorial optimization

  D. Avis; A. Hertz; O. Marcotte

  Graph Theory and Combinatorial Optimization, 2005, Peer-reviewed

  
• Preface

  D. Avis; A. Hertz; O. Marcotte

  Graph Theory and Combinatorial Optimization, 2005, Peer-reviewed

  
• Solving inequalities and proving Farkas's lemma made easy

  D Avis; B Kaluzny

  AMERICAN MATHEMATICAL MONTHLY, Feb. 2004, Peer-reviewed

  
• Stronger linear programming relaxations of max-cut

  D Avis; J Umemoto

  MATHEMATICAL PROGRAMMING, Aug. 2003, Peer-reviewed

  
• On the chromatic polynomial of a graph

  D Avis; C De Simone; P Nobili

  MATHEMATICAL PROGRAMMING, May 2002, Peer-reviewed

  
• On the binary solitaire cone

  D Avis; A Deza

  DISCRETE APPLIED MATHEMATICS, Nov. 2001, Peer-reviewed

  
• On the existence of a point subset with a specified number of interior points

  D Avis; K Hosono; M Urabe

  DISCRETE MATHEMATICS, Oct. 2001, Peer-reviewed

  
• On the solitaire cone and its relationship to multi-commodity flows

  D Avis; A Deza

  MATHEMATICAL PROGRAMMING, Mar. 2001, Peer-reviewed

  
• Automated 3-D extraction of inner and outer surfaces of cerebral cortex from MRI

  D MacDonald; N Kabani; D Avis; AC Evans

  NEUROIMAGE, Sep. 2000, Peer-reviewed

  
• A combinatorial approach to the solitaire game

  D Avis; A Deza; S Onn

  IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, Apr. 2000, Peer-reviewed

  
• Estimating the number of vertices of a polyhedron

  D Avis; L Devroye

  INFORMATION PROCESSING LETTERS, Feb. 2000, Peer-reviewed

  
• Two conjectures on the chromatic polynomial

  D. Avis; C. De Simone; P. Nobili

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2000, Peer-reviewed

  
• Computational experience with the reverse search vertex enumeration algorithm

  D Avis

  OPTIMIZATION METHODS & SOFTWARE, 1998, Peer-reviewed

  
• Automatic segmentation of cortical surfaces from MRI with partial-volume correction

  D. MacDonald; D. Avis; A.C. Evans

  NeuroImage, 1998, Peer-reviewed

  
• Unoriented Theta-maxima in the plane: Complexity and algorithms

  D Avis; B Beresford-Smith; L Devroye; H Elgindy; E Guevremont; F Hurtado; BH Zhu

  SIAM JOURNAL ON COMPUTING, 1998, Peer-reviewed

  
• How good are convex hull algorithms?

  D Avis; D Bremner; R Seidel

  COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, Apr. 1997, Peer-reviewed

  
• A surface-based 2-D sulcal atlas

  D. MacDonald; R. Venugopal; Z. Caramanos; M. Petrides; D. Avis; A.C. Evans

  NeuroImage, 1997, Peer-reviewed

  
• Generating rooted triangulations without repetitions

  D Avis

  ALGORITHMICA, Dec. 1996, Peer-reviewed

  
• Reverse search for enumeration

  D Avis; K Fukuda

  DISCRETE APPLIED MATHEMATICS, Mar. 1996, Peer-reviewed

  
• Large convex hull problems

  D Avis; D Bremner

  ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1996, Peer-reviewed

  
• METRIC EXTENSIONS AND THE L(1) HIERARCHY

  D AVIS; H MACHARA

  DISCRETE MATHEMATICS, Aug. 1994, Peer-reviewed

  
• GROUND-STATES OF A TERNARY FCC LATTICE MODEL WITH NEAREST-NEIGHBOR AND NEXT-NEAREST-NEIGHBOR INTERACTIONS

  G CEDER; GD GARBULSKY; D AVIS; K FUKUDA

  PHYSICAL REVIEW B, Jan. 1994, Peer-reviewed

  
• THE M-CORE PROPERLY CONTAINS THE M-DIVISIBLE POINTS IN-SPACE

  D AVIS

  PATTERN RECOGNITION LETTERS, Sep. 1993, Peer-reviewed

  
• A bound on the k-gonality of facets of the hypermetric cone and related complexity problems

  D. Avis; V.P. Grishukhin

  Computational Geometry: Theory and Applications, 1993, Peer-reviewed

  
• Guest editor\\'s foreword

  D. Avis

  Discrete & Computational Geometry, 1993, Peer-reviewed

  
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

  D. Avis; K. Fukuda

  Discrete & Computational Geometry, 1992, Peer-reviewed

  
• Distinct distances determined by subsets of a point set in space

  D. Avis; P. Erdo; s; J. Pach

  Computational Geometry: Theory and Applications, 1991, Peer-reviewed

  
• A BASIS ENUMERATION ALGORITHM FOR LINEAR-SYSTEMS WITH GEOMETRIC APPLICATIONS

  D AVIS; K FUKUDA

  APPLIED MATHEMATICS LETTERS, 1991, Peer-reviewed

  
• ALGORITHMS FOR HIGH DIMENSIONAL STABBING PROBLEMS

  D AVIS; M DOSKAS

  DISCRETE APPLIED MATHEMATICS, May 1990, Peer-reviewed

  
• LOWER BOUNDS FOR LINE STABBING

  D AVIS; JM ROBERT; R WENGER

  INFORMATION PROCESSING LETTERS, Nov. 1989, Peer-reviewed

  
• ON THE COMPLEXITY OF SINGLE FAULT SET DIAGNOSABILITY AND DIAGNOSIS PROBLEMS

  AK SOMANI; VK AGARWAL; D AVIS

  IEEE TRANSACTIONS ON COMPUTERS, Feb. 1989, Peer-reviewed

  
• Computing the volume of the union of spheres

  David Avis; Binay K. Bhattacharya; Hiroshi Imai

  The Visual Computer, Nov. 1988, Peer-reviewed

  
• THE PROBABILISTIC ANALYSIS OF A HEURISTIC FOR THE ASSIGNMENT PROBLEM

  D AVIS; CW LAI

  SIAM JOURNAL ON COMPUTING, Aug. 1988, Peer-reviewed

  
• Repeated distances in space

  D. Avis; P. Erdös; J. Pach

  Graphs and Combinatorics, 1988, Peer-reviewed

  
• Polyhedral line transversals in space

  D. Avis; R. Wenger

  Discrete & Computational Geometry, 1988, Peer-reviewed

  
• Triangulating point sets in space

  D. Avis; H. ElGindy

  Discrete & Computational Geometry, 1987, Peer-reviewed

  
• Diameter partitioning

  D. Avis

  Discrete & Computational Geometry, 1986, Peer-reviewed

  
• Visibility between two edges of a simple polygon

  D. Avis; T. Gum; G. Toussaint

  The Visual Computer, 1986, Peer-reviewed

  
• GENERALIZED THEORY FOR SYSTEM LEVEL DIAGNOSIS.

  Arun K. Somani; Vinod K. Agarwal; David Avis

  1985, Peer-reviewed

  
• SPACE PARTITIONING AND ITS APPLICATION TO GENERALIZED RETRIEVAL PROBLEMS.

  David Avis

  1985, Peer-reviewed

  
• ECCENTRIC GRAPHS

  J AKIYAMA; K ANDO; D AVIS

  DISCRETE MATHEMATICS, 1985, Peer-reviewed

  
• AN ANALYSIS OF A DECOMPOSITION HEURISTIC FOR THE ASSIGNMENT PROBLEM

  D AVIS; L DEVROYE

  OPERATIONS RESEARCH LETTERS, 1985, Peer-reviewed

  
• Miscellaneous Properties Of Equi-Eccentric Graphs

  Jin Akiyama; Kiyoshi Ando; David Avis

  North-Holland Mathematics Studies, 1984, Peer-reviewed

  
• NON-PARTITIONABLE POINT SETS

  D AVIS

  INFORMATION PROCESSING LETTERS, 1984, Peer-reviewed

  
• A COMBINATORIAL APPROACH TO POLYGON SIMILARITY

  D AVIS; H ELGINDY

  IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, Peer-reviewed

  
• APPLICATIONS OF A TWO-DIMENSIONAL HIDDEN-LINE ALGORITHM TO OTHER GEOMETRIC PROBLEMS

  H ELGINDY; D AVIS; G TOUSSAINT

  COMPUTING, 1983, Peer-reviewed

  
• A SURVEY OF HEURISTICS FOR THE WEIGHTED MATCHING PROBLEM

  D AVIS

  NETWORKS, 1983, Peer-reviewed

  
• ON THE MULTIMODALITY OF DISTANCES IN CONVEX POLYGONS

  D AVIS; GT TOUSSAINT; BK BHATTACHARYA

  COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1982, Peer-reviewed

  
• ON THE COMPLEXITY OF FINDING THE CONVEX-HULL OF A SET OF POINTS

  D AVIS

  DISCRETE APPLIED MATHEMATICS, 1982, Peer-reviewed

  
• ON A CONVEX-HULL ALGORITHM FOR POLYGONS AND ITS APPLICATION TO TRIANGULATION PROBLEMS

  GT TOUSSAINT; D AVIS

  PATTERN RECOGNITION, 1982, Peer-reviewed

  
• AN OPTIMAL ALGORITHM FOR DETERMINING THE VISIBILITY OF A POLYGON FROM AN EDGE

  D AVIS; GT TOUSSAINT

  IEEE TRANSACTIONS ON COMPUTERS, 1981, Peer-reviewed

  
• WORST CASE BOUNDS FOR THE EUCLIDEAN MATCHING PROBLEM

  D AVIS

  COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1981, Peer-reviewed

  
• AN EFFICIENT ALGORITHM FOR DECOMPOSING A POLYGON INTO STAR-SHAPED POLYGONS

  D AVIS; GT TOUSSAINT

  PATTERN RECOGNITION, 1981, Peer-reviewed

  
• BALANCING SIGNED GRAPHS

  J AKIYAMA; D AVIS; CHVATAL, V; H ERA

  DISCRETE APPLIED MATHEMATICS, 1981, Peer-reviewed

  
• A LINEAR ALGORITHM FOR COMPUTING THE VISIBILITY POLYGON FROM A POINT

  H ELGINDY; D AVIS

  JOURNAL OF ALGORITHMS, 1981, Peer-reviewed

  
• Extremal Metrics Induced by Graphs

  D. Avis

  Annals of Discrete Mathematics, 1980, Peer-reviewed

  
• A note on some computationally difficult set covering problems

  D. Avis

  Mathematical Programming, 1980, Peer-reviewed

  
• A linear algorithm for finding the convex hull of a simple polygon

  D. McCallum; D. Avis

  Information Processing Letters, 1979, Peer-reviewed

  

Misc.

• Those ubiquitous cut polyhedra

  D. Avis

  Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010, 2010, Peer-reviewed

  
• Preface: ICQNM 2010

  D. Avis; C. Kollmitzer; V. Ovchinnikov; B. Parke; V. Privman; P. Dini

  4th International Conference on Quantum, Nano and Micro Technologies, ICQNM 2010, 2010, Peer-reviewed

  
• Single, complete, probability spaces consistent with EPR-Bohm-Bell experimental data

  D. Avis; P. Fischer; A. Hilberf; A. Khrennikov

  AIP Conference Proceedings, 2009, Peer-reviewed

  
• Proceedings of the 3rd International Conference on Quantum, Nano and Micro Technologies, ICQNM 2009: Preface

  D. Avis; P. Dini; T. Tanamoto; S. Dan Cotofana; C. Kollmitzer; V. Privman

  Proceedings of the 3rd International Conference on Quantum, Nano and Micro Technologies, ICQNM 2009, 2009, Peer-reviewed

  
• The quantum locker puzzle

  D. Avis; A. Broadbent

  Proceedings of the 3rd International Conference on Quantum, Nano and Micro Technologies, ICQNM 2009, 2009, Peer-reviewed

  
• Proceedings - The 2nd International Conference on Quantum-, Nano- and Micro-Technologies ICQNM: Preface

  David Avis; Alexander Sergienko; Nicolas Chaillet; Toshio Fukuda; Constantinos Mavroidis; Masahito Hayashi; Christian Kollmitzer; Victor Ovchinnikov

  Proceedings - The 2nd International Conference on Quantum-, Nano- and Micro-technologies, ICQNM 2008, 2008, Peer-reviewed

  
• Multiparty distributed compression of quantum information

  D. Avis; P. Hayden; I. Savov

  Proceedings - The 2nd International Conference on Quantum-, Nano- and Micro-technologies, ICQNM 2008, 2008, Peer-reviewed

  
• Comparison of two bounds of the quantum correlation set

  David Avis; Tsuyoshi Ito

  First International Conference on Quantum, Nano, and Micro Technologies, ICQNM 2007, 2007, Peer-reviewed

  
• On the sectional area of convex polytopes

  David Avis; Prosenjit Bose; Thomas C. Shermer; Jack Snoeyink; Godfried Toussaint; Binhai Zhu

  Proceedings of the Annual Symposium on Computational Geometry, 1996, Peer-reviewed

  
• SINGLE FAULT DIAGNOSABILITY CONCEPT: SYSTEM-LEVEL DIAGNOSIS AS APPLIED TO LARGE SCALE MULTIPROCESSOR SYSTEMS.

  Arun K. Somani; Vinod K. Agrawal; David Avis

  Proceedings - IEEE International Symposium on Circuits and Systems, 1986, Peer-reviewed

  
• ON COMPLEXITY OF DIAGNOSABILITY AND DIAGNOSIS PROBLEMS IN SYSTEM-LEVEL DIAGNOSIS.

  A. Somani; D. Avis; V. Agarwal

  Digest of Papers - FTCS (Fault-Tolerant Computing Symposium), 1986, Peer-reviewed

  
• LOWER BOUNDS FOR GEOMETRIC PROBLEMS.

  David Avis

  Proceedings - Annual Allerton Conference on Communication, Control, and Computing, Peer-reviewed

  

Books and Other Publications

• Polyhedral Computation

  D.Avis; D. Bremner; A.Deza(editor

  CRM-AMS Proceedings(2009), 150pp., 2009, Not refereed

  
• Graph Theory and Combinatorial Optimization

  D.Avis; A.Hertz; O.Marcotte(edito

  Springer (2005) 264pp, 2005, Not refereed

  
• 計算機科学・離散幾何学 Computational and Dixcrete Geometry

  D.Avis; H.Imai; S.Matsunaga

  Asukura (1994) 150pp, 1994, Not refereed

  

External funds: Kakenhi

• New computational models for algorithms and discrete optimization

  Grant-in-Aid for Transformative Research Areas (A)

  Transformative Research Areas, Section (IV)

  National Institute of Informatics

  河原林 健一

  From 19 Nov. 2020, To 31 Mar. 2025, Granted

  グラフアルゴリズム;組合せ最適化;計算量;グラフ理論;グラフ;アルゴリズム;計算理論;組合せ最適;離散最適化

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05965/
• 量子アルゴリズム・計算量・浅層回路と量子コンピュータ実機実験による量子優位性研究

  Grant-in-Aid for Scientific Research (A)

  Medium-sized Section 60:Information science, computer engineering, and related fields

  Meiji Gakuin University;The University of Tokyo

  今井 浩

  From 01 Apr. 2020, To 31 Mar. 2025, Granted

  量子コンピュータ;量子優越性;浅層量子回路;凸多面体の量子情報;量子回路設計理論;量子優位性;量子エラー緩和;Bellの不等式;量子非局所性

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20H00579/
• Large Graphs: Theory and Algorithms

  Grant-in-Aid for Scientific Research (S)

  Broad Section J

  National Institute of Informatics

  河原林 健一

  From 11 Jun. 2018, To 31 Mar. 2023, Granted

  グラフアルゴリズム;グラフ理論;グラフ;離散数学;アルゴリズム;離散最適化;組合せ最適化;分散計算;サブモジュラー関数;計算理論

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/
• Large scale parallelization for geometric computation and mathematical optimization

  Grant-in-Aid for Scientific Research (B)

  Kyoto University

  David Avis

  From 01 Apr. 2016, To 31 Mar. 2021, Project Closed

  幾何計算;大規模並列処理;数理計画法への応用;大規模並列化;計算機科学;並列計算;離散最適化;数理計画法

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16H02785/
• Approximate Computing to Cope with Imperfect Information from Growing Data Size

  Grant-in-Aid for Scientific Research (A)

  Kyoto University

  KAZUO IWAMA

  From 01 Apr. 2013, To 31 Mar. 2016, Project Closed

  アルゴリズム;計算困難問題;情報の補填;数理モデル化;理論的性能保証

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25240002/
• Geometric computational approach to solving hard optimization problems: theory and implementation

  Grant-in-Aid for Scientific Research (B)

  Kyoto University

  David Avis

  From 01 Apr. 2012, To 31 Mar. 2016, Project Closed

  計算機科学;離散幾何学;最適化;幾何計算;大規模並列化;数理計画法への応用;多面体;)離散最適化;アルゴリズム;並列処理;離散最適化

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24300002/
• Analyzing the limits of computation using large scale linear programming

  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

  Science and Engineering

  Kyoto University

  David Avis

  From 28 Jun. 2012, To 31 Mar. 2017, Project Closed

  幾何計算;最適化;数理計画法への応用;最適化数;国際研究者交流:カナダ・チェコ・米国;数理計画;線形計画;整数計画;計算限界;国際研究者交流;多面体;国際研究者交流:カナダ・ベルギー・チェコ・ドイツ;国際研究者交流（ベルギー・ドイツ）

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106006/
• A Multifaced Approach Toward Understanding the Limitations of Compuation

  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

  Science and Engineering

  Tokyo Institute of Technology

  Osamu Watanabe

  From 28 Jun. 2012, To 31 Mar. 2017, Project Closed

  計算限界解明;研究連携促進;研究拠点形成;若手研究者の育成;成果の総括;成果の波及;計算複雑さの理論;アルゴリズム理論;計算量上下界解析;成果の総括と公表;計算限界解明手法の開拓;多視点からの連携研究;国際研究者交流;各種啓発・研究成果波及;若手研究者育成;多視点からの統合的解析;計算限界研究センター;計算理論若手研究者育成;ELC 秋学校;ELC Seminar;ELC Workshop

  https://kaken.nii.ac.jp/grant/KAKENHI-ORGANIZER-24106001/
• Polyhedral computation, discrete optimization and quantum information

  Grant-in-Aid for Research Activity Start-up

  Kyoto University

  David AVIS

  From 01 Apr. 2010, To 31 Mar. 2012, Project Closed

  計算幾何学;離散幾何学;アルゴリズム理論;量子情報;多面体;離散最適化;アルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22800031/
• Studies on Algorithms for Insufficient Spatial Information

  Grant-in-Aid for Scientific Research (A)

  Kyoto University

  Kazuo IWAMA

  From 01 Apr. 2010, To 31 Mar. 2013, Project Closed

  アルゴリズム理論;グラフ問題;アルゴリズム的ゲーム理論;乱化計算;アルゴリズム;計算困難問題;情報の補填;数理モデル化;理論的性能保証;劣線形時間;乱化アルゴリズム;分散アルゴリズム;准線形時間

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22240001/
• Graph Algorithms and Optimization: Theory and Scalable Algorithms

  Grant-in-Aid for Scientific Research (S)

  Broad Section J

  National Institute of Informatics

  河原林 健一

  From 27 Apr. 2022, To 31 Mar. 2027, Granted

  離散数学;グラフアルゴリズム;グラフ構造;グラフ理論;組合せ最適化

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22H05001/
• 高性能論理ソルバと幾何計算の結合による技術発展とその応用

  Grant-in-Aid for Scientific Research (C)

  Basic Section 60050:Software-related

  Otaru University of Commerce

  ジョーダン チャールズハロルド

  From 01 Apr. 2023, To 31 Mar. 2028, Granted

  幾何計算;論理ソルバ;SMTソルバ

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23K11043/

Education

Teaching subject(s)

• From Apr. 2011, To Mar. 2012

  Introduction to Algorithms and Infomatics

  Spring, 情報学研究科
• From Apr. 2011, To Mar. 2012

  Computational Intractability:NP-completeness and Integer Programming,with Scheduling Applications

  Spring, 情報学研究科
• From Apr. 2011, To Mar. 2012

  Polyhedral Computation:Theory,Practice and Applications in Engineering and Science

  Fall, 情報学研究科
• From Apr. 2011, To Mar. 2012

  Introduction to Algorithms and informatics

  Spring, 全学共通科目
• From Apr. 2011, To Mar. 2012

  Perspective in Informatics 4B

  Fall, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Computational Intractability

  Spring, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Introduction to Algorithms and Informatics

  Spring, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Perspective in Informatics 4B

  Fall, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Polyhedral Computation

  Fall, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Introduction to algorithms and informatics

  Spring, 全学共通科目
• From Apr. 2012, To Mar. 2013

  Perspective in Informatics 4

  Spring, 情報学研究科
• From Apr. 2012, To Mar. 2013

  Perspective in Informatics 5

  Fall, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Advanced Study in Communications and Computer Engineering I

  Year-long, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Introduction to Algorithms and Informatics

  Spring, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Computational Intractability

  Spring, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Polyhedral Computation

  Fall, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Perspective in Informatics 4

  Spring, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Perspective in Informatics 5

  Fall, 情報学研究科
• From Apr. 2013, To Mar. 2014

  Fundamentals of Informatics (English)

  Spring, 全学共通科目
• From Apr. 2014, To Mar. 2015

  Advanced Study in Communications and Computer Engineering I

  Year-long, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Advanced Study in Communications and Computer Engineering II

  Year-long, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Introduction to Algorithms and Informatics

  Spring, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Computational Intractability

  Spring, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Seminar on Communications and Computer Engineering, Advanced

  Year-long, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Seminar on Computer Engineering, Advanced

  Year-long, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Perspective in Informatics 4

  Spring, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Perspective in Informatics 5

  Fall, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Fundamentals of Informatics

  Spring, 全学共通科目
• From Apr. 2014, To Mar. 2015

  Fundamentals of Informatics

  Fall, 全学共通科目
• From Apr. 2014, To Mar. 2015

  Fundamentals of Discrete Optimization

  Spring, 全学共通科目
• From Apr. 2014, To Mar. 2015

  Advanced Study in Communications and Computer Engineering I

  Year-long, 情報学研究科
• From Apr. 2014, To Mar. 2015

  Advanced Study in Communications and Computer Engineering II

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Advanced Study in Communications and Computer Engineering I

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Advanced Study in Communications and Computer Engineering II

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Computational Intractability

  Spring, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Fundamentals of Discrete Optimization

  Spring, 全学共通科目
• From Apr. 2015, To Mar. 2016

  Fundamentals of Informatics

  Spring, 全学共通科目
• From Apr. 2015, To Mar. 2016

  Fundamentals of Informatics

  Fall, 全学共通科目
• From Apr. 2015, To Mar. 2016

  Introduction to Algorithms and Informatics

  Spring, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Seminar on Computer Engineering, Advanced

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Perspective in Informatics 4

  Spring, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Perspective in Informatics 5

  Fall, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Introduction to Algorithms and Informatics

  Spring, 工学研究科
• From Apr. 2015, To Mar. 2016

  Seminar on Communications and Computer Engineering, Advanced

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Advanced Study in Communications and Computer Engineering II

  Year-long, 情報学研究科
• From Apr. 2015, To Mar. 2016

  Advanced Study in Communications and Computer Engineering I

  Year-long, 情報学研究科

Part-time lecturer

• From 1978, To 0000

  C.O.R.E
• From 1983, To 0000

  東京大学
• From 1988

  東京大学
• From 1995, To 0000

  東京大学
• From 1984

  京都大学
• From 1988

  京都大学
• From 2000

  京都大学
• From 2004, To 0000

  京都大学
• From 1988

  九州大学
• From 1990

  T.I.T
• From 1988

  E.P.F.L
• From 1998

  IASI-CNR
• From 1994

  慶応大学
• From 2000

  ERATO
• From 2006

  ERATO
• From 1990

  東京大学
• From 1996

  東京大学
• From 1997

  東京大学
• From 2005

  京都大学
• From 2006

  京都大学
• From 1999

  E.P.F.L

Administration

Faculty management (title, position)

• From 01 Apr. 2011, To 31 Mar. 2012

  G30WG委員
• From 01 Apr. 2012, To 31 Mar. 2013

  G30WG委員
• From 01 Apr. 2013, To 31 Mar. 2014

  G31WG委員