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

[Theory Seminar] Xin Li
Feb 2 @ 12:00 pm – Feb 24 @ 1:00 pm

Details TBA

[Theory Seminar] Aravind Srinivasan
Feb 17 @ 12:00 pm – 1:00 pm

Speaker: Aravind Srinivasan
Affiliation: University of Maryland

Title: Properties and Generalizations of the Moser-Tardos Process

Abstract: Moser and Tardos have developed an elegant and powerful algorithmic version of the Lovasz Local Lemma. Since the publication of this work, it has become apparent that this algorithm has some very interesting properties and extensions, and can be viewed as a stochastic process of independent interest. I will survey some of these, especially the ideas of “partial resampling” and the “LLL-distribution” (the properties of the output distribution of Moser-Tardos). I will draw from joint works with Haeupler and Saha, with Harris, and with Chen and Harris.

[Theory Seminar] Merav Parter
Feb 24 @ 12:00 pm – 1:00 pm

Title: Fault Resilient Graph Structures
Speaker: Merav Parter (MIT)


A fault-tolerant (FT) structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. Fault-resilience can be introduced into the network in several different ways. This talk will focus on a notion of fault-tolerance whereby the structure at hand is augmented (by adding to it various components) so that subsequent to the failure of some of the network’s vertices or edges, the surviving part of the structure is still operational. As this augmentation carries certain costs, it is desirable to minimize the number of added components.We will revise several constructions of sparse fault tolerant structures such as FT spanner and FT shortest-path trees. I will also present a new model for fault resilient network structures that mix two orthogonal protection mechanisms: (a) backup, namely, augmenting the structure with many (redundant) low-cost and fault-prone components, and (b) reinforcement, namely, acquiring high-cost but fault-resistant components. A trade-off between these two mechanisms will be presented in a concrete setting of shortest-path trees.

[Theory Seminar] Abhishek Jain
Mar 2 @ 12:00 pm – 1:00 pm

Details TBA

[Theory Seminar] Joshua Brody
Mar 9 @ 12:00 pm – 1:00 pm

Talk Title:

Dependent Random Graphs and Multiparty Pointer Jumpin


We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges.  We call such graphs *dependent random graphs*  and give tight bounds on the clique and chromatic numbers of such graphs.  Surprisingly, some of the bounds in the standard random graph model continue to hold in this relaxed setting.  For example, the size of the largest clique in a dependent random graph remains roughly log(n)/log(1/p).

As an application, we give a new upper bound on communication complexity of the Multiparty Pointer Jumping (MPJ) problem in the number-on-the-forehead (NOF) model.  NOF communication lies at the current frontier of our understanding of communication complexity, and MPJ is one of the canonical problems in this setting.  Furthermore, sufficiently strong bounds for MPJ would have important consequences for circuit complexity.

No prior knowledge is assumed aside from basic discrete probability.  I hope to motivate both random graphs and the application and demonstrate why NOF communication is an important active research area.

This talk is based on research that is joint work with Mario Sanchez.


Joshua Brody received a bachelor’s degree in Mathematics/Computer Science from Carnegie Mellon University, a Master’s Degree in Computer Science from New York University, and a  PhD in Computer Science from Dartmouth College.  Prior to graduate school, he served in the Peace Corps teaching high school mathematics in Burkina Faso, West Africa.  Dr. Brody is currently an Assistant Professor in the Computer Science department at Swarthmore College.  His primary research area is communication complexity.  Additional research interests include several areas of theoretical computer science, including streaming algorithms, property testing, and data structures.

[Theory Seminar] Valerio Pastro
Apr 13 @ 12:00 pm – 1:00 pm
Speaker: Valerio Pastro (Columbia University)Title: Essentially Optimal Robust Secret Sharing with Maximal Corruptions

In a t-out-of-n robust secret sharing scheme, a secret message is shared among n parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to t of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where n=2t+1.In this scenario, to share an m-bit message with a reconstruction failure probability of at most 2−k, a known lower-bound shows that the share size must be at least m+k bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties n, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT ’12) achieves m+O˜(k+n).

In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with n=2t+1, that avoids the linear dependence between share size and the number of parties n. In particular, we get a share size of only m+O˜(k) bits. Our scheme is computationally efficient and relies on approximation algorithms for the minimum graph bisection problem.

This talk is based on a Eurocrypt’2016 paper with authors: Allison Bishop and Valerio Pastro and Rajmohan Rajaraman and Daniel Wichs.

(This work uses some cool tools from graph theory and I encourage you all to attend. )
[Theory Seminar] Noga Ron-Zewi
Apr 20 @ 12:00 pm – 1:00 pm

Details TBA

[Theory Seminar] Samir Khuller
Sep 14 @ 12:00 pm – 1:00 pm

Speaker: Samir Khuller

Affiliation: University of Maryland College Park

Title: To do or not to do: scheduling to minimize energy


Traditional scheduling algorithms, especially those involving job scheduling

on parallel machines, make the assumption that the machines are always

available and try to schedule jobs to minimize specific job related metrics.

Since modern data centers consume massive amounts of energy, we consider job

scheduling problems that take energy consumption into account, turning

machines off, especially during periods of low demand. The ensuing problems

relate very closely to classical covering problems such as capacitated set

cover, and we discuss several recent results in this regard.
(This is talk covers two papers, and is joint work with Jessica Chang, Hal Gabow

and Koyel Mukherjee.)

[Theory Seminar] Justin Hsu
Oct 12 @ 12:00 pm – 1:00 pm

Speaker: Justin Hsu
Affiliation: University of Pennsylvania

Title: Approximate Probabilistic Coupling and Differential Privacy
Abstract: Approximate lifting is a formal verification concept for proving
differential privacy. Recently, we have explored an interesting connection:
approximate liftings are an approximate version of probabilistic coupling. As a
consequence, we can give new, “coupling” proofs of differential privacy,
simplifying and generalizing existing proofs.  In this talk we will present
approximate couplings and describe how to they can be used to prove differential
privacy for the Sparse Vector mechanism, an algorithm whose existing privacy
proof is notoriously subtle.
Joint with Gilles Barthe, Marco Gaboradi, Benjamin Gregoire, and Pierre-Yves Strub.
[Theory Seminar] David Harris
Oct 19 @ 12:00 pm – 1:00 pm

Speaker: David Harris

Affiliation: University of Maryland College Park

Title: Improved parallel algorithms for hypergraph maximal independent set


Finding a maximal independent set in hypergraphs has been a long-standing algorithmic challenge. The best parallel algorithm for hypergraphs of rank $r$ was developed by Beame
and Luby (1990) and Kelsen (1992), running in time roughly $(\log n)^{r!}$. This is in RNC for fixed $r$, but is still quite expensive.  We improve on the analysis of Kelsen to
show that (a slight variant) of this algorithm runs in time $(\log n)^{2^r}$. We derandomize this algorithm to achieve a deterministic algorithm running in time $(\log
n)^{2^{r+3}}$ using $m^{O(1)}$ processors.

Our analysis can also apply when $r$ is slowly growing; using this in conjunction with a strategy of Bercea et al. (2015) gives a deterministic algorithm running in time
$\exp(O(\log m/\log \log m))$. This is faster than the algorithm of Bercea et al, and in addition it is deterministic. In particular, this is sub-polynomial time for graphs with
$m \leq n^{o(\log \log n)}$ edges.