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

[Theory Seminar] Ilan Komargodski @ Malone 228
Oct 25 @ 12:00 pm – 1:00 pm

Speaker: Ilan Komargodski
Affiliation: Cornell Tech

Title: White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? This problem is in TFNP, the class of search problems with guaranteed solutions.  If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued.

1) What if one is given a program or circuit (“white-box”) for computing the existence of an edge. Does the search problem remain hard?
2) Can we generically translate all TFNP black-box hardness into white-box hardness?
3) Does the problem remain hard if the black-box instance is small?

We will answer all of these questions and discuss related questions in the setting of property testing.

Joint work with Moni Naor and Eylon Yogev.

[Theory Seminar] Ran Ben Basat
Nov 13 @ 12:00 pm – 1:00 pm

Speaker: Ran Ben Basat
Affiliation: Technion

Title: Classic Network Measurement meets Virtual Switching

Abstract: In modern cloud infrastructures, each physical server often runs multiple virtual machines and employs a software Virtual Switch (VS) to handle their traffic. In addition to switching, the VS performs network measurements, such as identifying the most frequent flows, which are essential for networking applications such as load balancing and intrusion detection.

Unlike traditional streaming algorithms, which minimize the space requirements, the bottleneck in virtual switching measurement is the CPU utilization. In this talk, I will present new hardware-oriented algorithms and acceleration methods that optimize the update time for software, at the cost of a slight memory overhead.

Bio: Ran is a Ph.D. candidate at the Technion, Israel. He does research in streaming algorithms for networking applications, focusing on efficient processing and query speeds.

[Theory Seminar] Samson Zhou
Nov 29 @ 12:00 pm – 1:00 pm

Speaker: Samson Zhou
Affiliation: Purdue University

Title: Pattern Matching over Noisy Data Streams

Abstract: The identification of low-complexity structure in strings is a fundamental building block for many algorithms in computational biology or natural language processing. The general paradigm in these algorithms is to find either highly repetitive structure, in the form of periodicity or palindromes in a pre-processing stage, to filter out locations where a certain pattern cannot occur, thus improving efficiency.

Unfortunately, we must expect massive data to contain a number of small imperfections, such as through human error or mutations. This motivates the need to study structure in models of sublinear space, resilient to sources of noise. In this talk, we introduce several types of structure and noise, and discuss efficient algorithms to identify these structures over data streams.

As a warm-up, we provide an algorithm for identifying a longest common aligned substring of two inputs, resilient up to d errors of insertions, substitutions, or deletions. We then present a streaming algorithm for identifying the longest palindrome, resilient up to a threshold of d substitution errors. Finally, we discuss the problem of finding all periods of a string including up to d persistent changes or erasures. For each of these scenarios, we also provide complementary lower bounds.

Joint work with Funda Ergun, Elena Grigorescu, and Erfan Sadeqi Azer.

Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor’s in math and computer science, as well as a Master’s in computer science. He is a member of the Theory Group at Purdue, and his current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms.

[Theory] Venkata Gandikota @ Malone 228
Dec 6 @ 12:00 pm – 1:00 pm

Speaker: Venkata Gandikota
Affiliation: Johns Hopkins University

Title: NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Abstract: Establishing the complexity of Bounded Distance Decoding for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius).

We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length N and dimension K = O(N), we show that it is NP-hard to decode more than N-K-O(log N / log log N) errors.

These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called Moments Subset Sum, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.

This is a joint work with Badih Ghazi (MIT) and Elena Grigorescu (Purdue).

[Theory Seminar] Amirbehshad Shahrasbi @ Malone 228
Dec 13 @ 12:00 pm – 1:00 pm

Speaker: Amirbehshad Shahrasbi
Affiliation:Carnegie Mellon University

Title: Synchronization Strings
In this talk, I will introduce “synchronization strings”, mathematical objects which provide a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions in communication problems. Synchronization errors are strictly more general and much harder to deal with than more commonly studied symbol corruption and symbol erasure errors. For every eps > 0, synchronization strings allow to index a sequence such that one can efficiently transform k synchronization errors into (1+eps)k erasure and corruption errors. This powerful new technique has many applications.
A straight forward application of our synchronization string based indexing method gives a simple black-box construction which transforms any error correcting code (ECC) into an equally efficient insertion-deletion code with only a small increase in the alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs into the realm of insertion-deletion codes. Most notably, for the complete noise spectrum, we obtain efficient near-MDS insertion-deletion codes which get arbitrarily close to the optimal rate-distance trade-off given by the Singleton bound.
Further applications of synchronization strings will be discussed including a general method of simulating symbol corruption channels over any given insertion-deletion channel, an efficient and near-optimal coding scheme for interactive communication over insertion-deletion channels, and list-decodable insertion-deletion codes.
This talk is based on joint works with Bernhard Haeupler and Ellen Vitercik from CMU.
[Theory Seminar] Samson Zhou
Mar 14 @ 12:00 pm – 1:00 pm

Speaker: Samson Zhou
Affiliation: Purdue University

Title: Password Hashing and Graph Pebbling

Abstract: Although the passwords of users are no longer being stored, we show an offline attacker is compelled to crack all stolen passwords under current security recommendations. Memory hard functions have been proposed as moderately expensive cryptographic tools for password hashing. The cryptanalysis of these functions has focused on the cumulative memory complexity and the energy complexity of the function. The first metric measures how much memory users must commit to evaluating a function, while the second metric measures how much energy users must commit. We prove these evaluations reduce to pebbling games on graphs but show that a tool for exact cryptanalysis of functions is unlikely to exist. Nevertheless, we provide asymptotic upper and lower bounds on several families of functions, including Argon2i, the winner of the password hashing competition that is currently being considered for standardization by the Cryptography Form Research Group of the Internet Research Task Force.

Joint work with Jeremiah Blocki, Ben Harsha, Ling Ren

Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor’s in math and computer science, as well as a Master’s in computer science. He is a member of the Theory Group at Purdue and a winner of the Sigma Xi Research Awards Competition for graduate students in engineering. His current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms.

[Theory Seminar] Sai Lakshmi Bhavana Obbattu
Jul 2 @ 12:00 pm – 1:00 pm

Speaker: Sai Lakshmi Bhavana Obbattu
Affiliation: IISC Bangalore, India

Title: Privacy Amplification from Non-malleable Codes

The goal of a Privacy Amplification (PA) protocol is to allow two parties, who start out sharing a non-uniform secret ‘w’, to agree on a uniform secret ‘k’, in the presence of a computationally unbounded man-in-the-middle adversary. An interactive PA protocol is rated based on three parameters: 1) Number of rounds, 2) Entropy loss (entropy of w – |k|), and 3) Min-entropy requirement for w, while the asymptotically optimal parameters are 2, O(s) and O(s+log n) respectively (where s is the security parameter and n =|w|). There have been two popular approaches to solve this problem: one using use bit authentication protocols and the other using non-malleable extractors, but none of the prior protocols using these approaches had all asymptotically optimal parameters.

We give an alternate approach to solve the problem using Non-malleable Codes (NMCs). This approach results in a 8-round protocol with min-entropy requirement O(s+log n) and an entropy loss of O(s log s). Augmented NMCs with better parameters would result in optimal entropy loss of O(s). Our result is one of the first information theoretic applications of NMCs. In this talk, I will introduce NMCs and show connection of NMCs to PA.

In a concurrent and independent work, Xin Li gives a protocol with asymptotically optimal parameters based on non-malleable extractors. Because all known approaches have large hidden constants, exploring alternatives is necessary if we hope to get practical concrete parameters

The talk is based on:

Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu and Sruthi Sekar. Privacy Amplification from Non-malleable Codes. (

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu and Sruthi Sekar. Non-malleable Randomness Encoders and their Applications (Eurocrypt 2018)

Bio: Sai Lakshmi Bhavana Obbattu is a doctoral student at Indian Institute of Science(IISc), Bangalore, advised by Dr. Bhavana Kanukurthi. Her publication venues include the Theory of Cryptography Conference (TCC) and Eurocrypt. Her TCC publication on Four-state Non-malleable Codes was invited to the Journal of Cryptology. She received her Integrated Dual Degree (B.Tech and M.Tech) from IIT(BHU), Varanasi. Her research interests include Non-malleable codes, Privacy Amplification and Applied Multi-party computation.

[Theory Seminar] Akash Kumar @ Malone 338
Aug 23 @ 12:00 pm – 1:00 pm

Speaker: Akash Kumar
Affiliation: Purdue University
Location: Malone 338 (note change of location)

Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided query complexity.

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \varepsilon n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result.

By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt{n}) lower bound of Czumaj et al (RSA 2014).

Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_{2,k}, (k\times 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).

(Joint work with C. Seshadhri and Andrew Stolman).

[Theory Seminar] Welcome and Introductions
Sep 5 @ 12:00 pm – 1:00 pm

Welcome and Introductions

[Theory Seminar] Zhengzhong Jin
Sep 12 @ 12:00 pm – 1:00 pm

Speaker: Zhengzhong Jin
Affiliation: JHU

Title: Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors

We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length n and edit error upper bound k, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is Θ(k log n/k). However, known constructions are far from achieving these bounds.

We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(k log^2 n/k). This significantly improves the previous best known deterministic protocol, which has sketch size O(k^2+k log^2 n). For binary insdel codes, we obtain the following results:

1. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log^2 n/k). In particular this implies an explicit family of binary insdel codes that can correct ε fraction of insertions and deletions with rate 1−O(ε log^2(1/ε))=1−\tilde {O}(ε).

2. An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log n). This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes.

In obtaining our results we introduce the notion of ε-self matching hash functions and ε-synchronization hash functions. We believe our techniques can have further applications in the literature.

[Theory Seminar] Marius Zimand
Oct 3 @ 12:00 pm – 1:00 pm

Speaker: Marius Zimand
Affiliation: Towson University

Title: An operational characterization of mutual information in algorithmic information theory

Abstract: An operational interpretation of the concept of mutual information in the framework of Kolmogorov complexity has been elusive till now. We show that the mutual information of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We show that if the communication complexity drops below the established threshold then only very short secret keys can be obtained.

This is joint work with Andrei Romashchenko.

[Theory Seminar] Yasamin Nazari
Oct 10 @ 12:00 pm – 1:00 pm

Speaker: Yasamin Nazari
Affiliation: JHU

Title: Distributed Distance-Bounded Network Design Through Distributed Convex Programming

Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner, this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call “distance-bounded network design convex programs”. These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in O((D/ϵ)logn) rounds in the LOCAL model and finds a (1+ϵ)-approximation to the optimal LP solution for any 0<ϵ≤1, where D is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic 3- and 4-Spanner, Directed k-Spanner, Lowest Degree k-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any "heavy" computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.

[Theory Seminar] Karthik Abinav Sankararaman @ Malone 228
Oct 17 @ 12:00 pm – 1:00 pm

Speaker: Karthik Abinav Sankararaman
Affiliation: University of Maryland

Title: Adversarial Bandits with Knapsacks

Abstract: In this talk we will discuss the multi-armed bandits problem with resource constraints under the adversarial setting. In this problem, we have an interactive and repeated game between the algorithm and an adversary. Given T time-steps, d resources, m actions and budgets B1, B2, .. Bd, the algorithm chooses one of the m actions at each time-step. An adversary then reveals a reward and consumption for each of the d resources corresponding to this action. The time-step at which the algorithm runs out of the d resources (i.e., the total consumption for resource j > Bj), the game stops and the total reward is the sum of rewards obtained until the stopping time. The goal is to maximize the competitive ratio; the ratio of the total reward of the algorithm to the expected reward of a fixed distribution that knows all the rewards and consumption ahead of time. We give an algorithm for this problem whose competitive ratio is tight (matches the lower-bound). Moreover the algorithmic tools extends in an (almost) black-box fashion to also give an algorithm for the stochastic setting thus giving a “best-of-both-worlds” algorithm where the algorithm need not know a-priori if the input is adversarial or i.i.d. Finally we conclude with applications and special cases including the Dynamic Pricing problem.

This talk is based on a recent working paper with Nicole Immorlica, Rob Schapire and Alex Slivkins.

[Theory Seminar] Nithin Varma
Oct 24 @ 12:00 pm – 1:00 pm

Speaker: Nithin Varma
Affiliation: Boston University

Title: Separating erasures and errors in property testing using local list decoding

Corruption in data can be in the form of erasures (missing data) or errors (wrong data). Erasure-resilient property testing (Dixit, Raskhodnikova, Thakurta, Varma ’16) and tolerant property testing (Parnas, Ron, Rubinfeld ’06) are two formal models of sublinear algorithms that account for the presence of erasures and errors in input data, respectively.

We first show that there exists a property P that has an erasure-resilient tester whose query complexity is independent of the input size n, whereas every tolerant tester for P has query complexity that depends on n. We obtain this result by designing a local list decoder for the Hadamard code that works in the presence of erasures, thereby proving an analog of the famous Goldreich-Levin Theorem. We also show a strengthened separation by proving that there exists another property R such that R has a constant-query erasure-resilient tester, whereas every tolerant tester for R requires n^{Omega(1)} queries. The main tool used in proving the strengthened separation is an approximate variant of a locally list decodable code that works against erasures.

Joint work with Sofya Raskhodnikova and Noga Ron-Zewi.

[Theory Seminar] Jalaj Upadhyay
Nov 7 @ 12:00 pm – 1:00 pm

Speaker: Jalaj Upadhyay
Affiliation: JHU

Title: Differentially Private Spectral Sparsification of Graphs
In this talk, we will discuss differentially private spectral sparsification of graphs. We argue that traditional spectral sparsification where the output graph is a subgraph of the input graph is not possible with differential privacy. This motivates us to define a relaxed version of spectral sparsification of graphs.

We consider edge-level privacy, i.e., neighboring graphs differs in one edge with weight one. We give efficient $(\alpha,\beta)$-differentially private algorithms that, on input a dense graph G, construct a spectral sparsification of G. Our output graphs has $ O(n/\eps^2)$ weighted edges, which matches the best known non-private algorithms.

We can use our private sparse graph to solve various combinatorial and learning problems on graphs efficiently while preserving differential privacy. Some examples include all possible cut queries, Max-Cut, Sparse-Cut, Edge-Expansion, Laplacian eigenmaps, etc.

This talk is based on a joint work with Raman Arora and Vladimir Braverman.

Capital Area Theory Day @ Georgetown University
Nov 16 all-day
[Theory Seminar] Ke Wu
Dec 5 @ 12:00 pm – 1:00 pm

Speaker: Ke Wu
Affiliation: Johns Hopkins University

Title: Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Synchronization strings are recently introduced by Haeupler and Shahrasbi (STOC 2017) in the study of codes for correcting insertion and deletion errors (insdel codes). They showed that for any parameter ε>0, synchronization strings of arbitrary length exist over an alphabet whose size depends only on ε. Specifically, they obtained an alphabet size of O(ε^{−4}), which left an open question on where the minimal size of such alphabets lies between Ω(ε^{1}) and O(ε^{−4}). In this work, we partially bridge this gap by providing an improved lower bound of Ω(ε^{−3/2}), and an improved upper bound of O(ε^{−2}). We also provide fast explicit constructions of synchronization strings over small alphabets.

Further, along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant ε<1. We show that one can construct ε-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.

[Theory Seminar] Sami Davies
Jan 16 @ 12:00 pm – 1:00 pm

Speaker: Sami Davies
Affiliation: University of Washington

Title: A Tale of Santa Claus, Hypergraphs, and Matroids
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child i has for a present j is of the form p_{ij} \in \{0,p_j\}. A polynomial time algorithm by Annamalai et al. gives a 12.33-approximation algorithm and is based on a modification of Haxell’s hypergraph matching argument.

In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxell’s augmentation tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a (4 +\varepsilon)-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus.

[Theory Seminar] Jalaj Upadhyay
Feb 6 @ 12:00 pm – 1:00 pm

Speaker: Jalaj Upadhyay
Affiliation: Johns Hopkins Universit

Title: Towards Robust and Scalable Private Data Analysis

In the current age of big data, we are constantly creating new data which is analyzed by various platforms to improve service and user’s experience. Given the sensitive and confidential nature of these data, there are obvious security and privacy concerns while storing and analyzing such data. In this talk, I will discuss the fundamental challenges in providing robust security and privacy guarantee while storing and analyzing large data. I will also give a brief overview of my contributions and future plans towards addressing these challenges.

To give a glimpse of these challenges in providing a robust privacy guarantee known as differential privacy, I will use spectral sparsification of graphs as an example. Given the ubiquitous nature of graphs, differentially private analysis on graphs has gained a lot of interest. However, existing algorithms for these analyses are tailored made for the task at hand making them infeasible in practice. In this talk, I will present a novel differentially private algorithm that outputs a spectral sparsification of the input graph. At the core of this algorithm is a method to privately estimate the importance of an edge in the graph. Prior to this work, there was no known privacy preserving method that provides such an estimate or spectral sparsification of graphs.

Since many graph properties are defined by the spectrum of the graph, this work has many analytical as well as learning theoretic applications. To demonstrate some applications, I will show more efficient and accurate analysis of various combinatorial problems on graphs and the first technique to perform privacy preserving manifold learning on graphs.

[Theory Seminar] Martin Farach-Colton
Feb 13 @ 12:00 pm – 1:00 pm

Speaker: Martin Farach-Colton
Affiliation: Rutgers University

Title: TBA

Abstract: TBA