Seminar

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

Jun
10
Wed
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

Abstract:
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.

Sep
2
Wed
[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.

 

Sep
30
Wed
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

 

Title:

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

Abstract:

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.

Oct
7
Wed
[Theory Seminar] Sofya Raskhodnikova
Oct 7 @ 12:00 pm – 1:00 pm

Details and abstract will be added when available.

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

Abstract:

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.

Bio:

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.
Nov
4
Wed
[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

Abstract:
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.

Nov
9
Mon
[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).

Nov
18
Wed
[Theory Seminar] Zeyu Zhang
Nov 18 @ 12:00 pm – 1:00 pm
Approximating Low-Stretch Spanners
abstract:
Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating basic k-spanner (particularly for small k), and the dependence on f when approximating f-fault tolerant spanners.
We first design an Õ(n^(1/3))-approximation for 4-spanner (both basic and directed). This was the last value of k for which only an O(√n)-approximation was known for basic k-spanner, and thus implies that for any k the approximation ratio is at most Õ(n^(1/3)). For basic k-spanner, we also show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial approximation of n^{\frac{1}{\lfloor (k+1)/2\rfloor}}.
For f-fault tolerant spanners, we show that in the small-stretch setting (k ∈ {3,4}) it is possible to entirely remove the dependence on f from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on f was either almost-linear (in the undirected setting) or exponential (in the directed setting for stretch 4).

 

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

Details TBA

Feb
3
Wed
[Theory seminar] Tuo Zhao
Feb 3 @ 12:00 pm – 1:00 pm

Title: Nonconvex Statistical Optimization: Algorithm and Model-based Optimization Theory

Abstract: Nonconvex regularized M-estimators have been widely applied to high dimensional data analysis. Existing statisticaltheory has established their statistical properties
in high dimensions only when the global optimum or certain local optimum can be obtained. Though practitioners have proposed numerous heuristic computational algorithms for
solving these nonconvex optimization problems, existing optimization theory does not necessarily guarantee these algorithms to obtain the global or local optima with
desired statistical properties in polynomial time. Therefore, there exists a significant gap between theory and practice: What is actually computed is not the same as what has
been proved. To bridge this gap, we propose a new generation of nonconvex statistical optimization algorithms and model-based theory, which incorporate the statistical thinking
into modern optimization. When developing computational algorithms, we take underlying sparse statistical models into consideration. Particularly, for nonconvex regularized
M-estimation problems, our proposed algorithms devise three different optimization schemes, under which the solutions achieved by the optimization algorithm always falls within
a restricted sparse set. Thus the nonconvex objective function mimics the behavior of a strongly convex function, which eventually allows our proposed algorithms to obtain an
estimator with the desired optimal statistical properties in polynomial time with high probability

Feb
17
Wed
[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.

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

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

Abstract:

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.

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

Details TBA

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

Talk Title:

Dependent Random Graphs and Multiparty Pointer Jumpin

Abstract:

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.

Bio:

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.

Apr
13
Wed
[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

Abstract:
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. )
Apr
20
Wed
[Theory Seminar] Noga Ron-Zewi
Apr 20 @ 12:00 pm – 1:00 pm

Details TBA

Sep
14
Wed
[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

Abstract:

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.)

Oct
12
Wed
[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.
Oct
19
Wed
[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

Abstract:

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.