|
CSE Home |
Previous Quarters |
About Us |
Search |
Contact Info |
Time and LocationThe seminar meets Tuesdays, 1:30-2:20pm in EE1 037.Email ArchiveClick here to view the archive containing emails sent to cse590z@cs as well as to theory-group@cs.Description |
|
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.
| 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 | - | |
| 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
|
---------------
| 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:
|
|
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] |
||