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

[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] Martin Farach-Colton
Feb 13 @ 12:00 pm – 1:00 pm

Speaker: Martin Farach-Colton
Affiliation: Rutgers University

Title: TBA

Abstract: TBA