# 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 West Village H 366 (map). 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. Oct 26, 201612:30PM Matt Dippel and Chin Ho Lee Short Talks 366 WVH November 1, 201612:30PM Lorenzo Orecchia, Boston University First-Order Iterative Methods in the Design of Fast Algorithms: from Multiplicative Weight Updates to Nesterov's Method 366 WVH (Abstract) Fast iterative methods from Convex Optimization play a crucial role in a number of recent breakthroughs in the design of nearly-linear-time algorithms for fundamental combinatorial problems, such as maximum flow and graph partitioning. Multiplicative Weight Updates, Gradient Descent, and Nesterov's Method have become a mainstay in the construction and analysis of fast algorithms. The power of these approaches raises a number of questions: What is the exact relation between Multiplicative Weight Updates and Gradient Descent? Why do Multiplicative Weight Updates show up in so many settings? What is the intuition behind Nesterov's iterative algorithm that achieves the asymptotically optimal iteration count for smooth convex functions? In this survey talk, I will provide answers by presenting a unified framework that reveals the power and limitations of each method and provides much needed geometric intuition. Among other insights, I will explain how Multiplicative Weight Updates are a particular instance of a dual iterative method, known as Mirror Descent, and how Nesterov's algorithm can be naturally derived as a combination of Mirror and Gradient Descent. As an example of the application of these insights, I will also discuss their crucial role in recent progress in the nearly-linear-time solution of packing linear programs, both in parallel and sequentially. Nov 9, 201612:30PM Mitali Bafna and Hamid Jahanjou Short Talks 366 WVH Nov 16, 201612:30PM Harry Lang, Johns Hopkins New Frameworks for Offline and Streaming Coreset Constructions 366 WVH (Abstract) In the streaming model, data points arrive sequentially and algorithms attempt to use a sublinear amount of memory. For a class of clustering functions (including k-means, k-median, and L_p norms), we introduce a new technique for converting a coreset construction in the RAM model into a coreset construction in the streaming model. On a stream of n points, our method yields streaming coreset algorithms requiring the storage of O(S + k log n) points, where S is the size of the coreset. The previous state-of-the-art required O(S log^3 n) points. Note that S = \Omega(k), so this improves all parameters. In the RAM setting, we improve the size of coresets for a larger class of problems. This includes coresets for k-means with non-negative weights that depend on k as k \log k, and a Euclidean construction where the coreset size is independent of the dimension. Nov 23, 2016 Thanksgiving - No Seminar Nov 30, 201612:30PM Ankit Garg, MSR Algorithmic and optimization aspects of Brascamp-Lieb inequalities 411 Ell Hall (Abstract) The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute: - Feasibility of BL-datum - The optimal BL-constant - A weak separation oracle for the BL-polytope The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors provided a polynomial time algorithm recently. This will be based on joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson. Dec 07, 201612:30PM Vitaly Shmatikov, Cornell Tech Breaking web applications built on top of encrypted data 411 Ell Hall (Abstract) Mylar is a framework by Popa et al. that uses multi-key searchable encryption (MKSE) to build Web applications on top of encrypted data. We demonstrate that (1) the Popa-Zeldovich model for MKSE does not imply security against either passive or active attacks; (2) Mylar-based Web applications reveal users’ data and queries to passive and active adversarial servers; and (3) Mylar is generically insecure against active attacks due to system design flaws. Our results show that the problem of securing client-server applications against actively malicious servers is challenging and still unsolved.