# Computer Science Theory at Northeastern

## Theory Seminar

This semester the theory seminar will be every Thursday from 3:30-5:00PM in West Village H 366 (map). The Theory Seminar will occur every week whether or not we have a speaker. If we do not have a speaker, we will have short presentations from students or faculty. Write to Jonathan Ullman with suggestions for speakers or food!

## Spring Semester, 2017

 Apr 27, 20173:30PM Omri Weinstein, Columbia Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds 366 WVH Abstract We prove the first super-logarithmic lower bounds on the cell probe complexity of dynamic *boolean* (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new technique and use it to prove a ~ $\log^{1.5}(n)$ lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting *over $GF_2$* ([Pat07]). Proving an $\omega(\log n)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Patrascu's obituary [Tho13]. This result also implies the first $\omega(\log n)$ lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D "rectangle stabbing", and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of "weakly" simulating dynamic data structures using efficient *one-way* communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the "cell sampling" method of Panigrahy et al. [PTW10]. Joint work with Kasper Green-Larsen and Huacheng Yu. Apr 20, 20173:30PM Ankur Moitra, MIT Robust Statistics, Revisited RY 126 Abstract Starting from the seminal works of Tukey (1960) and Huber (1964), the field of robust statistics asks: Are there estimators that provably work in the presence of noise? The trouble is that all known provably robust estimators are also hard to compute in high-dimensions. Here, we study a basic problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithms that are able to tolerate a constant fraction of corruptions that is independent of the dimension. Additionally, we give several more applications of our techniques to product distributions and various mixture models. This is based on joint work with Ilias Diakonikolas, Jerry Li, Gautam Kamath, Daniel Kane and Alistair Stewart. Apr 13, 20173:30PM No seminar Apr 06, 20173:30PM No seminar Mar 30, 20173:30PM Ariel Hamlin and Lucianna Kiffer Short talks 366 WVH Mar 23, 20173:30PM Mehraneh Liaee, NEU Information Spreading in Dynamic Networks under Oblivious Adversaries 366 WVH Abstract We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, $n$ tokens are arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the n tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but a basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds. In previous work, it has been shown that under adaptive adversaries, every token forwarding algorithm requires $\Omega(n^2/\log n)$ rounds. In this paper, we study oblivious adversaries, which differ from adaptive adversaries in one crucial aspect--- they are oblivious to random choices made by the protocol. We present an $\tilde{\Omega}(n^{3/2})$ lower bound under an oblivious adversary for RANDDIFF, a natural algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We also present an $\tilde{\Omega}(n^{4/3})$ bound under a stronger notion of oblivious adversary for symmetric knowledge-based algorithms. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{\Omega}(n^{3/2})$ rounds. We also show an $\tilde{O}(n^{5/3})$ upper bound for RANDDIFF in a restricted class of oblivious adversaries, which we call paths-respecting. Mar 16, 20173:30PM Yael Kalai, MIT/MSR Interactive Coding with Constant Round and Communication Blowup 366 WVH Abstract We construct an interactive coding scheme, a notion introduced by Schulman (FOCS 1992, STOC 1993). Loosely speaking, we show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of *insertion* and *deletion* errors, while preserving computational efficiency, and blowing up the communication complexity and the *round* complexity by a constant factor that approaches 0 as the error-rate approaches 0. Previous works were not concerned with the round complexity, and typically assumed that one bit is sent per round. Moreover, most previous works (with the exception of the recent work of Braverman et. al.) considered only substitution errors or erasures errors. We consider the model where in each round each party may send a message of *arbitrary*, where the length of the messages and the length of the protocol may be adaptive, and may depend on the private inputs of the parties and on previous communication. This model is known as the (synchronous) message passing model, and is commonly used in distributed computing, and is the most common model used in cryptography. This is joint work with Klim Efremenko and Elad Haramaty. Mar 9, 20173:30PM No seminar - Spring Break Mar 2, 20173:30PM Gautam Kamath, MIT Some Frontiers in Distribution Testing 366 WVH Abstract Given samples from an unknown distribution p, does it have some property, or is it far from every distribution possessing this property? This question has received enormous attention in statistics, information theory, and theoretical computer science. Some properties of interest include: -Is p equal to a known distribution q? -Are the marginals of p independent? -Is the mass function of p monotone increasing? In this talk, I will discuss some recent results and directions on the frontiers of distribution testing. The main focus will be on testing whether a distribution belongs to a particular class, but I'll also talk about some newer directions, including testing on high-dimensional domains under structural assumptions (i.e., where the underlying distribution is a graphical model) and testing while maintaining differential privacy. Based on joint works with Jayadev Acharya, Bryan Cai, Constantinos Daskalakis, and Nishanth Dikkala. Feb 21, 20173:30PM Jalaj Upadhyay, Penn State Fast and Space-Optimal Differentially-Private Low-Rank Factorization in the General Turnstile Update Model 366 WVH Abstract The problem of low-rank factorization of an m x n matrix $A$ requires outputting a singular value decomposition: an m x k matrix $U$, an n x k matrix $V$, and a k x k diagonal matrix $D$ such that $U D V^T$ approximates the matrix $A$ in the Frobenius norm. In this talk, we study releasing differentially-private low-rank factorization of a matrix in the general turnstile update model. We give a differentially-private algorithm instantiated with respect to a privacy level stronger than privacy levels for this and related problems studied in previous works, namely that of Blocki et al.(FOCS 2012), Dwork et al. (STOC 2014), Hardt and Roth (STOC 2012, STOC 2013), and Hardt and Price (NIPS 2014). We consider two matrices $A$ and $A'$ as neighboring if $A - A'$ can be represented as an outer product of two unit vectors. Our private algorithm with respect to this privacy level incurs optimal additive error. We also prove a lower bound that shows that the space required by this algorithm is optimal up to a logarithmic factor. Based on the paper arXiv:1604.01429 Feb 16, 20173:30PM Adam Sealfon, MIT Network Oblivious Transfer 366 WVH Abstract Motivated by the goal of improving the concrete efficiency of secure multiparty computation (MPC), we study the possibility of implementing an infrastructure for MPC. We propose an infrastructure based on oblivious transfer (OT), which would consist of OT channels between some pairs of parties in the network. We devise information-theoretically secure protocols that allow additional pairs of parties to establish secure OT correlations using the help of other parties in the network in the presence of a dishonest majority. Our main technical contribution is an upper bound that matches a lower bound of Harnik, Ishai, and Kushilevitz (Crypto 2007), who studied the number of OT channels necessary and sufficient for MPC. In particular, we characterize which n-party OT graphs G allow t-secure computation of OT correlations between all pairs of parties, showing that this is possible if and only if the complement of G does not contain as a subgraph the complete bipartite graph $K_{n-t,n-t}$. Joint work with Ranjit Kumaresan and Srinivasan Raghuraman. Feb 9, 20173:30PM Talk cancelled due to weather Feb 2, 20173:30PM Constantinos Daskalakis, MIT Ten Steps of EM Suffice for Mixtures of Two Gaussians 108 WVH Abstract We provide global convergence guarantees for the expectation-maximization (EM) algorithm applied to mixtures of two Gaussians with known covariance matrices. We show that EM converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that in one dimension ten steps of the EM algorithm initialized at infinity result in less than 1% error estimation of the means. Joint work with Christos Tzamos and Manolis Zampetakis. Jan 26, 20173:30PM No talk Jan 19, 20173:30PM Stratis Ioannidis, Northeastern Secure Function Evaluation at Scale 366 WVH Abstract Secure Function Evaluation (SFE) allows an interested party to evaluate a function over private data without learning anything about the inputs other than the outcome of this computation. This offers a strong privacy guarantee: SFE enables, e.g., a medical researcher, a statistician, or a data analyst, to conduct a study over private, sensitive data, without jeopardizing the privacy of the study's participants (patients, online users, etc.). Nevertheless, applying SFE to "big data" poses several challenges. First, beyond any computational overheads due to encryptions and decryptions, executing an algorithm securely may lead to a polynomial blowup in the total work compared to execution in the clear. For large datasets, even going from linear to quadratic complexity is prohibitive. Second, secure evaluations of algorithms should also maintain parallelizability: an algorithm that is easy to parallelize in the clear should also maintain this property in its SFE version, if its execution is to scale. This poses a challenge, as communication patterns between processors may reveal a lot about the private inputs. In this talk, we show that several machine learning and data mining algorithms can be executed securely while leading to only (a) a logarithmic blow-up in total work and (b) a logarithmic increase in the execution time when executed in parallel. Our techniques generalize to any algorithm that is graph-parallel, i.e., can be expressed through a sequence of scatter, gather, and apply operations. This includes several algorithms of practical interest, including page rank, matrix factorization, and training neural networks. Jan 12, 20173:30PM Jonathan Ullman, Northeastern Algorithmic Stability for Adaptive Data Analysis 366 WVH Abstract Adaptivity is an important feature of data analysis - the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated a general formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. Specifically, suppose there is an unknown distribution $P$ and a set of $n$ independent samples $x$ is drawn from $P$. We seek an algorithm that, given $x$ as input, accurately answers a sequence of adaptively chosen "queries" about the unknown distribution $P$. How many samples $n$ must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? We give new upper bounds on the number of samples n that are needed to answer statistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015; NIPS, 2015). As in Dwork et al., our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that the stability notion guaranteed by differential privacy implies low generalization error. Joint work with Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, and Uri Stemmer. Jan 03, 20172:00PM Li-Yang Tan, TTI-Chicago Theory Seminar 166 WVH Abstract We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an $n$-variable $poly(n)$-clause CNF formula $F$ that has $|F-1(1)| /eq \epsilon 2n$, runs in time $nO^~(loglogn)2$ for $\epsilon \geq 1/\polylog(n)$ and outputs a satisfying assignment of $F$. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time $n\Omega^~(logn)$ even for constant $\epsilon$. Joint work with Rocco Servedio.