From Bell Inequalities to Tsirelson's Theorem: A Survey (2008)
Avis, David, Moriyama, Sonoko, Owari, Masaki
The first part of this paper contains an introduction to Bell inequalities and Tsirelson's theorem for the non-specialist. The next part gives an explicit optimum construction for the "hard" part of...
The Quantum Locker Puzzle (2008)
The locker puzzle is a game played by multiple players against a referee. It has been previously shown that the best strategy that exists cannot succeed with probability greater than 1-ln2 \approx...
Multiparty distributed compression of quantum information (2008)
Abstract—We study a protocol in which many parties use quantum communication to transfer a shared state to a receiver without communicating with each other. This protocol is a multiparty version of...
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained...
Complete account of randomness in the EPR-Bohm-Bell experiment (2008)
Avis, David, Fischer, Paul, Hilbert, Astrid, Khrennikov, Andrei
We show that paradoxical consequences of violations of Bell's inequality are induced by the use of an unsuitable probabilistic description for the EPR-Bohm-Bell experiment. The conventional...
Solving inequalities and proving Farkas’ lemma made easy (2008)
David Avis, Bohdan Kaluzny, David Avis, Bohdan Kaluzny
Les textes publiés dans la série des rapports de recherche HEC n’engagent que la responsabilité deleurs auteurs. La publication de ces rapports de recherche bénéficie d’une subvention du...
Visualizing and constructing cycles in the simplex method, GERAD (2008)
D. Avis, B. Kaluzny, David Avis, Bohdan Kaluzny
Les textes publiés dans la série des rapports de recherche HEC n’engagent que la responsabilité de leurs auteurs. La publication de ces rapports de recherche bénéficie d’une subvention du...
A list heuristic for vertex cover (2008)
We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most √ ∆/2 + 3/2 for...
Enumeration of Optimal Pin-Jointed Bistable Compliant Mechanisms (2008)
Naoki Katoh, Makoto Ohsaki, Takuya Kinoshita, Shin-ichi Tanigawa, David Avis, Ileana Streinu
Recently, a new type of mechanism called compliant mechanism has been developed and applied mainly in the field of micro-mechanics. A compliant mechanism has flexible parts to stabilize the...
SPACE PARTITIONING AND ITS APPLICATION TO GENERALIZED RETRIEVAL PROBLEMS (2008)
Afundamental problem in the area of database systems is the retrieval ofdata satisfying certain criteria. The simplest such problem is the retrieval ofdata based on a single key, and a comprehensive...
ALGORITHMS FOR LINE TRANSVERSALS IN SPACE Preliminary Report (2008)
Algorithms are developed for determining if a set of polyhedral objects in R 3 can be intersected by a common transversal (stabbing) line. It can be determined in O(n) time if a set of n lines in...
Afinite semimetric is L 1 − embeddable if it can be expressed as a nonnegative combination of Hamming semimetrics. Afinite semimetric is called hypermetric if it satisfies the (2k + 1) − gonal...
Enumerating constrained non-crossing minimally rigid frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Solving Inequalities and Proving Farkas's Lemma Made Easy (2007)
Every college student has learned how to solve a system of linear equations, but how many would know how to solve Ax b for x 0 or show that there is no solution? Solving a system of linear...
Generating Rooted Triangulations with Minimum Degree Four (2007)
A graph is a triangulation if it is planar and every face is a triangle. A triangulation is rooted if the external triangular face is labelled. Two rooted triangulations with the same external face...
On the existence of a point subset with 4 or 5 interior points (2007)
David Avis, Kiyoshi Hosono, Masatsugu Urabe
An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k 1, let h(k) be the smallest integer such that every...
David Avis, Thomas C. Shermer, Jack Snoeyink, Godfried Toussaint, Binhai Zhu
Let K be a convex polytope in R d, let h(x) be the hyperplane consisting of all points with first coordinate equal to x, and let A(x) be the area (or volume, if d? 3) of the section K "...
On a Conjecture of Baïou and Balinski (2007)
We disprove a conjecture of Baou and Balinski concerning a variation on the Birkho-von Neumann theorem.
On the binary solitaire cone David Avis (2007)
Antoine Deza Mcgill, David Avis, Antoine Deza
The solitaire cone SB is the cone of all feasible fractional Solitaire Peg games. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg...
Distributed Compression and Multiparty Squashed Entanglement (2007)
Avis, David, Hayden, Patrick, Savov, Ivan
We study a protocol in which many parties use quantum communication to transfer a shared state to a receiver without communicating with each other. This protocol is a multiparty version of the fully...
Enumerating non-crossing minimally rigid frameworks (2007)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Quantum Correlations: From Bell inequalities to Tsirelson’s theorem (2007)
The cut polytope and its relatives are good models of the correlations that can be obtained between events that can be well described by classical physics. Bell’s Theorem and subsequent experiments...
Quantum Correlations: From Bell inequalities to Tsirelson’s theorem (2007)
The cut polytope and its relatives are good models of the correlations that can be obtained between events that can be well described by classical physics. Bell’s Theorem and subsequent experiments...
Comparison of two bounds of the quantum correlation set (2007)
Abstract — From a geometric viewpoint, quantum nonlocality between two parties is represented as the difference of two convex bodies, namely the sets of possible results of classical and quantum...
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2006)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained...
Avis, David, Imai, Hiroshi, Ito, Tsuyoshi
In this paper we explore further the connections between convex bodies related to quantum correlation experiments with dichotomic variables and related bodies studied in combinatorial optimization,...
Generating facets for the cut polytope of a graph by triangular elimination (2006)
Avis, David, Imai, Hiroshi, Ito, Tsuyoshi
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Motivated by the work of Kawamoto et al. [5], who first suggested the use of graph enumeration techniques as an engineering tool for finding an optimum mechanism design, we give an algorithm for...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Abstract. We present an algorithm for enumerating without repetitions all the planar (noncrossing) minimally rigid (Laman) graphs embedded on a given generic set of n points. Our algorithm is based...
A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs (2006)
AVIS, David, HASEGAWA, Jun, KIKUCHI, Yosuke, SASAKI, Yuuya
This paper deals with graph colouring games, an example of pseudo-telepathy, in which two players can convince a verifier that a graph G is c-colourable where c is less than the chromatic number of...
A quantum protocol to win the graph colouring game on all Hadamard graphs (2005)
Avis, David, Hasegawa, Jun, Kikuchi, Yosuke, Sasaki, Yuuya
This paper deals with graph colouring games, an example of pseudo-telepathy, in which two provers can convince a verifier that a graph $G$ is $c$-colourable where $c$ is less than the chromatic...
Bell inequalities stronger than the CHSH inequality for 3-level isotropic states (2005)
Ito, Tsuyoshi, Imai, Hiroshi, Avis, David
We show that some two-party Bell inequalities with two-valued observables are stronger than the CHSH inequality for 3 \otimes 3 isotropic states in the sense that they are violated by some isotropic...
New Classes of Facets of Cut Polytope and Tightness of I_{mm22} Bell Inequalities (2005)
The Grishukhin inequality Gr_7 is a facet of CutP_7, the cut polytope on seven points, which is ``sporadic'' in the sense that its proper generalization has not been known. In this paper, we extend...
Two-Party Bell Inequalities Derived from Combinatorics via Triangular Elimination (2005)
Avis, David, Imai, Hiroshi, Ito, Tsuyoshi, Sasaki, Yuuya
We establish a relation between the two-party Bell inequalities for two-valued measurements and a high-dimensional convex polytope called the cut polytope in polyhedral combinatorics. Using this...
Visualizing and Constructing Cyclesin The Simplex Method (2005)
"Cycling is certainly not completely understood. "- Hoffman, 1951. Abstract Most examples of cycling in the simplex method are given without explanation of how they wereconstructed....
Two-party Bell inequalities derived from combinatorics via triangular elimination (2005)
David Avis, Hiroshi Imai, Tsuyoshi Ito, Yuuya Sasaki
Bell inequalities, originally introduced as a method to prove that some quantum states show nonlocal behavior, are now studied as a method to capture the extent of the nonlocality of quantum states....
Computing Disjoint Paths on Polytopes (2005)
Abstract The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone pathsfrom the source to the sink of a polytopal digraph consisting of the set of vertices and...
Computing Disjoint Paths on Polytopes (2005)
D. Avis, B. Kaluzny, David Avis, Bohdan Kaluzny
Les textes publiés dans la série des rapports de recherche HEC n’engagent que la responsabilité de leurs auteurs. La publication de ces rapports de recherche bénéficie d’une subvention du...
Avis, David, Imai, Hiroshi, Ito, Tsuyoshi, Sasaki, Yuuya
Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, I_{mm22}, and CGLMP inequalities. This paper presents a large number of new families...
David Avis, Hiroshi Imai, Tsuyoshi Ito, Yuuya Sasaki
Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, Imm22, and CGLMP inequalities. This paper presents a large number of new families of...
On the Fractional Chromatic Index of a Graph and its Complement (2004)
David Avis, Caterina De Simone, Bruce Reed
The chromatic index χ e(G) ofanundirected graph G is the minimum number of matchings needed to partition its edge set. Let Δ(G) denote the maximum vertex degree of G, and let G denote the...
On the Complexity of Testing Hypermetric, Negative Type, (2003)
Hypermetric inequalities have many applications, most recently in the approximate solution of max-cut problems by linear and semide nite programming. However, not much is known about the separation...
Stronger Linear Programming Relaxations of Max-Cut (2002)
We consider linear programming relaxations for the max cut problem in graphs, based on k- gonal inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1 + 1=k and...
On Canonical Representations of Convex Polyhedra (2002)
David Avis Komei, David Avis, Komei Fukuda, Stefano Picozzi
Every convex polyhedron in the Euclidean space R admits both H-representation and Vrepresentation.
On the Solitaire Cone and Its Relationship to (2001)
The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to...
David Avis, Antoine Deza, Shmuel Onn
Abstract. The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning...
David Avis, Antoine Deza, Shmuel Onn
Abstract. The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning...
On the Existence of a Point Subset with a Specified Number of Interior Points (2000)
David Avis, Kiyoshi Hosono, Masatsugu Urabe
An interior point of a finite point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k 1, let g(k) be the smallest integer such that every set of...
This paper describes the development of lrs, animplementation of the reverse search method to the vertex enumeration/convex hull problem for convex polyhedra. We describe an important and difficult...
Automated 3-D Extraction of Inner and Outer Surfaces of Cerebral Cortex from MRI (2000)
David Macdonald, Noor Kabani, David Avis, Alan C. Evans
Automatic computer processing of large multidimensional images such as those produced by magnetic resonance imaging (MRI) is greatly aided by deformable models, which are used to extract, identify,...
Estimating The Number Of Vertices Of A Polyhedron (2000)
Given a polyhedron P by a list of inequalities we develop unbiased estimates of the number of vertices and bases of P . The estimates are based on applying tree estimation methods to the reverse...
Unoriented Theta-Maxima In The Plane: Complexity And Algorithms (1998)
David Avis, Bryan Beresford-smith, Luc Devroye, Hossam Elgindy, Eric Guévremont, Ferran Hurtado, ...
We introduce the unoriented Theta-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented Theta-maximum of a set of...
Computational Experience with the Reverse Search Vertex Enumeration Algorithm (1998)
Dedicated to Professor Masao Iri on the occasion of his 65th birthday This paper describes computational experience obtained in the development of the lrs code, which uses the reverse search...
lrs: ARevised Implementation of the Reverse Search Vertex Enumeration Algorithm (1998)
This paper describes an improved implementation of the reverse search vertex enumeration/convex hull algorithm for d-dimensional convex polyhedra. The implementation uses a lexicographic ratio test...
How good are convex hull algorithms (1997)
A convex polytope is the bounded intersection of finite set H of halfspaces. A classic theorem of convexity theory is that every convex polyhedron can be expressed as the convex hull of its set V of...
How good are convex hull algorithms (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P, or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to...
How Good are Convex Hull Algorithms? (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
School Of, David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
DISTINCT DISTANCES DETERMINED BY SUBSETS OF A POINT SET IN SPACE (1997)
We answer the following question posed by Paul Erd"os and George Purdy: determine the largest number f d(k) = f with the property that almost all k-element subsets of any n-element set in R...
David Avis, Raimund Seidel Y, David Bremner, Fachberich Informatik
A convex polytope P can be speci ed in two ways: as the convex hull of the vertex set V of P,orastheintersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is to...
The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to...
Reverse search for enumeration (1996)
The reverse search technique has been recently introduced by the authors for efficient enumeration of vertices of polyhedra and arrangements. In this paper, we develop this idea in a general...
Generating rooted triangulations without repetitions (1996)
We use the reverse search technique to give algorithms for generating all graphs on n points that are two and three connected planar triangulations with r points on the outer face. The triangulations...
ACImplementation of the Reverse Search Vertex Enumeration Algorithm (1993)
This report documents a C implementation of the reverse search vertex enumeration algorithm for convex polyhedra of Avis and Fukuda. The implementation uses multiple precision rational arithmetic and...
Computational Aspects of Helly's Theorem and its Relatives (1991)
This paper investigates computational aspects of the well-known convexity theorem due to Helly, which states that the existence of a point in the common intersection of n convex sets is guaranteed by...
Universite de Paris VII 17, Passage de l’industrie (1990)
A finite metric (or more properly semimetric) on n points is a non-negative vector d = (dij) 1 ≤ i < j ≤ n that satisfies the triangle inequality: dij ≤ dik + d jk. The L 1 (or...
On the complexity of isometric embedding in the hypercube (1990)
Afinite metric is h − embeddable if it can be embedded isometrically in the N-cube (hypercube) for some N. Itisknown that the problem of testing whether ametric is h − embeddable is NP-Complete,...
APivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra (1990)
We present a new piv ot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an...
All the facets of the six point Hamming cone (1989)
A finite semimetric is L¹−embeddable if it can be expressed as a nonnegative combination of Hamming semimetrics. The cone of such semimetrics is called the Hamming cone. A finite semimetric is...
The probabilistic analysis of a heuristic for the assignment problem (1988)
We present a heuristic to solve the m by m assignment problem in O(m 2)time. The assignment problem is formulated as a weighted complete bipartite graph G = (S, T, E) , |S | = |T | = m. For...
Triangulating point sets in space (1987)
Aset P of n points in R d is called simplicial if it has dimension d and contains exactly d + 1extreme points. We show that when P contains n ′ interior points, there is always one point, called a...
We discuss the problem of partitioning a set of points into two subsets with certain conditions on the diameters of the subsets and on their cardinalities. For example, we give an O(n 2 log n)...
An Efficient Algorithm for Decomposing a Polygon into Star-Shaped Polygons (1981)
David Avis, Godfried Toussaint
In this paper we show how a theorem in plane geometry can be converted into an O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency or this new...
An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge (1981)
David Avis, Godfried Toussaint
In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper...
An efficient algorithm for decomposing a polygon into star-shaped pieces (1981)
David Avis, Godfried Toussaint
In this paper we show how a theorem in plane geometry can be converted into an O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency or this new...
Enumeration of Nash equilibria for two-player games
David Avis, Gabriel Rosenberg, Rahul Savani, Bernhard Stengel
Bimatrix game, Nash equilibrium, Linear programming, Complementarity, C72,