The SPAMS Schedule - Fall 2013

Abstract: The Four Color Theorem essentially states that four colors are sufficient to color any map so that bordering regions do not share the same color. While it has been proven roughly forty years ago, every known proof of it involves reducing it to a large but finite number of cases and then checking them by means of a computer. In this talk, I will begin by outlining a recent approach to proving the Four Color Theorem purely combinatorially using labeled binary trees. While this approach has only yielded several large cases of the final result, I will show how this approach very naturally yields a beautiful structure called the Comb Poset, with deep connections to the rotation graph, the Tamari Lattice, and other objects that are not well-understood. In particular, three (seemingly unrelated) functions that are extremely hard to compute in general become extremely easy in this framework. I will finish by outlining a couple of applications of the Comb Poset, particularly in graph searching algorithms.

Joint work with Alex Csar (UMN-Twin Cities) and Warut Suksompong (MIT).

Abstract: Remember the Fibonacci numbers? You probably thought they were really cool when you were younger. Maybe you played around with them and noticed some cool patterns, perhaps you stumbled across some identities they satisfy such as:

$(F_n)^4 = F_(n-2)F(n-1)F_(n+1)F_(n+2) +1 $

Maybe you even proved a few of them. Well I'm going to prove ALL of them. Okay, not all of them, but a lot of them. More importantly I'm going to do it without trying very hard. I'll also explain why this method for proving stupid identities about the Fibonacci numbers is actually useful.

Abstract: Given a graph, one can ask whether the graph looks sufficiently random, or is pseudorandom. It turns out there are in fact a few notions that are equivalent. I will talk about these notions and equivalences.

Abstract: Take a random walk on a graph, and each time you first visit a node, mark the edge that took you there. After you have visited all nodes, the marked edges form a spanning tree of your graph, sampled from whatever distribution arises from this random process. What is this distribution, i.e., can we characterize which spanning trees are more or less likely? Can we design a simple randomized process to produce *uniformly* random spanning trees?

Abstract: Suppose a graph G is given and we want to map the vertices of G to unit vectors where a pair of adjacent vertices are mapped into two vectors such that angle between them is maximized. The maximal minimum angle between the images of all pairs of adjacent vertices is a function of the dimension that eventually reaches a maximum. The vector chromatic dimension of G is defined as the smallest d we need to reach this maximum angle. I'll talk about some bounds on vector chromatic dimension and explicit computation of the dimension for special classes of graphs.

Abstract: In the problem of hashing, one wishes to provide an efficient, consistent and reliable way to map an unknown set of objects S into a known set of locations T injectively. Cuckoo hashing is a particularly clever solution to the problem which optimizes the worst-case lookup times by assigning every object to two locations that it can toggle between as other objects displace it. Hypercuckoo hashing is the natural generalization to k>2 locations, which achieves better space expansion for the cost of worse, but still constant, lookup times. The exact expansion factor for all k>2 was unknown until as recently as 2010, after which four independent research groups solved the problem with very different approaches. We will survey parts of these approaches and how they fit into the bigger picture.

Abstract: Sequencing the genome produces ginormous amounts of data. One large fraction of this data is the quality scores the sequencing machine spits out characterizing its confidence in the sequencing base calls it makes. In this very simple talk, I show how combining the basic ideas of counting k-mers in a large corpus of reads and measuring k-mer Hamming distance are sufficient to allow us to discard 95% of quality scores while not only not decreasing, but indeed actually improving the accuracy of downstream variant analyses. A naive application of Chernoff bounds will be used to justify the approach, but the majority of the talk is entirely suitable for anyone who knows how to count (or even just how to tell a computer to count). Joint work with Bonnie Berger & Deniz Yorukoglu.

Abstract: Social choice theory concerns the ability to aggregate a set of individual preferences into a collective decision. For example, political elections take voters' preferences of candidates and return a winner. The fact that there are many different voting systems (plurality, instant runoff) which can yield different results reflects the fact that the problem of aggregating individual preferences is very nontrivial. In this talk I will describe a way of modeling community preferences using tournaments, which are directed graphs with exactly one edge between each pair of vertices. Given a tournament, we can attempt to choose a subset of vertices to be the ``best'' options among the vertices. In 1990 Schwartz conjectured that there is a way of doing this so that the chosen subset satisfies many desirable properties from a social choice standpoint. We give a recent counterexample to this conjecture.

Abstract: Last June Adam Marcus, Daniel Spielman and Nikhil Srivastava posted a paper titled "Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem" in which they prove a result concerning rank one matrices, equivalent to the Kadison-Singer problem, a conjecture from 1959 from operator theory. I will try to give an account of the chain of equivalences, the solution and some motivation about why this problem is important.

Abstract: Path-Following Methods are some of the fastest algorithms to solve linear programming problems. In this talk, I will give a short proof of the standard path following method. Then, I will discuss a possible way to make it faster.

Joint work with Aaron Sidford.

Abstract: Come learn how math has a role to play in social and economic justice issues! We will talk about wealth inequality, racism, wages, war casualties, how numbers and plots can be made to say anything, and what we can do about it. This will be an interactive lecture in which we will discuss problems and solutions together!

Abstract: We consider k-Facility Location games, where n strategic agents report their locations on the real line, and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. We are interested in understanding mechanisms without payments that are strategyproof meaning that agents cannot improve their connection cost by lying about their locations, and achieve a good approximation ratio for some objective function e.g. sum of costs.

This talk will provide an overview of the area of mechanism design without money and present a combination of positive and negative results focusing on the single dimensional facility location problem moving towards more general domains.