Professor David Avis                             

Department of Communications and Computer Engineering
School of Informatics
Kyoto University
Yoshida-honmachi  36-1, Sakyo-ku,  Kyoto 606-8501, Japan
TEL: 075-753-5953

Born: March 20, 1951    Citizenship:  British and Canadian     Languages: English, French, Japanese 

B. Math (1973) Waterloo
M.Sc (Statistics, 1975) and Ph.D.(Operations Research, 1977) Stanford


Graduate School of Informatics, Kyoto University: Professor (2010-present)
School of Computer Science, McGill:
Assistant Professor  (1977-1981), Associate Professor (1981-1987), Professor (1987-2014)
Professor Emeritus (2015-present)

Visiting Professor:
Tokyo (1983, 1988, 1995), Kyoto (1984, 1988, 2000, 2004, 2006),  Kyushu (1988), T.I.T. (1990), E.P.F.L. (1998).

Visiting Researcher:
C.O.R.E. (1978), IASI-CNR (1998), ERATO(2000,2006)

Courses given at:
Tokyo (1990, 1996,1997), Keio (1994), E.P.F.L. (1998, 1999), Kyoto (2000, 2005)

Research Areas:
Combinatorial Optimization, Operations Research,  Mathematical Programming, Quantum Computation

Editorial Boards:
Discrete Applied Mathematics, Discrete and Computational Geometry, Graphs and Combinatorics

Recent Papers

D. Avis and H. Tiwary, "Compact Linear Programs for 2SAT", European J. of Combinatorics (accepted,2017)    arXiv:1702.06723
D. Avis and C. Jordan, "mplrs: A Scalable Parallel Vertex/Facet enumeration Code", Math. Prog. Computation (online, 2017) arXiv:1511.06487
D. Avis and O. Friedmann, "An Exponential Lower Bound for Cunningham's Rule"Math. Prog. B 161(2017)271-305
D. Avis and H. Tiwary, "On the H-free Extension Complexity of the TSP", Optimization Letters 11(2017)445-455   arXiv:1506.08311
D. Avis and C. Meagher, "On the Directed Cut Cone and Polytope", J. Combinatorial Optimization 31(2016)1685-1708 pdf
D. Avis, "George Dantzig: father of the simplex method", Bulletin of the EATCS 116(2015)
D. Avis and H. Tiwary, "A Generalization of  Extension Complexity that Captures P", Information Proc. Letters 115 (2015) 6-8 ,  arXiv:1402.5950
D. Avis, D. Bremner, H. Tiwary and O. Watanabe, "Polynomial size linear programs for non-bipartite matching problems and other problems in P", August 2014  arXiv:1408.0807
D. Avis and H. Tiwary, “On the Extension Complexity of Combinatorial PolytopesMath. Prog. B 153(2015)95-115. (Extended abstract: ICALP 2013).
M. Cuturi and D. Avis, “Ground Metric LearningJournal of Machine Learning Research 15, pp. 533-64 (2014).
D. Avis, K. Iwama, and D. Paku, “Reputation Games for Undirected GraphsDiscrete Applied Mathematics 166, pp. 1-13 (2014).
D. Avis and G. Roumanis, "A Portable Parallel Implementation of the lrs Vertex Enumeration Code", COCOA 2013, LNCS 8287 (2013) 414-29
D. Avis, H. Miyata, and S. Moriyama, “Families of Polytopal Digraphs that do not Satisfy the Shelling Property,” Comput. Geom. 46, pp. 382-93 (2013).
D. Aoshima, D. Avis, T. Deering, Y. Matsumoto, and S. Moriyama, “On the Existence of Hamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations of HypercubesDiscrete Applied Mathematics 160, pp. 2104-15 (2012).
D. Avis, P. Hayden, and M. Wilde, “Leggett-Garg Inequalities and the Geometry of the Cut PolytopePhysical Review A 82 (2010). 030102(R).
D. Avis, S. Moriyama, and M. Owari, “From Bell Inequalities to Tsirelson’s TheoremProc. IECIE E92-A, pp. 1254-67 (2009).

Books and Special Editions:
D. Avis, D. Bremner, and A. Deza (editors), Polyhedral Computation, CRM-AMS Proceedings and Lecture Notes (2008). 150 pages.
D. Avis, A. Bondy, M. Kano, and N. Katoh (editors), Computational Geometry and Graph Theory:The Akiyama-Chvatal Festschrift, Springer (2007). Graphs and Combinatorics Supplement,379 pages.
D. Avis, A. Hertz, and O. Marcotte (editors), Graph Theory and Combinatorial Optimization, Springer (2005). 264 pages.
D. Avis, H. Imai, and S. Matsunaga, Keisankikagaku Risankagaku (Computational and Discrete Geometry), Asakura, Tokyo (September 1994). In Japanese, 150 pages.
D. Avis (editor), Selected Papers: ACM Symposium on Computational Geometry 10(2), Discrete and Computational Geometry, Berlin (1993).
D. Avis (editor), Selected Papers: 1st Canadian Conference on Computational Geometry 31(2), Discrete Applied Mathematics, Montreal (1991).
F. Hillier, O. Yu, D. Avis, L. Fosset, F. Lo, and M. Reiman, Queueing Tables and Graphs, Elselvier North-Holland (1981).