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

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.

Spring break (no seminar)
Mar 18 @ 12:00 pm – 1:00 pm
Alex Slivkins
Apr 1 @ 12:00 pm – 1:00 pm

Speaker: Alex Slivkins
Affiliation: Microsoft Research – New York

Title: Bandits with Resource Constraints
Multi-armed bandits is the predominant theoretical model for exploration-exploitation tradeoff in machine learning, with countless applications ranging from medical trials, to communication networks, to Web search and advertising, to dynamic pricing. In many of these application domains the learner may be constrained by one or more supply/budget limits, in addition to the customary limitation on the time horizon. We introduce a general model that encompasses such problems, combining aspects of stochastic integer programming with online learning. A distinctive feature (and challenge) in our model, compared to the conventional bandit problems, is that the optimal policy for a given problem instance may significantly outperform the policy that always chooses the best fixed action. Our main result is an algorithm with near-optimal regret relative to the optimal policy. Also, we extend this result to contextual bandits, and detail an application to dynamic pricing.

Mohammad Hajiaghayi
Apr 15 @ 12:00 pm – 1:00 pm

Mohammad Hajiaghayi
University of Maryland – College Park

Title: Parameterized and Promised Streaming: Matching and Vertex Cover

As graphs continue to grow in size, we seek ways to effectively
process such data at scale. The model of streaming graph processing, in
which a compact summary is maintained as each edge insertion/deletion
is observed, is an attractive one. However, few results are known for
optimization (often NP-hard) problems over such dynamic graph streams.

In this talk, we introduce a new approach to handling graph streams,
by instead seeking solutions for the parameterized (and promised) versions of
these problems. Here, we are given a parameter k and the objective is to
decide whether there is a solution bounded by k. By combining
kernelization techniques with randomized sketch structures, we obtain the
first streaming algorithms for the parameterized versions of Maximal
Matching and Vertex Cover. We consider various models for a graph stream on n
nodes: the insertion-only model where the edges can only be added, and
the dynamic model where edges can be both inserted and deleted.

Gordon Wilfong
Apr 22 @ 12:00 pm – 1:00 pm

Gordon Wilfong
Alcatel-Lucent Bell Labs

Title: Optimal Path Encoding
Abstract: Packet networks need to maintain state in the form
of forwarding tables at each switch. The cost of this state
increases as networks support ever more sophisticated per-flow
routing, traffic engineering, and service chaining. Per-flow or per-path
state at the switches can be eliminated by encoding each
packet’s desired path in its header. A key component of such a
method is an efficient encoding of paths.
We introduce a mathematical formulation of this optimal path encoding
problem. We prove that the problem is APX-hard, by
showing that approximating it to within a factor less than 8/7
is NP-hard. We then present an algorithm
approximating the optimal path-encoding problem to within a
factor 2. Finally, we provide empirical results illustrating the
effectiveness of the proposed algorithm.
Joint work with A. Hari (Bell Labs) and U. Niesen (Qualcomm)

Lisa Zhang
May 13 @ 12:00 pm – 1:00 pm

Speaker: Lisa Zhang
Affiliation: Alcatel-Lucent Bell Labs

Title: Analysis of k-Anonymity Algorithms for Streaming Location Data

We propose and analyze algorithms to achieve k-anonymity for streaming location data. We consider a framework motivated by European Union privacy requirements, in which location information arrives online into a buffer of fixed size m. Whenever the buffer fills, some data must move to permanent storage in a k-anonymized fashion. This notion of anonymity refers to recording a coarse common region containing at least k points instead of separate exact locations. One primary goal is to minimize the recorded region size so that the anonymized location data is as accurate as possible.

We observe that under competitive analysis, any online algorithm can be arbitrarily bad in terms of the recorded region size. We therefore assume a more benign model in which the location distribution is known. For a uniform distribution, we analyze a simple, natural algorithm that partitions the space into m/k identical regions to ensure k-anonymity, and picks the region with the largest occupancy whenever the buffer fills. Our detailed analysis shows
that the largest occupancy converges to 2k. This implies, perhaps somewhat unintuitively, that it is sufficient to achieve k-anonymity by partitioning space into $2m/k$ regions, which reduces and thereby improves the recorded region size by a factor of 2. We also present an almost matching lower bound of 2m/k. Finally, we discuss generalizations to nonuniform distributions by partitioning the space to match the given distribution.

Sanjeev Khanna
Jun 10 @ 12:00 pm – 1:00 pm

Speaker: Sanjeev Khanna
Affiliation: University of Pennsylvania

Title: Tight Bounds for Linear Sketches of Approximate Matchings

We consider the problem of approximating a maximum matching in dynamic graph streams where the stream may include both edge insertions and deletions. Our main result is a resolution of the space complexity of linear sketches for approximating the maximum matching in this model.

Specifically, we show that for any $\eps > 0$, there exists a single-pass streaming algorithm, which only maintains a linear sketch of size roughly $n^{2-3\eps}$ bits and recovers an $n^\epsilon$-approximate maximum matching in dynamic graph streams, where $n$ is the number of vertices in the graph. We complement this result with the following lower bound result: any linear sketch for approximating the maximum matching to within a factor of $n^\eps$ has to be of size at least $n^{2-3\eps -o(1)}$ bits.

This is based on joint work with Sepehr Assadi, Yang Li, and Grigory Yaroslavtsev.

[Theory Seminar] Harry Lang
Sep 2 @ 12:00 pm – 1:00 pm


Title: A New Algorithm for Accurate and Low-Space k-Median Clustering on Data Streams
Abstract: The k-median problem for insertion-only data streams is an active area of research.  In 2003, Charikar et al provided the first poly(k, log n)-space constant-approximation, albeit with a massive constant (~5500).  In the current work, we introduce a new technique that finds a low-constant approximation (~40) without requiring any additional storage.
Short Bio: Harry Lang is a doctoral student in the mathematics department at JHU.  He studies algebraic topology, and in particular computational methods for detecting topological structure of massive data sets.  In computer science, he works on streaming algorithms for clustering with Professor Vladimir Braverman.
This talk will be given remotely.


Hossein Esfandiari
Sep 30 @ 12:00 pm – 1:00 pm

Details and abstract will be added when available.

[Theory Seminar] Hossein Esfandiari
Sep 30 @ 12:00 pm – 1:00 pm



Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond.


We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. Consider a graph G=(V,E) with n vertices and m edges. The input stream is a permutation of edges S= (e_1,…,e_m) chosen by an adversary.
The goal is to output an estimation of the size of a maximum matching. The algorithm is only allowed to use a small amount of memory (much smaller than n).

When the underlying graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using O-tilde(n^(2/3)) space. The approach generalizes to the family of graphs that have bounded arboricity. Graphs with bounded arboricity include, among other families of graphs, graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model). We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We hope that this approach finds applications in estimating other properties of graphs in the adversarial-order streaming model. We further reduce the required memory size to O-tilde(sqrt(n)) for three restricted settings: (i) when the underlying graph is a forest; (ii) when we have 2-passes over the stream of edges of a graph with bounded arboricity; and (iii) when the edges arrive in random order and the underlying graph has bounded arboricity.

Finally, by introducing a communication complexity problem, we show that the approximation factor of a deterministic algorithm cannot be better than a constant using o(n) space, even if the underlying graph is a collection of paths. We can show that under a plausible conjecture for the hardness of the communication complexity problem, randomized algorithms with o(sqrt(n)) space cannot have an approximation factor better than a fixed constant.

[Theory Seminar] Sofya Raskhodnikova
Oct 7 @ 12:00 pm – 1:00 pm
Title: Fast Algorithms for Testing Geometric Properties
Speaker: Sofya Raskhodnikova


How quickly can we determine if an object satisfies some basic geometric property? For example, is the object a half-plane? Is it convex? Is it connected? If we need to answer such a question exactly, it requires at least as much time as it takes to read the object. In this talk, we will focus on approximate versions of these questions and will discuss how to solve them in time that depends only on the approximation parameter, but not the size of the input.

Specifically, an algorithm is given access to a discretized image represented by an n x n matrix of 0/1 pixel values. Another input to the algorithm is an approximation parameter, epsilon. The algorithm is required to accept images with the desired property and reject (with high probability) images that are far from having the desired property. An image is far if at least an epsilon fraction of its pixels has to be changed to get an image with the required property. For example, in this model, if the algorithm is allowed to read pixels of its choice, the half-plane property and convexity can be tested in time O(1/epsilon). If the algorithm receives access to pixels chosen uniformly and independently at random, then the half-plane property still takes O(1/epsilon) time, but for convexity the (optimal) bound on the running time is O(1/epsilon^(4/3)).

Based on joint work with Piotr Berman and Meiram Murzabulatov.


Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, and randomized algorithms. She got her PhD from MIT in 2003. From the fall of 2003 to 2006, she worked at the Hebrew University of Jerusalem, the Weizmann Institute of Science and the Institute for Pure and Applied Mathematics. In 2013–2014, she was on sabbatical leave at Boston University for a special Privacy Year and also participated in thePrivacy Tools project at Harvard University in Spring 2014.
[Theory Seminar] Sofya Raskhodnikova
Oct 7 @ 12:00 pm – 1:00 pm

Details and abstract will be added when available.

[Theory Seminar] Gal Shahaf
Nov 4 @ 12:00 pm – 1:00 pm

Title: Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Speaker: Gal Shahaf
Affiliation: The Hebrew University of Jerusalem

Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and economic optimality. We focus on AMD’s paradigmatic problem: combinatorial auctions, and present new inapproximability results for truthful mechanisms in this scenario. Our main technique is a generalization of the classical VC dimension and the corresponding Sauer-Shelah Lemma.

Joint work with Amit Daniely and Michael Schapira

The talk is designed to be accessible to M.Sc. students, and includes an elementary introduction to VC dimension, combinatorial auctions and VCG mechanisms.

[Theory Seminar] Ilya Razenshteyn
Nov 9 @ 12:00 pm – 1:00 pm

SPEAKER: Ilya Razenshteyn (MIT)

TITLE: Sketching and Embedding are Equivalent for Norms

ABSTRACT: Imagine the following communication task. Alice and Bob each have a point from a metric space. They want to transmit a few bits and decide whether their points are close to each other or are far apart. Of particular interest are sketching protocols: Alice and Bob both compute short summaries of their inputs and then a referee, given these summaries, makes the decision; sketches are very useful for the nearest neighbor search, streaming, randomized linear algebra etc. Indyk (FOCS 2000) showed that for the l_p spaces with 0 < p <= 2 the above problem allows a very efficient sketching protocol. Consequently, any metric that can be mapped into the l_p space with all the distances being approximately preserved has a good protocol as well. 

I will show that for normed spaces (a very important class of metric spaces) embedding into l_p is the only possible technique for solving the communication problem. Slightly more formally, we show that any normed space that admits a good communication (in particular, sketching) protocol for distinguishing close and far pairs of points embeds well into l_p with p being close to 1. The proof uses tools from communication complexity and functional analysis.

 As a corollary, we will show communication lower bounds for the planar Earth Mover’s Distance (minimum-cost matching metric) and for the trace norm (the sum of the singular values of a matrix) by deriving them from the (known) non-embeddability theorems and (the contrapositive of) our result.


The talk is based on a joint paper with Alexandr Andoni and Robert Krauthgamer (arXiv:1411.2577).