CURRICULUM VITAEDavid Avis
30 January 2018
Present Address:
Graduate School of Informatics
Kyoto University
Yoshida-honmachi 36-1, Sakyo-ku,
Kyoto 606-8501 Japan
http://i.kyoto-u.ac.jp/˜avis
075-753-5953 email: avis@i.kyoto-u.ac.jp
Date of Birth:

March 20, 1951

Citizenship:

Canadian and British

Languages:

English, French, Japanese

Education
Institution

Degree

Field

Year

Stanford University
Stanford University
University of Waterloo

Ph. D
M.S.
B. MathOperations Research
Statistics
Combinatorics and Optimization

1977
1975
1973

Academic Experience
Position

Dates

Location

Researcher
Visiting Professor
Professor Emeritus
Professor
Associate Professor
Assistant Professor

2016.4 - present
2010.1 - 2016.3
2015.1 - present
1987.6 - 2014.12
1981.6 - 1987.5
1977.9 - 1981.5

Graduate School of Informatics, Kyoto University
Graduate School of Informatics, Kyoto University
School of Computer Science, McGill University
School of Computer Science, McGill University
School of Computer Science, McGill University
School of Computer Science, McGill University

J.S.P.S. Senior Fellow
Visiting Professor
J.S.P.S. Senior Fellow
Visiting Researcher
Visiting Professor
Adjoint Professor
Visiting Researcher
Visiting Professor
Visiting Professor
Visiting Professor
Visiting Professor
J.S.P.S. Senior Fellow
C.O.R.E. Fellow

2008.12 - 2009.1
2006.1 - 2006.3
2004.12 - 2005.6
2000.12
2000.1 - 2000.8
1995.8 - 1999.7
1998.1 - 1998.4
1991.1 - 1991.4
1990.4 - 1990.8
1990.8 - 1990.12
1988.6 - 1988.7
1983.9 - 1983.12
1978.5 - 1978.7

Keio University
Kyoto University
Kyoto University
ERATO Quantum Computing Project, Tokyo
Kyoto University
University of Tokyo
IASI, CNR Rome
University of West Indies, Jamaica
Kyushu University
Tokyo Institute of Technology
University of Tokyo
University of Tokyo
C.O.R.E., Université de Louvain, Belgium

-2Research Grants (1989 - present)
Date

AgencyType$/YearCo-investigators

16-21
11-16
12-17
09-13
08-11
04-09
05-08
99-04
01-04
98-01
95-99
95-98
97-98
92-95
92-95
92
89-92
89-92
89-92

JSPS
JSPS
JSPS
NSERC
MDEIE
NSERC
FQRNT
NSERC
FCAR
FCAR
NSERC
FCAR
CRIM
NSERC
FCAR
NSERC
FCAR
NSERC
NSERC

OperatingOperatingTeam
OperatingInternational
OperatingTeam
OperatingTeam
Team
OperatingTeam
OperatingOperatingTeam
Bilateral
Team
Infrastructure
Operating

3,000,000 yen (approx.)
3,000,000 yen (approx.)
4,300,000 yen (approx.)
38,50035,00052,50070,00052,50061,00056,00047,50056,0003,750
44,00068,40010,00083,00084,00038,500

C. Jordan
Amano, Ueno
INTRIQ-ERATO/SORST collaboration

Devroye, Toussaint, Whitesides
Devroye, Toussaint, Whitesides
Devroye, Toussaint, Whitesides
El Gindy, Devroye, Toussaint, Whitesides
El Gindy, Devroye, ToussaintSchool of Computer Science-Awards and Fellowships
1. McGill-Japan Visiting Scholar Award (for visit of Dr. Yoshiaki Oda)
Professional Activities
1. Member of Editorial Boards of:Discrete Applied Mathematics.
Computational Geometry: Theory and Applications.
Graphs and Combinatorics.
Discrete and Computational Geometry.
2. Advisory Member of the IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences published by The Institute of Electronics, Information and Communication Engineers of Japan (1994-2002).
3. Member of selection committee for the Japan Science and Technology Fund (Academic Section) administered by the N.S.E.R.C., from January 1994.
4. Referee for numerous Journals including:
Advances in Computing Research, Algorithmica, Annals of Discrete Mathematics, American
Math Monthly, Australasian Journal of Combinatorics, Communications of the ACM, Discrete
Applied Mathematics, Discrete Mathematics, Discrete and Computational Geometry, European
Journal of Combinatorics, Graphs and Combinatorics, IEEE Transactions on Computers, IEEE
Transactions on Information Theory, Information Processing Letters, Information Sciences, Journal of Classification, Journal of Fire Prevention Engineering, Journal of Graph Theory, Journal of
Combinatorial Theory B, Journal of the ACM, Journal of Computers and Systems Sciences, Journal of Optimization Theory and Applications, Journal of Symbolic Computation, Mathematical
Programming, Networks, Neural Networks, SIAM Journal of Computing, The Visual Computer,Transactions on Mathematical Software.
5. Member of Grant Selection Committee for N.S.E.R.C. Operating grants (1987/90) and theProvince of Québec F.C.A.R. team research grants (1981/83).

-36. Reviewer for Canada Council, Mathematical Reviews, N.S.E.R.C., N.S.F, City College Summer Bursaries.
7. External evaluator for tenure decisions at University of Newcastle, Carleton University, Simon
Fraser University, University of California(Berkeley), and University of Saskatchewan.
8. Program Committee chairman, 8th ACM Symposium on Computational Geometry, Berlin,
1992. Program Committee member, 6th ACM Symposium on Computational Geometry, Urbana,
1990.
9. Co-organizer of the First Canadian Conference on Computational Geometry, McGill University, 1989.
10. Program Committee member, 3rd Annual International Symposium on Algorithms and Computation, Nagoya 1992.
11. External evaluator for PhD. theses at Rutger’s University and University of Waterloo.
12. Guest Editor of Discrete and Computational Geometry, Volume 10, No. 2, 1993 based on
ACM Symposium on Computational Geometry, Berlin 1991.
13. Guest Editor of Discrete Applied Mathematics, Volume 31, No. 2, 1991 based on First Candian Conference on Computational Geometry, Montreal 1989.
14. Co-editor with P. Bose of Snapshots of Computational and Discrete Geometry, Volume 3,
School of Computer Science, McGill University.
15. Program Committee, CCCG ’97, Kingston ON, August 1997.
16. Co-organizer (with E. Goodman and R. Pollack) of 924th AMS meeting, Montreal, Sept.
26-28 1997.
17. Session Chair, ISMP’97, Lausanne, August 1997.
18. Session Chair, Journées de geometrie algorithmique, Sophia-Antipolis, May 1998.
19. Co-organizer (with V. Klee and P. Gritzmann) of Oberwolfach meeting on Computational
Convexity, February 1999.
20. Co-organizer (with T. Biedl, L. Devroye, S. Lezard, G. Toussaint, S. Whitesides) of 10th
Canadian Conference on Computational Geometry, McGill, August 1998.
21. Program Committee, COCOON’2000, Sydney, Australia, July 2000.
22. Program Committee, Japanese Conference on Discrete and Computational Geometry, Tokyo,
November 2000, December 2002.
23. Program Committee, 20th ACM Symposium on Computational Geometry, May 2004.
24. Co-organizer (with B. Reed) of Colloquium on Applied Optimization, GERAD-HEC, Montreal, October 15, 2004.
25. Co-organizer (with A. Deza) of Polyhedral Computation I-III, 3 sessions in Journées del’optimisation, 2005, GERAD, Montreal, May 9-11, 2005.
26. Program Committee, Franco-Canadian Workshop on Combinatorial Algorithms, McMaster
University, August 2005.
27. Co-organizer (with D. Bremner and Antoine Deza) of Workshop on Polyhedral Computation,
CRM, Montréal, October 2006.
28. Program Committee Co-Chair, Computational Geometry and Graph Theory, Kyoto University, June 2007.
29. Program Committee Co-Chair, ICQNM 2008, Martinique, February 2008.
30. Program Committee, CanaDAM 2009, Montreal, May 2009.
31. Program Committee, IPCO 2010, Lausanne, June 2010.
32. Program Committee, XIV Spanish Meeting on Computational Geometry, Alcala de Henares,June 2011.

-4Industrial Experience
Position

Dates

Location

Consultant
Consultant
Consultant
Programmer Analyst

2.94 - 4.94
8.83 - 9.83
1.75 - 3.76
1.69 - 5.73

MontréalMontréal
Palo Alto CA and Fairbanks, Alaska
Six four month work terms in industry

Conferences where papers were presented
Discrete Geometry and Optimization, Fields’ Institute, Toronto, September 2011.
AAAC 2011, Taiwan, April 2011.
Efficiency of the Simplex Method, IPAM, UCLA, Los Angeles, January 2011.
Discrete and Computational Geometry, Bernoulli Institute, EPFL, September 2010.
Erdos Lecturer, Canadian Conference on Computational Geometry, Winnipeg, August 2010.
Canada-Japan Workshop on Discrete and Comptutaional Geometry, Tokyo, June 2009.
International Conference on Quantum, Nano and Micro Technologies (ICQNM), Martinique, January 2008.
International Workshop on Combinatorics, Yokohama, June 2007.
International Conference on Quantum, Nano and Micro Technologies (ICQNM), Guadeloupe,
January 2007
Conference on Applications of Computer Algebra (ACA 2005) Nara, Japan, August 2005 (paper
presented by Rudy Raymond)
Workshop on Enumeration Algorithms, Gunma University, March 2005.
High Performance Algorithms and Software for Nonlinear Optimization, HSPNO 2004, Ischia,
Italy, June 2004.
Computers and Discovery, invited speaker, DIMACS-GERAD workshop, June 2004.
3rd Discrete Math Day, invited speaker, Carleton University, April 2004.
Journées d’optimisation", conférence magistral, Montreal, May 2003.
Third Japan Conference on Discrete and Computational Geometry, invited speaker, Tokai University, Tokyo, December 2002.
New Trends in Optimization (NTOC ’01), Kyoto, Japan, December 2001.
Max Clique ’01, University of Klagenfurt, Austria, May 2001 (presented by C. de Simone)
4th Latin American Symposium on Theoretical Informatics, Punta del Este, Uruguay, April 2000.
(presented by C. de Simone)
3rd SPA Workshop, Komatsu, Japan, May 2000.
Kansai Operations Research Regional Meeting, Kyoto University, January 2000, invited speaker.
Workshop on Geometry and Software, ETH Zurich, April 1999, invited speaker.
First Japan Conference on Discrete and Computational Geometry, invited speaker, Tokai University, Tokyo, December 1998.
3rd SMM-AMS Meeting, Oaxaca, December 1997.
ISMP’97, Lausanne, August 1997, invited speaker
8th CCCCG, Ottawa, August 1996, joint paper presented by M. Kong.
ACM Special Meeting on Discrete and Computational Geometry, Mount Hollyoke, Mass., July
1996, invited speaker.
2nd SPA Workshop, Dogashima, Japan, May 1995, co-organizer (with H. Imai).
24th Computational Geometry Day, Courant Institute, New York, October 1994, invited speaker.

-5Workshop on Discrete and Computational Geometry, Hungarian Academy of Science, Budapest,
June 1994, invited speaker.
892nd meeting of American Mathematical Society, Brooklyn N.Y., April 1994, invited speaker.
Workshop on Polyhedra, Kyoto University, May 1993, opening speaker.
Computational Geometry Day, Courant Institute, New York, 1992, invited speaker.
Colloque des Sciences Mathématiques du Québec, Montréal, October 1991, invited speaker.
Third Canadian Conference of Computational Geometry, Vancouver, August 1991, plenary
speaker.
7th ACM Symposium on Computational Geometry, North Conway NH, June 1991.
1st and 5th Tokyo Algorithms Day, Tokyo, May 1991, October 1990, invited speaker.
The 2nd Japan Conference on Graph Theory and Applications, Hakone, August 1990, invited
speaker.
First SIGAL Conference, Tokyo, August 1990.
First Canadian Conference of Computational Geometry, Montreal, August 1989.
Journées d’Optimisation, Université de Montreal, May 1989, invited participant.
Mathematical Programming Symposium, Tokyo, August 1988, invited participant.
13th IFIP Conference on System Modelling and Optimization, Tokyo, August 1987, invited participant.
Workshop in Computational Combinatorics, Vancouver, July-August 1987, invited participant.
3rd ACM Symposium on Computational Geometry, Waterloo, Ontario, June 1987.
Algorithms and Combinatorial Geometry, Mathematisches Forschungsinstitut Oberwolfach,Freiburg, West Germany, February 1987, invited participant.
2nd Computational Geometry Day, Courant Institute, New York, 1987, invited speaker.
AMS-IMS-SIAM Summer Research Conference on Discrete and Computational Geometry, Santa
Cruz CA, July 1986, invited participant.
3 ème Colloque International Théorie des Graphes et Combinatoire, Marseille-Luminy, June
1986, invited speaker.
The 1st Japan Conference on Graph Theory and Applications, Hakone, June 1986, invited
speaker.
2nd ACM Symposium on Computational Geometry, Yorktown Heights NY, June 1986.
1st ACM Symposium on Computational Geometry, Baltimore MD., June 1985.
International Conference on Foundations of Data Organization, Kyoto, Japan, May 1985.
IEEE Conference on Information Science, St. Jovite, Québec, September 1983.
Workshop on Computational Geometry, University of Illinois, invited paper, October 1982.
AMS Summer Meeting, Toronto, invited paper, August 1982.
2nd Franco-Southeast Asian Mathematics Conference, Quezon City, Philippines, May 1982.
Summer Graph Theory Symposium, Hakone, Japan, invited paper, May 1982.
Symposium on Matching Theory, National Bureau of Standards, invited paper, October, 1981.
International Mathematics Conference, National University of Singapore, Singapore, May 1981.
87th Annual ACM Meeting, San Francisco CA, invited paper, January 1981.
18th Allerton Conference, Urbana IL, October 1980.
Franco-Canadian Combinatorial Colloquium, Montréal, August 1979.
ISCAS Meeting, Tokyo, July 1979.
Summer Japanese Graph Theory Symposium, Nikko, Japan, July 1979.
9th S.E. Conference on Combinatorics, Graph Theory and Computing, Boca Raton FL,February
1978.

-6Invited Lectures
University of Tokyo, December 2010, December 1998(4 lectures), January 1997, August 1996,
November 1995, April 1995, December 1994, April 1994, July 1993, May 1992, July 1988, November 1983, May 1982, June 1980.
Tohoku University, December 2010, April 2006, March 2005, July 2000.
Tokyo Science University, June 2010.
ERATO, Tokyo, December 2009, April 2006.
Mini-school on Computational Geometry, Kyoto, March 2006 (2 lectures).
KIDS, Kyoto University, January 2006.
Operations Society of Japan, Kyoto, January 2006.
National Institute of Informatics, Tokyo, March 2005.
University of San Marcos, November 2004.
ERATO Quantum Computing and Information, December 2003.
Kyoto University, Kyoto, December 2003, June 2001, April 1988, March 1984.
IASI-CNR Rome, June 2003, April 1998.
University of West Indies, Kingston, Jamaica, February 2003, February 2001, March 1991 (2 lectures).
Tokyo Institute of Technology, December 2002, July 1993, October 1990 (2 lectures), July 1988,
June 1983, May 1982.
C.O.R.E., Université de Louvain, Belgium, May 2002.
Technical University of Berlin, May 2002.
University of Technology, Kingston, Jamaica, February 2002, February 1999, March 1997.
Universitat Politecnica de Catalunya, May 2001.
GERAD, Montreal, March 2001
Electro-Communications University, Tokyo, May 2000.
EPFL Lausanne, April 1999(5 lectures), April 1998(5 lectures).
ETH Zurich, April 1998.
University of Rome, La Sapienza, February 1998.
University of Tokyo January 1998(two lectures).
TRL-IBM Japan, January 1998.
Simon Fraser University, October 1996.
IBM Japan, Yokohama, August 1996.
Niigata University, March 1996.
Tsukuba University, April 1994, May 1993, May 1992(3 lectures).
Keio University, July 1993.
University of Hong Kong, June 1993.
Chuo University, June 1993 (3 lectures).
Osaka Electro-Communications University, April 1993.
Dalhousie University, October 1992.
Cornell University, Ithaca NY, November 1991.
Queen’s University, Kingston Ont., November 1991, December 1980.
Fujitsu Research Labs, Kawasaki, October 1990.
Tokai University, Hiratsuka, Japan, October 1990, June 1980, June 1979.
Kyushu University, Fukuoka, June 1990, April 1989, May 1988

-7Université du Québec á Montréal, March 1990.
Case Western Reserve University, Cleveland, February 1990.
Hitachi Central Research Laboratories, Kokubunji, April 1989.
Courant Institute, New York University, March 1989, December 1985.
Bell Core, NJ, February 1987.
City College, NY, April 1986.
Princeton University, December 1985.
Carleton University, Ottawa, November 1985.
Short Courses Given
Institution

Title

Date

Kyoto University
Kyoto University
Kyoto University
E.P.F.L.
E.P.F.L.
University of Tokyo
University of Tokyo
Keio University
University of Tokyo

Algorithms for High Dimensional Computational Geometry
Discrete and Computational Geometry
Advanced Algorithms
Metric and Cut Polyhedras
Pivot Methods for Convex Hulls
Cryptography
Generating Discrete Objects
Discrete and Computational Geometry
Discrete and Computational Geometry

April-June 2005
April-July 2000
April-July 2000
April 1999
April 1998
April 1997
May 1996
December 1994
October 1990

Teaching at McGill
COMP 100 Introduction to Computing
COMP 203 Introduction to Computing - II
COMP 250 Introduction to Computer Science
COMP 315 Data Structures
COMP 360 Algorithm Design Techniques
COMP 506 Advanced Analysis of Algorithms
COMP 507 Computational Geometry (New Course)
COMP 566 Computer Methods in Operations Research
COMP 567 Integer Programming (New Course)
COMP 610 Information Structures - 1
COMP 611 Information Structures - 2
COMP 647 Cryptography and Data Security (New Course)
COMP 650 Combinatorial Algorithms - 1 (New Course)
COMP 651 Combinatorial Algorithms - 2 (New Course)
COMP 762 Topics in VLSI (New Course)
Note: Courses numbered COMP 500 and higher are graduate courses.
Postdoctoral Fellows
Mark Wilde, Sep 2009 - present, Quantum Information
Stephan Langerman, Sep 2001- Dec 2002, Geometric Search.
Tom Fevens, May-Dec 2000, Convex Subsets.
Sylvain Lezard, Nov-Dec 1998, Geometric Computation.

-8Graduate Student Supervision
Name

DegreeTitle

Date GraduatedY. Furukawa
D. Paku
C. Meagher
T. Deering
T. Imamura
B. Kaluzny

MSc.
MSc.
Phd.
MSc.
PhD.
PhD.
MSc.
PhD.
PhD.
PhD.
PhD.
MSc.
PhD.
PhD.
PhD.
PhD.
PhD.
MSc.
PhD.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.
MSc.A
MSc.
MSc.A
MSc.
MSc.A
MSc.
MSc.

Hardness Results for History Based Pivot Rules
Nash Equilibria for Undirected Web Graphs
Directed Max Cut with Mining Applications
History Based Pivot Rules for USOs
Vertex and Set Covering
Pivoting on Polyhedra and Arrangements
Finite Pivot Algorithms and Feasibility
Surface Matching in 3-Dimensional Images
On the Complexity of Vertex and Facet Enumeration
Register Allocation for Optimal Loop SchedulingLine Transveral Algorithms in the Plane
Hidden-surface Removal in Polyhedral Cross-sections
Linear Approximation and Line Transversals
Fault Tolerant Arrays
Visibility and Art Gallery Theorems
Stabbing and Separation
Complexity of Computing Simple Circuits in the Plane
Visibility in Restricted Classes of Polyhedra
Hierarchical Decomposition of Polygons with Applications
Feasibility algorithms for linear programming
Projections of Penatagon Inequalities
Linear Programming Relaxations for Max Cut
Tool for Real-Time Conscious Design of Distributed Systems
Elliptic Curve Cryptography
Undeniable Signatures
Survey of Internet Security Protocols
A Survey of Public Key Infrastructures
Performance Modelling of Terabit Optical Backplane
Cryptography and Number Theory
Generating Rooted Triangulations with Minimum Degree Four
Production Scheduling with Lead Times
Computer Aided Learning in Recursive Algorithms
Robot Location
Partitioning Point Sets
Geometric Covering
Manipulating 3-d Polyhedra
Vertical and Orthogonal L1 Linear Approximation
Motion Planning Arround Disks

2015
2015
2011
2010
2007
2005
2001
1998
1997
1993
1992
1987
1991
1991
1989
1988
1986
1982
1985
2005
2004
2002
2000
1998
1998
1997
1997
1997
1997
1996
1995
1995
1990
1990
1989
1989
1988
1988

D. MacDonald
D. Bremner
N. Qi
P. Egyed
J-M. Robert
L. Laforge
T. Shermer
R. Wenger
D. Rappaport
H. ElGindy
R. Bitar
A. Guérette
J. Umemoto
G. Jabbour
T. Nkgau
J.F. Yeung
K. TseM. Branchaud
V.K. Ho
M. Saeki
M. Kong
C. Trouiller
D. Simmonds
A. Leblanc
J. Caron
G. PesantL. Boyd-Wilson
P. Yamamoto
G. Gao

The following students were co-supervised:Nkgau’s Phd with K. Fukuda (Mcgill, Computer Science)
Ho with T. Szymanski(McGill, Elec. Eng.)
Qi with G. Gao (McGill, Computer Science)
MacDonald with A. Evans (Montreal Neurological Institute)
Saeki and Yeung with C. Crepeau (U. de Montréal, IRO)
Trouiller with J-L Goffin (McGill, Management)
Jabbour with M. Saksena (Concordia, CS)
List of Publications
Most publications since 1986 available on-line at: http://cgm.cs.mcgill.ca/˜avis/
Refereed Journal Papers
1.
D. Avis and C. Jordan, “mplrs: A Scalable Parallel Vertex/Facet enumeration Code,” Math.
Prog. Computation (online) (2017).

-92.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

13.
14.
15.

16.
17.
18.

19.
20.
21.
22.
23.
24.
25.

D. Avis and O. Friedmann, “An Exponential Lower Bound for Cunningham’s Rule,” Math.
Prog. B 161, pp. 271-305 (2017).
D. Avis and H. Tiwary, “Compact Linear Programs for 2SAT,” European J. of Combinatorics (2017(accepted)).
D. Avis and H. Tiwary, “On the H-free Extension Complexity of the TSP,” Optimization
Letters, pp. 445-455 (2017).
D. Avis and C. Meagher, “On the Directed Cut Cone and Polytope,” J. Combinatorial Optimization 31, pp. 1685-1708 (2016).
D. Avis and H. Tiwary, “A Generalization of Extension Complexity that Captures P,” Information Proc. Letters, pp. 6-8 (2015).
R. Dimitrakopoulos, C. Meagher, and D. Avis, “Optimized Open Pit Mine Design, Pushbacks and the Gap Problem - A Review,” Journal of Mining Science 50, pp. 508-526 (2014).
D. Avis and H. Tiwary, “On the Extension Complexity of Combinatorial Polytopes,” Mathematical Programming B (2014).
M. Cuturi and D. Avis, “Ground Metric Learning,” Journal of Machine Learning Research
15, pp. 533-64 (2014).
D. Avis, K. Iwama, and D. Paku, “Reputation Games for Undirected Graphs,” Discrete
Applied Mathematics 166, pp. 1-13 (2014).
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 ofHamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations ofHypercubes,” Discrete Applied Mathematics 160, pp. 2104-15 (2012).
D. Avis, P. Hayden, and M. Wilde, “Leggett-Garg Inequalities and the Geometry of the Cut
Polytope,” Physical Review A 82 (2010). 030102(R).
D. Avis, S. Moriyama, and M. Owari, “From Bell Inequalities to Tsirelson’s Theorem,”Proc. IECIE E92-A, pp. 1254-67 (2009).
M. Ohsaki, N. Katoh, T. Kinoshita, S. Tanigawa, D. Avis, and I. Streinu, “Enumeration of
Optimal Pin Jointed Bistable Compliant Mechanisms with Non-Crossing Members,” J. of
Structural and Multidisciplinary Optimization 37, pp. 645-665 (2009).
D. Avis, P. Hayden, and I. Savov, “Distributed Compression and Multiparty Squashed
Entanglement,” Journal of Physics A 41 (2008 (24 pages)).
D. Avis, H. Imai, and T. Ito, “Generating Facets of the Cut Polytope by Triangular Elimination,” Mathematical Programming 112, pp. 303-25 (2008).
D. Avis, N. Katoh, M. Ohsaki, I. Streinu, and S. Tanigawa, “Enumerating Constrained Noncrossing Minimally Rigid Frameworks,” Discrete and Computational Geometry 40(1),pp. 31-46 (2008).
D. Avis and B. Kaluzny, “Computing Disjoint Paths on Polytopes,” Journal of Combinatorial Optimization (April 2008, online). 23 pages.
D. Avis, B. Kaluzny, and D. Titley-Peloquin, “Visualizing and Constructing Cycles in the
Simplex Method,” Operations Research 56, pp. 512-518 (2008).
D. Avis, J. Bondy, W. Cook, and B. Reed, “Vasek Chvátal: A Short Introduction,” Graphs
and Combinatorics 23, pp. 41-66 (2007).
D. Avis, N. Katoh, M. Ohsaki, I. Streinu, and S. Tanigawa, “Enumerating Planar Minimally
Rigid Graphs,” Graphs and Combinatorics 23, pp. 117-34 (2007).
D. Avis and T. Imamura, “A List Heuristic for Vertex Cover,” Operations Research Letters
35, pp. 201-4 (2007).
D. Avis and T. Ito, “New Classes of Facets of the Cut Polytope and Tightness of the
I_mm22 Bell Inequalities,” Discrete Applied Mathematics 155, pp. 1689-99 (2007).
D. Avis, H. Imai, and T. Ito, “On the Relationship Between Convex Bodies Related to Correlation Experiments with Dichotomic Observables,” Journal of Physics A 39(36),pp. 11283-99 (2006).

-1026.
27.
28.
29.

30.
31.
32.
33.
34.
35.
36.
37.
38.

39.
40.
41.

42.
43.
44.
45.
46.
47.

48.
49.

T. Ito, H. Imai, and D. Avis, “Bell Inequalities Stronger than the CHSH Inequality for Three
Level Isotropic States,” Physical Review A 73(4), p. 042109(9 pages) (2006).
D. Avis and A. Deza, “Un des "Problèmes Plaisans et Délectables" de Claude Berge,” Discrete Mathematics 306, pp. 2299-2302 (2006).
D. Avis, C. De Simone, and B. Reed, “On the Fractional Chromatic Index of a Graph and its
Complement,” Operations Research Letters 33, pp. 385-388 (2005).
D. Avis, J. Hasegawa, Y. Kikuchi, and Y. Sasaki, “A Quantum Protocol to Win the Graph
Colouring Game on all Hadamard Graphs,” IEICE Trans. Fundamentals E89A, pp. 1378-81(2005).
D. Avis, H. Imai, T. Ito, and Y. Sasaki, “Two-party Bell Inequalities Derived from Combinatorics via Triangular Elimination,” Journal of Physics A 38(50), pp. 10971-10987 (2005).
D. Avis and B. Kaluzny, “Solving Inequalities and Proving Farkas’ Lemma Made Easy,”
AMS Mathematical Monthly 111, pp. 152-157 (2004).
D. Avis and J. Umemoto, “Stronger Linear Programming Relaxations of Max-Cut,” Mathematical Programming B 97, pp. 451-469 (2003).
D. Avis, C. De Simone, and P. Nobili, “On the Chromatic Polynomial of a Graph,” Mathematical Programming B B 92, pp. 439-452 (2002).
D. Avis, K. Hosono, and M. Urabe, “On the Existence of a Point Set with a Specified Number of Interior Points,” Discrete Mathematics 241, pp. 33-40 (2001).
D. Avis and A. Deza, “On the Binary Solitaire Cone,” Discrete and Applied Mathematics
115, pp. 3-14 (2001).
D. Avis and A. Deza, “On the Solitaire Cone and its Relationship to Multicommodity
Flows,” Mathematical Programming 90-1, pp. 27-57 (2001).
D. MacDonald, N. Kabani, D. Avis, and A.C. Evans, “Automated 3-D Extraction of Innerand Outer Surfaces of Cerebral Cortex from MRI,” Neuroimage 12, pp. 340-356 (2000).
D. Avis, A. Deza, and S. Onn, “A Combinatorial Approach to the Solitaire Game,” IEICE
Trans. on Fund. of Electronics, Communications and Computer Sciences E83-A,
pp. 656-661 (2000).
D. Avis and L. Devroye, “Estimating the Number of Vertices of a Polyhedron,” Information
Processing Letters 73, pp. 137-143 (2000).
D. Avis, “Computational Experience with the Reverse Search Vertex Enumeration Algorithm,” Optimization Methods and Software 10, pp. 107-124 (1998).
D. Avis, B. Beresford-Smith, L. Devroye, H. ElGindy, E. Guevermont, F. Hurtado, and B.
Zhu, “Unoriented Theta-Maxima in the Plane: Complexity and Algorithms,” SIAM J. Comput. 28, pp. 278-296 (1998).
D. Avis, D. Bremner, and R. Seidel, “How Good are Convex Hull Algorithms?” Computational Geometry: Theory and Applications 7, pp. 265-301 (1997).
D. Avis and D. Bremner, “Large Convex Hull Problems,” Zeitschrift fur Ang. Math. und
Mec. 76, suppl. 3, pp. 179-182 (1996).
D. Avis, “Generating Rooted Triangulations Without Repetitions,” Algorithmica 16,
pp. 618-632 (1996).
D. Avis and K. Fukuda, “Reverse Search for Enumeration,” Discrete Applied Math 6,
pp. 21-46 (1996).
D. Avis and M. Houle, “Computational Aspects of Helly’s Theorem and its Relatives,”
International Journal of Computational Geometry & Applications 5, pp. 357-367 (1995).
G. Ceder, G.D. Garbulsky, D. Avis, and K. Fukuda, “Ground States of a Ternary Lattice
Model with Nearest and Next-Nearest Neighbor Interactions,” Physical Review B 49,
pp. 1-7 (1994).
D. Avis and H. Maehara, “Metric Extensions and the L1-Hierarchy,” Discrete Mathematics
131, pp. 17-28 (1994).
D. Avis and V. P. Grishukhin, “A Bound on the k-gonality of Facets of the HypermetricCone and Related Complexity Problems,” Computational Geometry: Theory and

-11-

50.
51.

52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.

63.
64.
65.
66.
67.
68.
69.
70.

71.
72.
73.

Applications 2, pp. 241-254 (1993).
D. Avis, “The m-Core Properly Contains the m-Divisible Points in Space,” Pattern Recognition Letters 14, pp. 703-705 (1993).
D. Avis and K. Fukuda, “A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of
Arrangements and Polyhedra,” Discrete and Computational Geometry 8, pp. 295-313(1992).
D. Avis and K. Fukuda, “A Basis Enumeration Algorithm for Linear Systems with Geometric Applications,” Applied Math. Letters 4, pp. 39-42 (1991).
D. Avis and M. Deza, “The Cut Cone, L1-Embedability, Complexity and Multicommodity
Flows,” Networks 21, pp. 595-617 (1991).
D. Avis, P. Erdos, and J. Pach, “Distinct Distances Determined by a Subset of Points inSpace,” Computational Geometry: Theory and Applications 1, pp. 1-12 (1991).
D. Avis and H. Imai, “Locating A Robot With Angle and Distance Measurements,” J. Symbolic Computation 10, pp. 311-327 (1990).
D. Avis and M. Doskas, “Algorithms for High Dimensional Stabbing Problems,” Discrete
Applied Math. 27, pp. 39-48 (1990).
D. Avis, J-M. Robert, and R. Wenger, “Lower Bounds for Line Stabbing,” Information Processing Letters 33, pp. 59-62 (1989).
D. Avis and Mutt, “All the Facets of The Six Point Hamming Cone,” European Journal of
Combinatorics 10, pp. 309-312 (1989).
A. Somani, V. K. Agarwal, and D. Avis, “On the Complexity of Single Fault Set Diagnosability and Diagnosis Problems,” IEEE Trans. on Computers 38, pp. 195-201 (1989).
D. Avis, P. Erdos, and J. Pach, “Repeated Distances in Space,” Graphs and Combinatorics
4, pp. 207-217 (1988).
D. Avis and R. Wenger, “Polyhedral Line Transversals in Space,” Discrete and Computational Geometry 3, pp. 257-265 (1988).
D. Avis, B. Davis, and J. M. Steele, “Probabilistic Analysis of a Greedy Heuristic for
Euclidean Matching,” Probability In the Engineering and Information Sciences 2,
pp. 143-156 (1988).
D. Avis and C. W. Lai, “The Probabilistic Analysis of a Heuristic for the Assignment Problem,” SIAM Journal on Computing 17, pp. 732-741 (1988).
D. Avis, B. K. Bhattacharya, and H. Imai, “Computing the Volume of the Union of
Spheres,” The Visual Computer 3, pp. 323-328 (1988).
D. Avis and H. ElGindy, “Triangulating Point Sets in Space,” Discrete and Computational
Geometry 2, pp. 99-111 (1987).
A. Somani, V. K. Agarwal, and D. Avis, “A Generalized Theory for System Level Diagnosis,” IEEE Trans. on Computers C-36, pp. 538-547 (1987).
D. Avis, T. Gum, and G. Toussaint, “Visibility Between Two Edges of a Simple Polygon,”
The Visual Computer 2, pp. 342-357 (1986).
D. Avis, “Diameter Partitioning,” Discrete and Computational Geometry 1, pp. 265-276(1986).
J. Akiyama, K. Ando, and D. Avis, “Eccentric Graphs,” Discrete Mathematics 56, pp. 1-6(1985).
D. Avis and J. Horton, “Remarks on The Sphere of Influence Graph” in Discrete Geometry
and Convexity, ed. Goodman, Lutwak, Malkevitch, and Pollack 440, pp. 323-327, N.Y.
Academy of Sciences (1985).
D. Avis and L. Devroye, “An Analysis of a Decomposition Heuristic for the Assignment
Problem,” Operations Research Letters 3, pp. 279-283 (1985).
D. Avis, “Non-Partitionable Point Sets,” Information Proc. Letters 19, pp. 125-129 (1984).
D. Avis, “The Number of Furthest Neighbour Pairs of a Finite Planar Set,” American Math
Monthly 91, pp. 417-420 (1984).

-1274.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.

J. Akiyama, K. Ando, and D. Avis, “Miscellaneous Properties of Equi-Eccentric Graphs,”
Annals of Discrete Mathematics 20, pp. 13-23 (1983).
D. Avis, “A Survey of Heuristics for the Weighted Matching Problem,” Networks 13,
pp. 475-493 (1983).
D. Avis and H. ElGindy, “A Combinatorial Approach to Polygon Similarity,” IEEE Trans.
on Information Theory IT-29, pp. 148-150 (1983).
H. ElGindy, D. Avis, and G. T. Toussaint, “Applications of a Two-dimensional Hidden Line
Algorithm to Other Geometric Problems,” Computing 31, pp. 191-202 (1983).
D. Avis, G. T. Toussaint, and B. K. Bhattacharya, “On the Multimodality of Distances in a
Convex Polygon,” Computers and Maths. with Applications 8, pp. 153-156 (1982).
D. Avis, “On the Complexity of Finding the Convex Hull of a Set Points,” Discrete Applied
Math 4, pp. 81-86 (1982).
G.T. Toussaint and D. Avis, “On a Convex Hull Algorithm for Polygons and its Application
to Triangulation Problems,” Pattern Recognition 15, pp. 23-29 (1982).
J. Akiyama, D. Avis, V. Chvátal, and H. Era, “Balancing Signed Graphs,” Discrete Applied
Maths. 3, pp. 227-233 (1981).
D. Avis and G. T. Toussaint, “An Efficient Algorithm for Decomposing a Polygon into Starshaped Components,” Pattern Recognition 13, pp. 395-398 (1981).
D. Avis, “Hypermetric Spaces and the Hamming Cone,” Canadian Journal of Mathematics
33, pp. 795-802 (1981).
D. Avis and G. T. Toussaint, “An Optimal Algorithm for Determining the Visibility of a
Polygon from an Edge,” IEEE Trans. on Computers C-30, pp. 910-914 (1981).
D. Avis, “Worst Case Bounds for the Euclidean Matching Problem,” Computers and Maths
with Applications 7, pp. 251-257 (1981).
D. Avis and M. Newborn, “On Pop-stacks in Series,” Utilitas Mathematica 19, pp. 129-140(1981).
H. ElGindy and D. Avis, “A Linear Algorithm for Computing the Visibility of a Polygon
from a Point,” J. of Algorithms 2, pp. 186-197 (1981).
J. Akiyama, D. Avis, and H. Era, “On a [1,2] factor of a Graph,” TRU Mathematics 16,
pp. 97-102 (1980).
D. Avis, “Comments on a Lower Bound for Convex Hull Determination,” Information Proc.
Letters 11, p. 126 (1980).
D. Avis, “A Note on Some Computationally Difficult Set Covering Problems,” Math. Programming 18, pp. 138-145 (1980).
D. Avis, “On the Extreme Rays of the Metric Cone,” Canadian J. of Maths. 32, pp. 126-144(1980).
D. Avis, “Extremal Metrics Induced by Graphs,” Annals of Discrete Maths. 8, pp. 217-220(1980).
D. Avis, “On Minimal 5-Chromatic Triangle Free Graphs,” J. of Graph Theory 3,
pp. 397-400 (1979).
D. McCallum and D. Avis, “On the Complexity of Finding the Convex Hull of a Simple
Polygon,” Information Proc. Letters 9, pp. 201-206 (1979).
D. Avis and V. Chvátal, “Notes on Bland’s Pivoting Rule,” Math. Programming Study 8,
pp. 24-34 (1978).
D. Avis, “Computing the Waiting Time in GI/Ek/c Queueing Systems,” Studies in Management Science 7, pp. 215-232 (1977).

Books and Special Journal Editions
1.
D. Avis, D. Bremner, and A. Deza (editors), Polyhedral Computation, CRM-AMS Proceedings and Lecture Notes (2008). 150 pages.

-132.

3.
4.
5.
6.
7.

D. Avis, A. Bondy, M. Kano, and N. Katoh (editors), Computational Geometry and Graph
Theory:The Akiyama-Chvátal 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).

Book Chapters
1.
D. Avis and S. Moriyama, “On Combinatorial Properties of Linear Program Digraphs” in
Polyhedral Computation 49, pp. 1-14, CRM-AMS Proceedings and Lecture Notes (2009).
2.
D. Avis, “lrs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm” in Polytopes - Combinatorics and Computation, ed. G. Kalai and G.M. Ziegler,
pp. 177-198, Birkhauser-Verlag (2000).
3.
D. Avis, “A C Implementation of the Reverse Search Vertex Enumeration Algorithm” in
RIMS Kokyuroku 872, ed. H. Imai, Kyoto University (May 1994). http://cgm.cs.mcgill.ca/˜avis/doc/avis/Av94a.ps.
4.
D. Avis and D. Rappaport, “Computing Monotone Simple Circuits in the Plane” in Computational Morphology, ed. G. Toussaint, pp. 13-23, North-Holland (1988).
5.
D. Avis, “Space Partitioning and its Application to Generalized Retrieval Problems” inFoundations of Data Organization, ed. S.Ghosh, Y. Kambayashi, K. Tanaka, pp. 237-249,
Plenum Press (1987).
6.
D. Avis, H. ElGindy, and R. Seidel, “A Simple On-line Algorithm for Planar Convex Hulls”
in Computational Geometry, ed. G. T. Toussaint, pp. 23-41, Springer Verlag (1985).
7.
D. Avis and B. K. Bhattacharya, “Algorithms for Computing d-dimensional Voronoi Diagrams and Their Duals” in Advances in Computing Research 1, Computational Geometry,ed. F.P. Preparata, pp. 159-180, JAI Press (1983).
Conference Proceedings
1.
D. Avis and H. Tiwary, “On the Extension Complexity of Combinatorial Polytopes,” ICALP,
pp. 57-68 (2013).
2.
D. Avis and G. Roumanis, “A Portable Parallel Implementation of the lrs Vertex Enumeration Code,” Lecture Notes in Computer Science LNCS 8287, pp. 414-29 (2013). COCOA
2013.
3.
D. Avis, K. Iwama, and D. Paku, “Verifying Nash Equilibria in Page Rank Games in Undirected Web Graphs” in ISAAC 2011, Tokyo.
4.
D. Aoshima, D. Avis, T. Deering, Y. Matsumoto, and S. Moriyama, “Enumerating Hamiltonian Paths on Acyclic USO Cubes with History Based Pivot Rules” in AAAC 2011 (April,2011).
5.
D. Avis and A. Broadbent, “The Quantum Locker Puzzle,” ICQNM2009, IEEE Digital
Library (February 2009). 4 pages.
6.
D. Avis, H. Miyata, and S. Moriyama, “A Family of Polytopal Digraphs that do not Satisfy
the Shelling Property” in 6-th Japanese-Hungarian Symposium (June 2009).
7.
D. Avis, P. Fischer, A. Hilbert, and A. Khrennikov, “Complete account of randomness in the
EPR-Bohm-Bell experiment,” Foundations of Probability and Physics-5 (2008 (14 pages)).

-148.
9.
10.
11.
12.

13.
14.

15.
16.
17.

18.
19.
20.

21.

22.

23.
24.

25.

26.
27.
28.
29.

D. Avis, P. Hayden, and I. Savov, “Multiparty Distributed Compression of Quantum Information,” ICQNM 2008, IEEE Digital Library (February 2008 (7 pages)).
D. Avis and T. Ito, “Comparison of Two Bounds of the Quantum Correlation Set,” ICQNM
2007, IEEE Digital Library (January 2007 (3 pages)).
D. Avis, “Quantum Correlations: From Bell inequalities to Tsirelson’s Theorem,” Proc.
International Workshop on Combinatorics, Yokohama (June 2007 (10 pages)).
D. Avis and T. Ito, “Polyhedral and Semidefinite Approaches to Classical and Quantum Bell
Inequalities,” AQIS 2006, Beijing (Sep. 2006 (2 pages)).
N. Katoh, M. Ohsaki, T. Kinoshita, S. Tanigawa, D. Avis, and I. Streinu, “Enumeration of
Optimal Pin-Jointed Bistable Mechanisms,” 4th China-Japan-Korea Symp. of Structural andMechanical Systems, Beijing (Nov. 2006 (6 pages)).
T. Ito, Y. Sasaki, H. Imai, and D. Avis, “Families of Tight Bell Inequalities Derived fromClasses of Facets of Cut Polytopes” in EQIS’04, pp. 78-9, Tokyo (September 2004).
D. Avis, “On the Complexity of Testing Hypermetric, Negative Type, k-gonal and Gap
Inequalities,” Lecture Notes in Computer Science LNCS 2866, pp. 51-59 (2003). Japanese
Conference on Discrete and Computational Geometry, JCDCG ’02.
D. Avis, K. Fukuda, and S. Picozzi, “On Canonical Representations of Convex Polyhedra,”
ICMS 2002, pp. 350-360, World Scientific (2002).
D. Avis, C. De Simone, and P. Nobili, “Two Conjectures on the Chromatic Polynomial” in
Lecture Notes in Computer Science 1776, pp. 154-162, Springer-Verlag (2000).
D. Avis, K. Hosono, and M. Urabe, “On the Existence of a Point Set with 4 or 5 Interior
Points” in Lecture Notes in Computer Science, ed. J. Akiyama and M. Kano 1763,
pp. 57-64, Springer-Verlag (2000).
D. Avis, “Living with lrs” in Lecture Notes in Computer Science, ed. J. Akiyama and M.
Kano 1763, pp. 47-56, Springer-Verlag (2000).
D. Avis and A. Deza, “On the Boolean Solitaire Cone” in Proc. of the 1st Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, pp. 115-122, Kyoto (1999).
D. MacDonald, D. Avis, and A.C. Evans, “Proximity Constraints in Deformable Models for
Cortical Surface Identification” in Lecture Notes in Computer Science 1496, pp. 650-659,
Springer-Verlag, MICCAI’98 (1998).
T. Ono, Y. Kyoda, T. Masada, K. Hayase, T. Shibuya, M. Inaba, H. Imai, K. Imai, and D.
Avis, “A Package for Triangulations (Video)” in Proc. 12th Annual ACM Symp. on Comput.
Geom., ACM Press, Philadelphia, PA (1996).
D. Avis, P. Bose, T. Shermer, J. Snoeyink, G. Toussaint, and B. Zhu, “On the Sectional Areaof Convex Polytopes,” Proc. 12th ACM Symposium on Computational Geometry,
pp. C11-12, Philadelphia (1996).
D. Avis and D. Bremner, “How Good are Convex Hull Algorithms?” in Proc. 11th Annual
ACM Symp. on Comput. Geom., pp. 20-28 (June 1995).
D. MacDonald, D. Avis, and A. Evans, “Multiple Surface Identification and Matching in
Magnetic Resonance Images,” Visualization in Biomedical Computing, SPIE ’94 (October1994).
D. Avis and K. Fukuda, “A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of
Arrangements and Polyhedra,” Proceedings of the 7th ACM Symposium on Computational
Geometry, pp. 98-104, ACM Press (June 1991).
D. Avis, “On the Complexity of Isometric Embedding in the Hypercube,” Proc. SIGAL Int.
Symp. on Algorithms, pp. 348-357, Springer-Verlag, Tokyo (1990).
D. Avis and R. Wenger, “Algorithms for Line Transversals in Space,” Proceedings of the 3rd
ACM Conference on Computational Geometry, pp. 300-307, Waterloo (1987).
D. Avis and H. ElGindy, “Triangulating Simplicial Point Sets in Space,” Proceedings of the
2nd ACM Conference on Computational Geometry, IBM Yorktown Heights (1986).
A. Somani, V. K. Agarwal, and D. Avis, “Single Fault Diagnosability Concept: System
Level Diagnosis Applied to Large Scale Multiprocessor Systems,” Proc. 1986 Symp. on

-15-

30.

31.
32.

33.

34.
35.

Circuits and Systems, pp. 634-638, San Jose, CA (May 1986).
A. Somani, D. Avis, and V. K. Agarwal, “On the Complexity of Diagnosability and Diagnosis Problems in System Level Diagnosis,” Proc. 1986 Symp. on Fault Tolerant Computing,
Vienna (June 1986).
D. Avis, “On the Partitionability of Point Sets in Space,” Proceedings of the Symposium on
Computational Geometry, pp. 116-121, ACM, Baltimore, MD (1985).
D. Avis and D. Rappaport, “Computing the Largest Empty Convex Subset of a Set of
Points,” Proceedings of the Symposium on Computational Geometry, pp. 161-167, ACM,
Baltimore, MD (1985).
J. Akiyama and D. Avis, “Cube Factors” in Proc. 1st S.E. Asian Graph Theory Colloquium,
ed. A. Dold and B. Eckman 1073, pp. 93-99, Springer Verlag, Lecture Notes in Mathematics (1983).
D. Avis, “Lower Bounds for Geometric Problems,” 18th Allerton Conference, pp. 35-40,
Urbana, IL (1980).
D. Avis, “Two Greedy Heuristics for the Weighted Matching Problem,” Proc. 9th S.E. Conf.
on Comb., Graph Theory, and Computing, pp. 65-76, Congressus Numerantium XXI(1978).

Other Publications
1.
D. Avis and L. Devroye, An analysis of budgeted parallel search on conditional GaltonWatson trees (2017). arXiv:1703.10731.
2.
D. Avis and C. Jordan, mts: A light framework for parallelizing tree search codes (2017).
arXiv:1709.07605.
3.
D. Avis and C. Jordan, A Parallel Framework for Reverse Search Using mts (2016).
arXiv:1610.07735.
4.
D. Avis and C. Jordan, Comparative Computational Results for Some Vertex and Facet Enumeration Codes (2015). arXiv:1510.02545.
5.
D. Avis and S. Moriyama, “On Combinatorial Properties of Linear Program Digraphs,” Les
Cahiers du GERAD G-2008-08 (February 2008 (10 pages)).
6.
Y. Sasaki, T. Ito, H. Imai, and D. Avis, “Bell Inequalities Derived from Combinatorics” in10th Quantum Information Technology Symposium (QIT10) Technical Report QIT2004-12(December 2004.). (In Japanese).
7.
D. Avis, H. Imai, T. Ito, and Y. Sasaki, “Test of Relevance Relation between Bell Inequalities using Nonlinear and Semidefinite Programming” in 11th Quantum Information Technology Symposium (QIT11) Technical Report QIT2004-57 (May 2004). (In Japanese).
8.
D. Avis and V. Chvátal, “On a Conjecture of Baiou and Balinski,” Technical Report
2002-08, DIMACS (2002).
9.
D. Avis, lrs Documentation (June 2001). http://cgm.cs.mcgill.ca /˜avis/lrs.html.
10. D. Avis and Chiu Ming Kong, “Generating Rooted Triangulations with Minimum Degree
Four,” Technical Report SOCS 96.9, McGill University (1996). http://cgm.cs.mcgill.ca/˜avis/doc/avis/AK96a.ps.
11. D. Avis, P. Bose, G. Toussaint, and B. Zhu, “On the Modality of the Sectional Area of Convex Polyhedra,” Technical Report SOCS 93.11, School of Computer Science, McGill University (1993).
12. D. Avis and K. Fukuda, “A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of
Arrangements and Polyhedra” in Tech. Rept. B-237, Tokyo Institute of Technology,, Dept. ofInformation Science (November 1990).
13. D. Avis, “Review of ‘Art Gallery Theorems and Algorithms’ by J. O’Rourke,” Bull. A.M.S.
23, pp. 230-234 (1990).
14. D. Avis, “On the Hamming Cone,” Technical Report 77-5, Dept. of Operations Research,
Stanford University (1977).

-16-