CSE logo University of Washington Department of Computer Science & Engineering
 CSE 590z - Theory Seminar, Autumn 2001
  CSE Home     Previous Quarters  About Us    Search    Contact Info 

Time and Location

The seminar meets Tuesdays, 1:30-2:20pm in EE1 037.

Email Archive

Click here to view the archive containing emails sent to cse590z@cs as well as to theory-group@cs.

Description

Proofs from The Book   

This quarter we will be studying some great proofs. Paul Erdos, the famous combinatorialist, used to talk about the notion of a "proof from The Book". According to him, The Book is where God maintains the perfect proofs for mathematical theorems, following the dictum of G.H. Hardy that there is no permanent place for ugly mathematics. Erdos also said that you need not believe in God, but, as a mathematician, you should believe in The Book.

A recent book called Proofs from The Book by Aigner and Ziegler (with collaboration from Paul Erdos just prior to his death in 1997) presents proofs that they believe are indeed proofs from The Book. The theorems proved are in the fields of combinatorics, graph theory, geometry, number theory and analysis.

Our plan for the quarter is to have students present a selection of proofs from this book, preferably of those theorems that have been most useful in computer science (e.g., graph theory and combinatorics). These proofs are relatively short, self-contained nuggets. Only minimal mathematical background is assumed.

There will also be a few outside speakers this quarter talking about their recent research in theoretical computer science.

Schedule

Note for speakers: Please email me (ashish@cs.washington.edu) the details of your talk as soon as you decide. Thanks!

Day Speaker(s) Title
Oct 2 Organizational meeting, video show: "N is a Number: A Portrait of Paul Erdos"
Oct 9 Eric Anderson, Matt Cary, Erik Vee Three Applications of Euler's Formula, PFTB Chapter 10 (abstract)
Oct 16 Nilesh Dalvi, Mausam, Amol Prakash, Sumit Sanghai Cayley's Formula for the Number of Trees, PFTB Chapter 22 (abstract)
Oct 23 ** Eric Allender (Rutgers University) The Circuit Complexity of Division (abstract)
Oct 30 Andrei Alexandrescu, Ashish Sabharwal, Zizhen Yao Completing Latin Squares, PFTB Chapter 23 (abstract)
Nov 6 Nicholas Deibel, Andrew Schwerin, Kevin Sikorski Sperner's Lemma and Two Interesting Applications, PFTB Chapter 20 (abstract)
Nov 13 ** Kamal Jain (Microsoft Research) Equitable, Group Stategyproof Cost Allocations via Primal-Dual-Type Algorithms (abstract)
Nov 20 Janet Davis, Julie Goldberg, Bill Pentney How to Guard a Museum, PFTB Chapter 26
Nov 27 Isaac Kunen, Frank McSherry The Probabilistic Method, PFTB Chapter 30 (abstract)
Dec 4 ** John Dunagan (Department of Mathematics, MIT) Optimal Outlier Removal (abstract)
Dec 11 Stefan Saroiu, Gidon Shavit, Adrien Treuille Three Famous Theorems on Finite Sets, PFTB Chapter 21 (abstract)
Jan ?? Justin Campbell, Jason Hartline, Ed Hong -


Talk Abstracts

Speakers Eric Anderson, Matt Cary, Erik Vee
Title Three Applications of Euler's Formula
Abstract Euler's formula beautifully relates geometry and combinatorics, by giving an algebraic relation between the number of vertices, edges and faces of a planer graph. After proving the formula, we will present as many as three applications (time permitting): arrangements of points in the plane (the Sylvester-Gallai theorem), the monochromatic line theorem, and computing the area of a lattice polygon (Pick's theorem).

Copies of chapter 10 are located on top of the file cabinet on the 4th floor of Sieg.

---------------

Speakers Nilesh Dalvi, Mausam, Amol Prakash, Sumit Sanghai
Title Cayley's Formula for the Number of Trees
Abstract One of the most interesting and difficult problems in graph theory is calculating the number of spanning trees of graphs. We will discuss the special case of a complete graph, where the number of spanning trees is related by the famous Cayley's Theorem. We will cover four different proofs of Cayley's Theorem, using various techniques from Algebra and Combinatorics.

Copies of chapter 22 are located on top of the file cabinet on the 4th floor of Sieg.

---------------

Speaker Eric Allender
Title The Circuit Complexity of Division
Abstract The circuit complexity of addition, subtraction, and multiplication has been well-understood for decades, but the complexity of division had remained something of a mystery. The first breakthough on the division problem occurred in the mid-1980's, when Beame, Cook, and Hoover showed that division can be computed by circuits of logarithmic depth (and in fact division can be computed by threshold circuits of depth O(1)). However, these circuits were somewhat difficult to construct -- and thus it remained an open question if division could be computed in logspace.

The second breakthrough occurred more recently, when Chiu, Davida, and Litow showed that division can be computed in logspace. The circuits that they produce were still not "easy" enough to construct, to be useful in certain applications. More formally, it was still not known if division could be computed in "uniform TC0" (meaning that it was not known if division could be computed by threshold circuits of depth O(1) that are "very easy to construct").

I will report on joint work with Bill Hesse and David Mix Barrington, in which we resolve this question. The presentation will include a very simple division algorithm that can be implemented in logspace.

---------------

Speakers Andrei Alexandrescu, Ashish Sabharwal, Zizhen Yao
Title Completing Latin Squares
Abstract Latin squares are one of the oldest combinatorial objects studied for their interesting properties. To obtain a Latin square, one has to fill the n^2 cells of an (n x n)-square array with the numbers 1, 2, ..., n so that every number appears exactly once in every row and in every column. Suppose someone has already filled in some of the squares with numbers. Can we extend this partial configuration to a complete Latin square? Evans conjecture (1960), settled by Bohdan Smetaniuk in 1981, says that the answer is yes, as long as fewer than n cells are already filled. This result is also tight in the sense that there exists a (trivial) partial configuration with only n already filled cells that cannot be extended to a complete Latin square.

Copies of chapter 23 are located on top of the file cabinet on the 4th floor of Sieg.

---------------

Speakers Nicholas Deibel, Andrew Schwerin, Kevin Sikorski
Title Sperner's Lemma and Two Interesting Applications
Abstract At face value, Sperner's lemma is an obscure and esoteric observation involving double counting and the pigeonhole principle. However, the proof of this lemma is itself a beautiful example of double counting. We will show this proof along with two mathematical puzzles that both have truly elegant solutions due to Sperner's lemma.

Copies of the relevant sections of chapter 21 and descriptions of the puzzles will be available on top of the file cabinet on the 4th floor of Sieg.

---------------

Speaker Kamal Jain (Microsoft Research)
Title Equitable, Group Strategyproof Cost Allocations via Primal-Dual-Type Algorithms
Abstract We build on the well-studied egalitarian cost-sharing method of Dutta and Ray [1987] as follows. Using a primal-dual-type algorithm, we show how to construct a class of cost-sharing methods for a submodular cost function, parameterized by $n$ functions, one for each user. All methods in our class are cross-monotone and therefore lead to group strategyproof mechanisms.

Our class contains cost-sharing methods satisfying a wide range of fairness criteria, hence the name ``equitable''. For instance, if the $n$ functions are identical, we get the egalitarian method, which attempts to equalize the amounts charged from the users. If they are probability distributions from which users pick their utilities, we get a method that attempts to equalize the probabilities of users getting service.

---------------

Speakers Isaac Kunen, Frank McSherry
Title The Probabilistic Method
Abstract Tomorrow in theory seminar, Isaac and I will present two proofs from the book that use the probabilistic method, which operates via the following principle: If the probability that a random combinatorial object has property P is strictly greater than 0, there must exist an object that has this property. This technique is used (and will be used tomorrow) to non-constructively show the existence of certain objects. In particular, we will show that
  1. If R(m,n) is a number such that all graphs on R(m,n) nodes have a clique of size m or an independent set of size n, then R(k,k) >= 2^{k/2}
  2. While some graphs are planar, even non-planar graphs can be embedded in the plane(!); they just have edges that cross each other. We will see that the minimum number of crossings in any planar embedding is Crossings(G) >= (1/64) * m^{3}/n^{2}, when m >= 4n.
In each of these proofs we will use simple probability, the most complicated techniques being the linearity of expectation (if you look close) and the union bound.

---------------

Speaker John Dunagan (Department of Mathematics, MIT)
Title Optimal Outlier Removal
Abstract Given a set of points in high-dimensional Euclidean space, we define a point x to be a gamma-outlier if there exists some direction w in which x is more than gamma standard deviations from the mean along w. Outlier removal is the problem of removing an epsilon fraction of points so that the remaining subset has no gamma-outliers. We characterize the optimal trade-off between epsilon and gamma using a simple algorithm for outlier removal.

We believe this work has a good chance of being useful to anyone who works with data, from physical scientists to computer scientists to applied mathematicians. As one application, we improve the running time of learning a halfspace in the presence of random classification noise (a classic problem in machine learning) from O(n^{28}) to O(n^5). For a visual demonstration, please visit http://theory.lcs.mit.edu/~jdunagan

This is joint work with Santosh Vempala.

---------------

Speakers Stefan Saroiu, Gideon Shavit, Adrien Treuille
Title Three Famous Theorems on Finite Sets
Abstract We will discuss a basic theme in combinatorics -- properties and sizes of special families of subsets of a finite set N={1, 2, 3, ..., n}. We will present three beautiful proofs to three famous theorems:
  • Sperner's Theorem (size of largest antichain of N)
  • Erdos-Ko-Rado's Theorem (size of largest intersecting k-family of N)
  • Hall's Theorem (necessary and sufficient condition to have a mass-wedding).



CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[Comments to ashish]