Algorithms for High Dimensional Computational Geometry

Kyoto University, 2005                                         Lecture dates: April 13, 14, 20, 21, May 11, 18, 25, 26,  June 1, 8

In the first part of the course we will consider algorithms for various problems related to the computation of convex hulls in high dimensions.
Although the material is "classical", we will look at it in a new way that emphasizes the geometric aspect.
The second part of the course deals with some new applications: computing Nash equilibria for cooperative games, and  Bell inequalities used in quantum information processing.

Instructor:                 David Avis, avis@cs.mcgill.ca            
Teaching Assistant:    Raymond Putra, raymond@kuis.kyoto-u.ac.jp          Raymond's course home page

Requirements:  (Revised April 20)

Each student will prepare complete lecture notes (in English!) for one lecture using latex, and a standard template that Raymond has provided on his course home page above.

Figures should be included in the document using .eps format. I recommend you do this within two weeks of the lecture.
Each student will also choose 5 exercises, at most one from any lecture, that are listed on Raymond's course home page.
The final date for handing in all work is June 30, 2005.
Completed sets of notes will be posted on this web site. A brief summary will be placed here after each lecture.

Some reading items:

1. Solving Inequalities and Farkas' Lemma Made Easy, Avis and Kaluzny,  here. AMS Monthly, 2004 (111)152-7.
2. Visualizing and Constructing Cycles in the Simplex Method,  Avis,  Kaluzny and Titley-Peloquin,  here. GERAD Report G-2005-33.
3. Double Description Method Revisited, by K. Fukuda is here.
    Beneath and Beyond Revisited by M. Joswig is here
4. lrs home page (see Theoretical Description) here.
5. Nash equilibria.  von Stengel's survey here. Supplemental notes here.
7. John Milnor's review in the Notices of the AMS of the book "A Beautiful Mind", by  Sylvia Nasar is here.
8. Bell Inequalities: Avis, Imai, Ito, Sasaki: here.
9. General background reference: Lectures on Polytopes by G. Ziegler (1995).
10. Bell's Theorem, from Physics Virtual Bookshelf. The Magic Square, by P. Aravind.
11. Cleve et al., Consequences and limits of non-local strategies,  http://arxiv.org/abs/quant-ph/0404076
       A game based on the triangle inequality is given by Schmelzer.
12. Nash and Correlated Equilibria, I. Gilboa and E. Zemel  is here.
      Megiddo's paper.

Lecture Summaries and Exercises:

April 13: Introduction to high dimensional computing. Affine flats (points, lines, planes,...) V- and H- representation.
Finding a point in a flat. Polyhedra: V- and H- representations and convex hull problem (vertex enumeration variant).
How to find a point in a polyhedron. Read: Item 1.

April 14: The smallest subscript rule is used to give a simple finite algorithm to find a solution to a system of inequalities
Ax<=b, x>=0, or a certificate of infeasibility. We proved Farkas' lemma: The system is infeasible iff there is a vector y>=0
s.t. y^T A >=0 and yb<0. We used Bohdan's pivoting applet. We saw that if the pivots are not chosen carefully, a cycle can occur. Read Item 2.

Exercises:
1.Modify the algorithm to handle cases (a) Ax<=b and (b) Ax=b, x>=0. Try to find variants of Farkas' lemma
for these cases.
2. Try to construct your own cycle

April 20: Complexity issues. Other methods for finding a solution to a system of inequalities:
1. Ellipsoid method (Khachicyan, 1979). 2. Fourier Elimination (Fourier, 1827)(see item 9, ch. 1) 3. Megiddo's technique (Megiddo, 1984).
Interior point methods, such as the ellipsoid method, run in polynomial time, but not strong polynomial time.
The other methods are all super polynomial. Introduction to the vertex enumeration problem via graph search.
Read: One of the papers in item 3.

April 21: The details of the adjacency oracle for feasible dictionaries. Improvement using lexicographic ratio test.
DFS for vertex enumeration. The size of the output: upper bound theorem (see 9, ch8.4).
Reverse search (see tutorial ). Read: Item 4, Theoretical Description.

May 11: Introduction to quantum mechanics and Bell's theorem. Lecture given by Raymond Putra. Read: Item 10.

May 18: We proved two important theorems. The Farkas-Minkowski-Wely theorem that states that a polyhedron P given by and H-representation is equal to the convex hull of its vertices. (We proved this by assuming a point in P not in the CH, using Farkas Lemma to get a separating plane, then the simplex method to get a missing vertex - a contradiction.) We also proved that the facet enumeration problem for polytopes containing the origin is equivalent to a vertex enumeration problem on the same input, using the duality between vertex v and inequality vx <= 1. Read: Class notes when they are ready.

May 25: First we saw that the cut polytope describes the correlations between binary valued random variables. Facets of the cut polytope can be obtained by a facet enumeration of the known vertices (see exercise from May 18). These facets can be used to show that certain correlations are not possible. We considered a bipartite setting where n random variables belong to each party.
To get Bell inequalities, we project out correlations between measurements by a single party. We can find these inequalities by facet enumeration on the set of cut vectors with the projected coordinates missing. For n=2 we get the CHSH inequality, and non-negativity.
Read: Item 8 above.

May 26: We considered a game on CHSH inequalities, where Alice and Bob receive bits a, b respectively and answer with bits u and v.
They win if a ^ b =  u exor v. Alice and Bob cannot communicate once the game starts, but can agree any strategy in advance.
We saw that if the bits a and b are uniform random, a probablity of win of .75 can be obtained (eg: by both replying zero always).
Ex: This strategy can be defeated by Charlie if he switches to a=1=b always. Show (in spite of what I said in class) that there is
a probabilistic (classical) strategy for Alice and Bob that gives this winning probability, no matter what Charlie does.
We saw that if Alice and Bob share a random qbit they can improve their winning probability to .8535...
We discussed distributed proof systems for proving a graph is k colourable. Using a quantum strategy we can 'prove' this even when the graph is not k colourable! Read: Item 11.
Correction: When |psi> =  ( |00> - |11>)/sqrt(2)  and we measure the two qbits with an angle alpha displacement, the two results P, Q
satisfy Pr(P exor Q = 1) = sin(alpha)^2.
Some machines that can transmit qbits up to 100km are for sale: http://www.idquantique.com/products/clavis.htm
                                                                                                  http://www.magiqtech.com/
June 1: Two person non-cooperative games. We defined Nash equilibria (NE) and developed a non-linear system of equations for which the solutions are the NE. Finding all NE is NP-hard (Gilboa-Zemel, 1988). We developed an algoriithm for finding all equilibria by enumerating vertices of two polyhedra, and by then checking the non-linear complementary slackness condition for each pair of vertices.
An improved algorithm interleaved the two vertex enumeration algorithms. An implementation can be found at
http://cgm.cs.mcgill.ca/~avis/nashlrs.tar
See the README to get instructions for using the two programs setupnash and nash (needed for exercise.)
Read: Item 5.

June 8: Prisoner's dilemna as an example of interleaved vertex enumeration.
Giboa and Zemel's proof (1988) that finding a NE with at least a payoff of r for each player is NP-hard.
Corollary: It is NP-complete to decide if a bi matrix game has two or more NE.
We also formulated CHSH as a classical game.
We showed that there is no mixed strategy for Alice and Bob to guarantee a positive payoff against Charles unless they share some additional information
(such as a random string or qbits).
Read  Item 12.

P.S.
Megiddo's proof that "if it is NP-hard to find a Nash Equilibrium then NP =coNP" ( Proposition 3.2 )
The argument is easy: if finding a NE is NP-hard, then and oracle for NE can be used to decide if a formula for SAT is satisfiable or not.
But an oracle for NE can be replaced by a non-deterministic algorithm for NE that guesses an equilibrium pair (x,y).
Such a pair can be verified to be a NE in polynomial time by checking the conditions discussed on June 1.
 So even an unsatisfiable formula can be verified non-deterministically in polynomial time. Hence NP=coNP.

Thanks for coming and have a nice summer!