The SPAMS Schedule - Spring 2014

Abstract: The subject of graph limits started about a decade ago, with goal of developing of a mathematical theory of very large graphs and networks, such as those arising from real world applications. A basic mathematical question is: what does it mean for a sequence of graphs to converge, and how can we represent its limit? I will give an introduction to the subject, and also discuss some recent developments concerning sparse graph limits and scale-free networks.

Abstract: In recent years the biomedical community has again and again found that supposedly de-identified data isn't as de-identified as they thought. It turns out that our naive ideas about what kind of data compromises privacy are not in line with reality. Here we will talk about some of the privacy breaches that have happened in the past few years and the techniques that made them possible. We will then talk about ways that we can ensure such privacy breaches are avoided in the future (differential privacy, etc.) -- namely techniques that provide provable privacy guarantees!

Abstract: Distributed algorithms are algorithms meant to run on a network of multiple processors, with no centralized control. We need the network to be connected so that information can propagate along the edges, but the processors typically decide on how to act based on the information history that they have received. Distributed algorithms have proven to be a wonderful mathematical tool in solving problems like leader election, mutual exclusion, and consensus. In this talk I will present a little bit of the history of distributed algorithms, particularly graph coloring problems in the distributed setting. I will then try to go into a recent nice connection between distributed algorithms and structural graph theory. There may or may not be a walrus in the talk, depending on how much time I have.

Abstract: There had been several attempts to prove whether P = NP or not via linear programmings (LP). Some people claimed that they proved P = NP by constructing small LP for Traveling Salesman Problem (TSP). Yannakakis disputed their results by proving that any symmetric LP which solves TSP needs to have exponential size (and all of the wrong results provided symmetric LP). Ignited by Yannakakis' result, it has been of interest to know what is the smallest size of LP formulation of known combinatorial optimization problems. I'd like to go over the brief history of this relatively new area and talk about some known results and intriguing open questions.

Abstract: Many important optimization problems are impossible to solve exactly in polynomial time (unless P = NP). But this does not mean we should give up on these problems altogether. One way to remedy the situation is to design efficient approximation algorithms that produce solutions provably close to the true optimum. There are many open problems in this area because for many computational problems it is not known just how good of an approximation guarantee you can get before it becomes NP-hard to do any better. One technique in designing approximation algorithms is to relax the problem to a convex optimization problem (generally a linear program or semidefinite program). After introducing the basics of approximation algorithms I will talk about a specific recent technique called the Lasserre Hierarchy which gives a systematic way to produce semidefinite relaxations. It is still open whether this hierarchy is powerful enough to resolve various open questions in approximation theory such as the Unique Games Conjecture.

Abstract: The notions of probability density and conditioning on sets of measure zero are traditionally defined and computed by rejecting all samples that do not fall in a neighborhood of increasingly small size. In many computational situations, one wishes to restrict oneself to neighborhoods of nearly infinitesimal measure (for example, if the property we are looking at is very sensitive to the conditioned variable or if we are conditioning on many variables). In such cases, traditional Monte Carlo sampling is prohibitively inefficient because the vast majority of samples generated by the traditional Monte Carlo algorithm do not fall in this nearly infinitesimal neighborhood and must therefore be discarded.

Rather than defining probability density and conditioning as the limit of increasingly unlikely neighborhoods of some constraint, we interpret the conditional samples as the intersection points of the constraint manifold with random Haar-measure great spheres via Crofton's formula from classical integral geometry, directly obtaining the constrained samples themselves and eliminating the need to take any such limits. Using this new representation of conditional probability as a root finding problem, we develop a corresponding Monte Carlo algorithm, allowing us to sample the conditional distribution and compute the probability density at a specific point, rejecting only as many samples as are needed by the nonlinear solver to locate the intersection point.

Abstract: When assigning processors to tasks, or managing a personal to-do list, we have to make choices about which tasks to work on first. In many situations in classical scheduling theory, an objective of minimizing total flow time is appropriate. We consider several variant possibilities, depending on our knowledge of the lengths of the tasks and the existence of importance weights on the tasks, giving rise to an alphabet soup of very simple algorithms. We will learn which of these algorithms are optimal or scalable, a weaker notion, and consider how feasibly we might apply these to our own to-do lists. Finally, we will consider some recent surprising results about extending these algorithms to the multiprocessor case, or alternatively stated, managing a team to-do list.