# Computer Science Theory at Northeastern

## Theory Lunch (New)

This semester we are instituting a new theory lunch! Lunch will be every Wednesday from 12:30-2:00PM in WVH 366. Theory lunch 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!

## Fall Semester, 2016

 Sep 21, 201612:30PM Daniel Wichs and Jack Doerner Welcome Back + Short Talks 366 WVH Sep 28, 201612:30PM Yaron Singer, Harvard Submodular Optimization under Noise 366 WVH Abstract In this talk we will consider the problem of maximizing a monotone submodular function under noise. There has been a great deal of work on optimization of submodular functions under various constraints, with many algorithms that provide desirable approximation guarantees. However, in many applications we do not have access to the function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under a cardinality constraint when given access to a noisy oracle of the function. Oct 05, 201612:15PM Huy Nguyen, Northeastern Heavy hitters via cluster-preserving clustering 366 WVH Abstract In the turnstile L_p heavy hitters problem with parameter eps, one must maintain a high-dimensional vector x in R^n subject to updates of the form update(i, Delta), which increases x_i by Delta, where i is in [n], and Delta is an integer. Upon receiving a query, the goal is to report every heavy hitter'' i in[n] with |x_i| >= eps*|x|_p as part of a list L, which is a subset of [n] of size O(1/\eps^p), i.e. proportional to the maximum possible number of heavy hitters. In fact we solve the stronger tail version, in which L should include every i such that |x_i| >= \eps |x_{proj{1/eps^p}}|_p and |x_i| > 0, where x_{proj{k}} denotes the vector obtained by zeroing out the largest k entries of x in magnitude. We provide a new algorithm, which in the most general turnstile model achieves optimal O(\eps^{-p}\log n) space, O(\log n) update time, and fast O(\eps^{-p}\poly(\log n)) query time, providing correctness whp. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We thus need a cluster-preserving clustering'' algorithm, that partitions the graph into clusters with the promise of not destroying any original cluster. To do this we first apply standard spectral graph partitioning, and then we use some novel combinatorial techniques to modify the cuts obtained so as to make sure that the original clusters are sufficiently preserved. Our cluster-preserving clustering may be of broader interest much beyond heavy hitters. Joint work with Kasper Green Larsen, Jelani Nelson, and Mikkel Thorup. Oct 12, 201612:30PM Mohsen Ghaffari, MIT/ETH Zurich Improved Local Distributed Graph Algorithms 366 WVH (Abstract) How can the computers in a network interact and communicate to solve the network's graph problems efficiently? This is the subject of the area of (local) distributed graph algorithms, which dates back to the 1980s. The recent years have witnessed significant developments in this classical area. In this talk, we survey some of these developments. Noting the gap between randomized and deterministic distributed graph algorithms, the talk has three (closely-related) parts: 1) On the randomized side, we present the first nearly-optimal randomized distributed algorithm for maximal independent set. Using well-known reductions, this provides a unified efficient algorithm for all the classical problems of the area. 2) On the deterministic side, we present an improved deterministic distributed algorithm for edge coloring, which almost settles a quarter-century old open problem. 3) We conclude with mentioning a surprising result that pinpoints the gap between randomized and deterministic distributed algorithms: we present a rudimentary-looking rounding problem, which admits a trivial 0-round randomized algorithm, and prove that if one can solve it deterministically in polylog(n) rounds, we would get polylog(n)-round deterministic distributed algorithms for all the local problems. The latter remains the most well-known open question of the area. Oct 19, 201612:30PM Mor Weiss, Northeastern From Secure Computation to Zero-Knowledge Probabilistic Checking and Back Again 366 WVH (Abstract) In the past few decades, probabilistic checking techniques were shown to yield dramatic efficiency improvements in verifying proofs and approximating distance from error-correcting codes. We show connections between cryptography and "zero-knowledge" variants of these techniques, such as Probabilistically Checkable Proofs (PCPs) and PCPs of Proximity (PCPPs), and use them to improve the complexity of cryptographic protocols. In this talk we will discuss two constructions: 1. PCPs for NP with zero-knowledge guarantees, that can be verified non-adaptively, namely by making a single round of queries to the proof. Our construction is based on a novel connection to leakage-resilient circuits. 2. Zero-knowledge PCPPs for NP, a generalization of zero-knowledge PCPs, which we construct by combining standard PCPPs with secure multiparty computation protocols. Based on joint works with Yuval Ishai, Amit Sahai, Michael Viderman and Guang Yang.