Publications On-line              (For a complete publication list see CV )

2014

D. Avis and H. Tiwary, "A Generalization of  Extension Complexity that Captures P", February 2014 arXiv:1402.5950

2013

D. Avis and G. Roumanis, "A Portable Parallel Implementation of the lrs Vertex Enumeration Code", COCOA 2013, LNCS 8287 (2013) 414-29 pdf

D. Avis, K. Iwama and D. Paku, "Reputation Games for Undirected Graphs", May 2012, Discrete Applied Mathematics (to appear)  arXiv:1205.6683v1

D. Avis and H. Tiwary, "On the Extension Complexity of Combinatorial Polytopes", Mathematical Programming B (to appear) ICALP (1) 2013 57-68. arXiv:1302.2340

D. Avis and O. Friedmann, "An Exponential Lower Bound for Cunningham's Rule", arXiv:1305.3944

2012

Y. Aoshima, D. Avis, T. Deering, Y. Matsumoto, S. Moriyama, "On the Existence of Hamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes", Discrete Applied Mathematics, online June 20, 2012,     arXiv:1110.3014v2

D. Avis, H. Miyata and S. Moriyama, "Families of Polytopal Digraphs that do not Satisfy the Shelling Property", Oct. 2011,   arXiv:1110.3078v1
  CGTA 46 (2013) 382-393, (online Nov. 11, 2012)         

2011   

M. Cuturi, D. Avis, "Ground Metric Learning", JMLR (to appear) pdf 

D. Avis, K. Iwama and D. Paku, "Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs", ISAAC 2011: 415-424 pdf

2010

D. Avis, P. Hayden and M. Wilde,  "Leggett-Garg Inequalities and the Geometry of the Cut Polytope," arXiv:1004.3818
Physical Review A 82, 030102(R) (2010)

D. Avis, "Those ubiquitous cut polyhedra". CCCG 2010: 25 pdf

D. Avis, "Recollections on the Discovery of the Reverse Search Technique", LA Symposium 55(2010) 14-16  pdf

2009

D. Avis, L. Devroye and K. Iwama, "The Locker Problem with Empty Lockers", World Academy of Science, Engineering and Technology 60 (2009) pdf

D. Avis, S. Moriyama and M. Owari, "From Bell Inequalities to Tsirelson's Theorem", IECIE E92-A (2009)1254-67 pdf

D. Avis and S. Moriyama, "On Combinatorial Properties of Linear Program Digraphs", in Polyhedral Computation, CRM-AMS Proceedings,  48(2009) 1-14 (Les Cahiers du Gerad, G-2008-08) pdf

D. Avis, G. Rosenberg, R. Savani, B. von Stengel, "Enumeration of Nash Equilibria for Two-Player Games", Economic Theory 42(2009) 9-37  pdf

D. Avis, H. Miyata, S. Moriyama, " A Family of Polytopal Digraphs that do not Satisfy the Shelling Property", 6-th Japanese-Hungarian Symposium, June 2009,11 pages pdf  

D. Avis and A. Broadbent, "The Quantum Locker Puzzle", ICQNM09, Cancun, February 2009, 4 pages. pdf

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(2009) 645-65. pdf

2008

D. Avis, B. Kaluzny and D. Titley-Peloquin, "Visualizing and Constructing Cycles in the Simplex Method",  Operations Research  vol 56, 512-518(2008). pdf

D. Avis, P. Hayden and I. Savov, "Distributed Compression and Multiparty Squashed Entanglement", J. Phys. A Math. Theor. 41, 115301, 25 pages,(2008), pdf

D. Avis, P. Fischer, A. Hilbert, A. Khrennikov, "Complete account of randomness in the EPR-Bohm-Bell experiment", Vaxjo Conference on Foundations of Probability and Physics-5, August 2008, 14 pages. http://arxiv.org/abs/0806.0445

D. Avis and B. Kaluzny, "Computing Disjoint Paths on Polytopes",  Journal of Combinatorial Optimization 16 (2008) 328-343.   pdf

D. Avis, H. Imai and  T. Ito,"Generating Facets of the Cut Polytope by Triangular Elimination", Mathematical Programming 112(2008)303-25.  pdf

D. Avis, N. Katoh, M. Ohsaki, I. Streinu and S. Tanigawa, "Enumerating Constrained Non-crossing Minimally Rigid Frameworks", Discrete and Computational Geometry 40 (2008) 31-46  pdf

D. Avis, P. Hayden and I. Savov, "Multiparty Distributed Compression of Quantum Information", ICQNM08, Martinique, February 2008, 7 pages. pdf

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 (2007) 1689-99,  pdf

D. Avis, "Quantum Correlations: From Bell inequalities to Tsirelson's Theorem", Proc. International Workshop on Combinatorics 2007, Yokohama, June 2007. pdf

D. Avis, N. Katoh, M. Ohsaki, I. Streinu and S. Tanigawa, "Enumerating Planar Minimally Rigid Graphs",  Graphs and Combinatorics 23 (2007) 117-134.  pdf

D.Avis, A. Bondy, W. Cook and B. Reed, "Vasek Chvatal: A Short Introduction", Graphs and Combinatorics 23 (2007) 41-66. pdf

D. Avis and T. Ito, "Comparison of Two Bounds of the Quantum Correlation Set", ICQNM07, Guadeloupe, January 2007. pdf

D. Avis and T. Imamura, "A List Heuristic for Vertex Cover", Operations Research Letters 35 (2007) 201-4.   ps

2006

D. Avis and A. Deza, "Un des "problemes delectables" de Claude Berge",  Discrete Mathematics 306(2006)2299-2302   pdf

D. Avis and T. Ito, "Polyhedral and Semidefinite Approaches to Classical and Quantum Bell Inequalities", AQIS 2006, Beijing, Sep 2006, 2 pages pdf

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 and Mechanical Systems, Kunming, Nov 2006, 6 pages. pdf

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 (2006) 11283-99, pdf

T. Ito, H. Imai and D. Avis, "Bell Inequalities Stronger than the CHSH Inequality for Three-level Isotropic States", Physical Review A 73(4) (2006)  042109(9 pages)       pdf

D. Avis, J. Hasegawa, Y. Kikuchi and Y. Sasaki, " A Quantum Protocol to Win the Graph Colouring Game on all Hadamard Graphs",  Proceedings of the IEICE E89A (2006) 1378-81.   pdf

2005

D. Avis, H. Imai, T. Ito and Y. Sasaki, "Two-party Bell Inequalities Derived from Combinatorics via Triangular Elimination", August 2005, 20 pages,  Journal of Physics A 38(50) (2005)10971-10987,  pdf


D. Avis,  C. De Simone,  and B. Reed, "On the fractional chromatic index of a graph and its complement",
Operations Research Letters, vol 33, pp. 385-388 (2005) pdf

2004             

D. Avis, H. Imai, T. Ito and Y. Sasaki, "Deriving Tight Bell Inequalities for 2 Parties with Many 2-valued Observables from Facets of Cut Polytopes", 24 pages, April 2004.    http://arxiv.org/abs/quant-ph/0404014

D. Avis and B. Kaluzny, "Solving Inequalities and Farkas' Lemma Made Easy", AMS Mathematical Monthly, vol 111, pp 152-157(2004)    ps

2003

D. Avis and J. Umemoto, "Stronger Linear Programming Relaxations for Max -Cut", Mathematical Programming, vol. B 97, pp. 451-469 (2003).   ps

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).  ps

2002

D. Avis, K. Fukuda and S. Picozzi, "On Canonical Representations of Convex Polyhedra", Mathematical Software,
ICMS 2002, Ed. A. Cohen, X-S Gao, N. Takayama, World Scientific, pp.350-360 (2002)       ps

D. Avis and V. Chvatal, "On a Conjecture of Baiou and Balinski", DIMACS Technical Report 2002-08, March 2002. ps
       
D. Avis, C. De Simone, P. Nobili, "On the Chromatic Polynomial of a Graph", Mathematical Programming,  vol B 92, pp. 439-452(2002)       ps

2001

D. Avis, K. Hosono, M. Urabe, "On the Existence of  a Point Subset with a Specified Number of  Interior Points," Discrete Mathematics, Vol. 241, pp. 33-40. (2001)     ps

D. Avis and A. Deza, "On the Solitaire Cone and its Relationship to Multicommodity Flows" Mathematical Programming, Vol. 90, pp. 27-57 (2001).    ps.           
D. Avis and A. Deza, "On the Binary Solitaire Cone", Discrete Applied Mathematics, Vol. 115, pp. 3-14 (2001)   ps         

2000

D. Avis and L. Devroye, "Estimating the Number of Vertices of a Polyhedron," Information Processing Letters, Vol 73, pp. 137-143. ps

D. Avis, K. Hosono, M. Urabe, "On the Existence of  a Point Subset with a 4 or 5  Interior Points," Lecture Notes in Computer Science, Vol. 1763, pp. 57-64 (2000)     ps.
 D. Avis, S. Onn,  and A. Deza, "A Combinatorial Approach to the Solitaire Game",  IEICE Trans. on Fund. of Electronics, Communications and Computer Sciences  E83-A, pp. 656-661(2000). .ps

D. Avis,  "Living with lrs," Lecture Notes in Computer Science, Vol. 1763, pp. 47-56 (2000)  ps

D. Avis,  "lrs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm," In: Polytopes - Combinatorics and Computation, G. Kalai & G. Ziegler eds., Birkhauser-Verlag, DMV Seminar Band 29, pp. 177-198 (2000)  .ps

1998

D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration Algorithm," Optimization Methods and Software,  Vol. 10, pp.107-124 (1998)  ps.

1997

D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol. 7, pp. 265-301 (1997). ps

1996

D. Avis and K. Fukuda, "Reverse Search for Enumeration," Discrete Applied Math, Vol. 6, pp. 21-46 (1996). pdf.

D. Avis, "Generating Rooted Triangulations Without Repetitions," Algorithmica, Vol. 16, pp.618-632(1996).pdf.

D. Avis and Chiu Ming Kong, "Generating Rooted Triangulations with Minimum Degree Four," Technical Report, Vol. SOCS 96.9, McGill University, (1996). ps.

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). ps.

1995

D. Avis and D. Bremner, "How Good are Convex Hull Algorithms?," pp. 20-28 in Proc. 11th Annual ACM Symp. on Comput. Geom., (June 1995). .ps

.D. Avis and M. Houle, "Computational Aspects of Helly's Theorem and its Relatives," International Journal of Computational Geometry & Applications, Vol. 5, pp. 357-367 (1995). ps

1994

.D. Avis and H. Maehara, "Metric Extensions and the L1-Hierarchy," Discrete Mathematics, Vol. 131, pp. 17-28 (1994). ps
.D. Avis, "A C Implementation of the Reverse Search Vertex Enumeration Algorithm," in RIMS Kokyuroku 872, ed. H. Imai, Kyoto University (May 1994). ps

1993

.D. Avis and V. P. Grishukhin, "A Bound on the k-gonality of Facets of the Hypermetric Cone and Related Complexity Problems," Computational Geometry: Theory and Applications, Vol. 2, pp. 241-254 (1993). ps
.D. Avis, "The m-Core Properly Contains the m-Divisible Points in Space," Pattern Recognition Letters, Vol. 14, pp. 703-705 (1993). ps

1992

.D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra," Discrete and Computational Geometry, Vol. 8, pp. 295-313 (1992).ps

1991

.D. Avis and M. Deza, "The Cut Cone, L1-Embedability, Complexity and Multicommodity Flows," Networks, Vol. 21, pp. 595-617 (1991). ps
.D. Avis, P. Erdos, and J. Pach, "Distinct Distances Determined by a Subset of Points in Space," Computational Geometry: Theory and Applications, Vol. 1, pp. 1-12 (1991). ps

1990

.D. Avis, "On the Complexity of Isometric Embedding in the Hypercube," Proc. SIGAL Int. Symp. on Algorithms, pp. 348-357 Springer-Verlag, (1990). ps
.D. Avis and M. Doskas, "Algorithms for High Dimensional Stabbing Problems," Discrete Applied Math., Vol. 27, pp. 39-48 (1990). ps

1989

.D. Avis and Mutt, "All the Facets of The Six Point Hamming Cone," European Journal of Combinatorics, Vol. 10, pp. 309-312 (1989). ps
.D. Avis, J-M. Robert, and R. Wenger, "Lower Bounds for Line Stabbing," Information Processing Letters, Vol. 33, pp. 59-62 (1989). ps

1988

D. Avis, P. Erdos, and J. Pach, "Repeated Distances in Space," Graphs and Combinatorics, Vol. 4, pp. 207-217 (1988). ps

D. Avis, B. K. Bhattacharya, and H. Imai、"Computing the Volume of the Union of Spheres", The Visual Computer, (1988) 3:323-328 pdf
.D. Avis and C. W. Lai, "The Probabilistic Analysis of a Heuristic for the Assignment Problem," SIAM Journal on Computing, Vol. 17, pp. 732-741(1988).ps

1987

.D. Avis and R. Wenger, "Algorithms for Line Transversals in Space," Proceedings of the 3rd ACM Conference on Computational Geometry, pp. 300-307 (1987). ps
.D. Avis and H. ElGindy, "Triangulating Point Sets in Space," Discrete and Computational Geometry, Vol. 2, pp. 99-111 (1987). ps
.D. Avis, "Space Partitioning and its Application to Generalized Retrieval Problems," pp. 237-249 in Foundations of Data Organization, ed. S.Ghosh, Y. Kambayashi, K. Tanaka, Plenum Press (1987). ps

1986

D. Avis, "Diameter Partitioning," Discrete and Computational Geometry, Vol. 1, pp. 265-276 (1986). ps

D. Avis and D. Rappaport, "Computing the Largest Empty Convex Subset of a Set of Points" Proc. 1st ACM Symposium on Computational Geometry, pp. 161-167, 1985.pdf

1981

D. Avis, "Hypermetric Spaces and the Hamming Cone," Can. J. Math, Vol 33, pp 795-802, 1981.  pdf

1980

D. Avis, Lower Bounds for Geometric Problems, 18th Allerton Conference, pp. 35-40, Urbana, IL (1980). pdf

D. Avis,  "A Note on Some Computationally Difficult Set Covering Problems, " Mathematical Programming 18 (1980) 138-145. pdf

D. Avis,  "On the Extreme Rays of the Metric Cone," Can. J. Math, Vol 32, pp 126-144, 1980.  pdf

D. Avis and M. Newborn, "On Pop Stacks in Series," Utilitas Mathematica Vol 19, pp129-40 pdf

1978

D. Avis and V. Chvatal, "Notes on Bland's Pivoting Rule," Math Prog. Study, Vol 8, pp.24-34, 1978  pdf

.
.