Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home People Profile

David Avis


Home Page:
Office: MC308
Phone: +1-514-398-3737
Fax: +1-514-398-3883

Research Description

My current research interests are in discrete optimization, mixed-integer programming, polyhedral computation and quantum information. I am interested in connections between geometry and optimization.I have been designing and implementing algorithms for generating geometric and combinatorial objects using a technique developped with Komei Fukuda, called reverse search. A typical application of this technique is for generating vertices/facets of polyhedra, which has application to multi-objective optimisation, computing Nash equilibria, Bell inequalities and generating cutting planes for mixed integer programs. Most recently I have been studying polyhedra and related bodies related to quantum computing.

Research Interests

Research Labs


Selected Publications (click link in front of each publication to see bibtex in ASCII format)

[1] Ohsaki, M., Katoh, N., Kinoshita, T., Tanigawa, S., Avis, D., and Streinu, I. Enumeration of optimal pin jointed bistable compliant mechanisms with non-crossing members. J. of Structural and Multidisciplinary Optimization, 2009, v. 37, pp. 645-651.
[2] Avis, D., Fischer, P., Hilbert, A., and Khrennikov, A. Complete account of randomness in the epr-bohm-bell experiment. Proceedings of the conference Foundations of Probability and Physics-5, December 2008. arXiv:0806.0445 (14 pages).
[3] Avis, D., Kaluzny, B., and Titley-Peloquin, D. Visualizing and constructing cycles in the simplex method. Operations Research, 2008, v. 56, pp. 512-518.
[4] Avis, D., Hayden, P., and Savov, I. Distributed compression and multiparty squashed entanglement. Journal of Physics A, 2008, v. 41, p. 11530. arXiv:0707.2792 (25 pages).
[5] Avis, D., Imai, H., and Ito, T. Generating facets of the cut polytope by triangular elimination. Mathematical Programming, 2008, v. 112, pp. 303-325.
[6] Avis, D., Hayden, P., and Savov, I. Multiparty distributed compression of quantum information. In Proceedings of the Second International Conference on Quantum, Nano and Micro Technologies. IEEE Xplore, 2008. 7 pages. (Best paper award).
[7] Avis, D., and Moriyama, S. On combinatorial properties of linear program digraphs. Les Cahiers du Gerad, February 2008, v. G-2008-0. 10 pages.
[8] Avis, D., Katoh, N., Ohsaki, M., Streinu, I., and Tanigawa, S. Enumerating planar minimally rigid graphs. Graphs and Combinatorics, September 2007, 23, pp. 117-134.
[ .pdf ]
[9] Avis, D., and Imamura, T. A list heuristic for vertex cover. Operations Research Letters, March 2007, v. 35, pp. 201-204.
[ .ps ]
[10] Avis, D., and Ito, T. Comparison of two bounds of the quantum correlation set. In First International Conference on Quantum, Nano, and Micro Technologies, ICQNM07, Guadeloupe. IEEE Xplore (Best paper award), January 2007. 3 pages.
[ .pdf ]
[11] Katoh, N., Ohsaki, M., Kinoshita, T., Tanigawa, S., Avis, D., and Streinu, I. Enumeration of optimal pin-jointed bistable mechanisms. In 4th China-Japan-Korea Symp. of Structural and Mechanical Systems, 2007. 6 pages.
[ .pdf ]
[12] Avis, D., and Ito, T. New classes of facets of the cut polytope and tightness of the i_mm22 bell inequalities. Discrete Applied Mathematics, 2007, 155, pp. 1689-99.
[13] Avis, D., Bondy, A., Cook, W., and Reed, B. Vasek chvatal: A short introduction. Graphs and Combinatorics, 2007, v. 23, pp. 41-66.
[14] Avis, D., Imai, H., and Ito, T. On the relationship between convex bodies related to correlation experiments with dichotomic observables. Journal of Physics A, 2006, v. 39, pp. 11283-99.
[ http ]
[15] Ito, T., Imai, H., and Avis, D. Bell inequalities stronger than the chsh inequality for three-level isotropic states. Physical Review A, 2006, v. 73, n. 4, p. 042109(9 pages).
[ http ]
[16] Avis, D., and Ito, T. Polyhedral and semidefinite approaches to classical and quantum bell inequalities. AQIS 2006, 2006, p. 2.
[ .pdf ]
[17] Avis, D., and Deza, A. Un des problemes delectables de claude berge. Discrete Mathemetics, 2006, v. 303, pp. 2299-2302.
[ .pdf ]
[18] Avis, D., Hasegawa, J., Y.Kikuchi, and Sasaki, Y. Quantum protocol to win the graph colouring game on all hadamard graphs. Proceedings of the IEICE, 2005, v. E89A, pp. 1378-81.
[ http ]
[19] Avis, D., Imai, H., Ito, T., and Sasaki, Y. Two-party bell inequalities derived from combinatorics via triangular elimination. Journal of Physics A, 2005, v. 38, n. 50.
[ http ]
[20] Avis, D., Simone, C. D., and Reed, B. On the fractional chromatic index of a graph and its complement. Operations Research Letters, 2005, v. 33, pp. 385-388.
[ .pdf ]
[21] Avis, D., and Ito, T. New classes of facets of the cut polytope and tightness of the i_mm22 bell inequalities. Proceedings of the 4th Japan-Hungarian Symposium on Discrete Mathematics and its Applications, June 2005, p. 12 pages.
[ http ]

Last Update:   2013/08/05 08:32:32.638 GMT-4