We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Aaron Roth
Sep 24 @ 12:00 pm – 1:00 pm

Title: Correctness Protection via Differential Privacy

Speaker: Aaron Roth
Affiliation: UPenn

False discovery is a growing problem in scientific research. Despite
sophisticated statistical techniques for controlling the false discovery rate
and related statistics designed to protect against spurious discoveries, there
is significant evidence that many
published scientific papers contain incorrect conclusions.

In this talk we consider the role that adaptivity has in this problem. A
fundamental disconnect between the theorems that control false discovery rate
and the practice of science is that the theorems assume a fixed collection of
hypotheses to be tested, selected non-adaptively before the data is gathered,
whereas science is by definition an
adaptive process, in which data is shared and re-used, while hypotheses are
generated after seeing the results of previous tests.

We note that false discovery cannot be prevented when a substantial number of
adaptive queries are made to the data, and data is used naively — i.e. when
queries are answered exactly with their empirical estimates on a given finite
data set. However we show that remarkably, there is a different way to evaluate
statistical queries on a data set that allows even an adaptive analyst to make
exponentially many queries to the data set, while guaranteeing that with high
probability, all of the conclusions he draws generalize to the underlying
distribution. This technique counter-intuitively involves actively perturbing
the answers given to the data analyst, using techniques developed for privacy
preservation — but in our application, the perturbations are added entirely to
increase the utility of the data.

Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann
Pitassi, and Omer Reingold.

Guy Kortsarz
Oct 8 @ 12:00 pm – 1:00 pm

Speaker: Guy Kortsarz
Affiliation: Rutgers University-Camden

Title: What have we learned about cut expansion and density problems

Abstract: I will survey several problems related to the above subjects. Directed and undirected multicut.  For Directed multicut I will show the approximation algorithm algorithm of Gupta.  Conductance (and sparsest cut), overlapping and non overlapping clustering, the small set expansion conjecture and it equivalent to breaking the ratio of 2 for MINIMUM partial vertex cover problem, the densest subgraph problem and the dense k-subgraph problem.

Robert Krauthgamer
Oct 22 @ 12:00 pm – 1:00 pm

Speaker: Robert Krauthgamer
Affiliation: Weizmann Institute of Science

Title: The Sketching Complexity of Graph Cuts

We study the problem of sketching an input graph $G$ on $n$ vertices, so that given the sketch, one can estimate the weight (capacity) of any cut in the graph within a small approximation factor $1+\epsilon$. The classic cut-sparsifier construction of Benczur and Karger (STOC 1996) implies a sketch of size $\tilde O(n/\epsilon^2)$ [this notation hides logarithmic factors].

We show that the dependence on $\epsilon$ can be brought down to only linear, at the price of achieving a slightly relaxed guarantee. Specifically, we design a randomized scheme that produces from $G$ a sketch of size $\tilde O(n/\epsilon)$ bits, from which the weight of any cut $(S,\bar S)$ can be reported, with high probability, within factor $1+\epsilon$. We also demonstrate some applications where this “for each” guarantee is indeed useful.

We further prove that that our relaxation is necessary. Specifically, a sketch that can $(1+\epsilon)$-approximate the weight of all cuts in the graph simultaneously (i.e., a “for all” guarantee), must be of size $\Omega(n/\epsilon^2)$ bits.

Joint work with Alexandr Andoni and David Woodruff.

Calvin Newport
Oct 29 @ 12:00 pm – 1:00 pm

Calvin Newport
Georgetown University

Title: Radio Network Lower Bounds Made Easy

Amitabh Basu
Nov 5 @ 12:00 pm – 1:00 pm

Speaker: Amitabh Basu
Affiliation: JHU

Title: Cutting Planes and Geometry of Numbers

Abstract: We survey some recent results in cutting plane theory for integer programming. Cutting Planes give a way to reduce the search space for the optimal solution in an integer optimization problem. The results we will present are very recent connections between cutting planes and covering/tiling properties of subsets of euclidean sets. Important structural information about cutting planes can be translated to geometric questions like: Does a particular compact subset B of R^n cover all of R^n when we consider all of its translates by integer vectors. This connects to very classical problems in the geometry of numbers and deep theorems like the Venkov-Alexandrov-McMullen theorem on tilings, and the geometry of zonotopes can be leveraged. Research in this area of integer optimization is very much work-in-progress; we will close the presentation with an invitation to join our quest with some open problems.

Grigory Yaroslavtsev
Nov 19 @ 12:00 pm – 1:00 pm

Speaker: Grigory Yaroslavtsev
Affiliation: University of Pennsylvania

Title: Parallel Algorithms for Geometric Graph Problems

I will describe algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. The talk will be self-contained, including a formal introduction of the modern theoretical computational models used to capture computations in massively parallel “MapReduce”-like systems. It will also include a sample of major open problems in the area.

For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes an approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms).

I will also show how the main ideas from the MST algorithm can be captured within a general “Solve-and-Sketch” algorithmic framework that we develop. Besides MST it also applies to the approximate Earth-Mover Distance (EMD) and the transportation cost problem. Algorithms designed in the “Solve-and-Sketch” framework have implications which go beyond parallel models. In particular, our work implies new near-linear time algorithms for EMD cost and transportation cost in the plane. Other implications include algorithms in the streaming with sorting model.

Joint work with Alexandr Andoni, Krzysztof Onak and Aleksandar Nikolov.

Michael Dinitz
Jan 28 @ 12:00 pm – 1:00 pm

Speaker: Michael Dinitz
Affiliation: Johns Hopkins University

Title: Approximating Graph Spanners

Graph spanners (subgraphs which approximately preserve distances) have been studied extensively since the 1980’s. Many of the known results are about the optimal tradeoffs between various parameters, particularly the stretch and size of the spanner. But there has been some recent progress on a different and less developed line of research: fixing the allowable stretch, and optimizing the size. This turns spanners into more of a computational problem, and allows us to use many of the standard techniques from approximation algorithms (convex relaxations in particular). In this talk we will give an overview of some of the progress in this area, its limitations, and some possible future directions.

David Harris
Feb 18 @ 12:00 pm – 1:00 pm

Speaker: David Harris
Affiliation: University of Maryland – College Park

Title: Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lov\'{a}sz Local Lemma

Abstract: The Lopsided Lovasz Local Lemma (LLLL) is a powerful probabilistic principle which has been used in a variety of combinatorial constructions. While this principle began as a general statement about probability spaces, it has recently been transformed into a variety of polynomial-time algorithms. The resampling algorithm of Moser & Tardos is the most well-known example of this. A variety of criteria have been shown for the LLLL; the strongest possible criterion was shown by Shearer, and other criteria which are easier to use computationally have been shown by Bissacot et al, Pegden, and Kolipaka & Szegedy.

We show a new criterion for the Moser-Tardos algorithm to converge. This criterion is stronger than the LLLL criterion, and in fact can yield better results even than the full Shearer criterion. This is possible because it does not apply in the same generality as the original LLLL; yet, it is strong enough to cover many applications of the LLLL in combinatorics. We show a variety of new bounds and algorithms. A noteworthy application is for $k$-SAT, with bounded occurences of variables. As shown in Gebauer, Szabo, and Tardos, a $k$-SAT instance in which every variable appears $L \leq \frac{2^{k+1}}{e (k+1)}$ times, is satisfiable. Although this bound is asymptotically tight (in $k$), we improve it to $L \leq \frac{2^{k+1} (1 – 1/k)^k}{k-1} – \frac{2}{k}$ which can be significantly stronger when $k$ is small.

Matthew Andrews
Mar 4 @ 12:00 pm – 1:00 pm

Speaker: Matthew Andrews
Affiliation: Alcatel-Lucent Bell Labs

Title: Understanding Sponsored Content in Mobile Data Networks

Sponsored content is a mechanism in which content providers can pay the operator of a wireless network to make their content free to end users. Such offerings have recently been introduced in both the US and Asia and they raise many challenging questions regarding which sites should be candidates for sponsoring and how much the service provider should charge the content provider.

In this talk we introduce a number of models that aim to capture the interactions between the service provider, the content provider and the end users in a sponsored content offering. We show that it is possible to design the system so that it is win-win-win for all players. In many settings the problem is a generalization of the “Adwords” problem that arises in the design of sponsored search. We also show how to analyze network traffic and content provider financial data in order to calculate the input parameters for these models.

Jeremy Fineman
Mar 11 @ 12:00 pm – 1:00 pm

Speaker: Jeremy Fineman
Affiliation: Georgetown University

How to Fix Exponential Backoff: Achieving Constant Throughput and Robustness with Polylog Attempts

Randomized exponential backoff is employed in many domains to coordinate access to a shared resource or communication channel. Despite the ubiquity of the protocol, exponential backoff has poor general performance guarantees. Most notably, exponential backoff neither achieves constant throughput in a general online setting, nor is it robust to corrupted or jammed messages. This talk considers a new backoff protocol that achieves constant throughput, even in the presence of an adaptive adversary that jams (or blocks access to) the shared resource at certain times. The protocol also makes relatively few attempts to access the resources, which means that each agent does not expend too much energy. Specifically, we show that the expected energy per agent is O(log^2(n+J)), where n is the number of contenders and J is the amount of time the adversary jams.