# Computer Science Theory at Northeastern

## PeopleCoursesSeminar

 Apr 14, 20162:50PM Gabor Lippner, Northeastern University Dept. of Mathematics Local algorithms on sparse graphs 366 WVH (Abstract) A local algorithm aims to compute some global structure on a graph using only simultaneous, local, decisions at the nodes. I will review recent developments on the possibilities and the limitations of such algorithms, and explain their connection to the theory of graph limits. Apr 7, 20161:30PM Huy Nguyen, TTI Chicago Small summaries, efficient algorithms and fundamental limits 366 WVH (Abstract) Challenges abound in modern large scale data analysis, ranging from the sheer volume of the data to its complex structure and the need for timely responses. A promising common approach centers on capturing key information from the data using concise representations that can be constructed in a distributed manner or from an evolving stream of data. In this talk, we will illustrate both the power and limitations of this approach using three research vignettes. In the first example, we describe an algorithmic framework for fundamental linear algebra problems based on short summaries. In the second example, we design distributed algorithms for a family of non-convex problems arising in learning applications. In the third example, we show that even basic statistical estimation tasks require large summaries. Apr 4, 201610:30AM Matt Weinberg, Princeton Algorithms for Strategic Agents 366 WVH (Abstract) When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional desiderata beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against strategic manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents. In this talk, I will focus on robustness against strategic manipulation, and present a new algorithmic framework for these settings. Specifically, I will present a black-box reduction from solving any optimization problem in strategic settings, where the input is held by selfish agents with interests of their own, to solving a perturbed version of that same optimization problem in traditional settings, where the input is directly given. I will further apply this framework to resolve two longstanding open problems: extending Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), and designing truthful mechanisms for job scheduling on unrelated machines (Nisan and Ronen 1999). Finally, I will briefly show how strategic considerations motivate nice questions in "traditional" areas of algorithm design as well, and present some of my work in convex optimization, parallel algorithms, and prophet inequalities. Mar 23, 201610:30AM Sofya Raskhodnikova, Penn State Sublinear-Time Algorithms 366 WVH (Abstract) Massive datasets are becoming increasingly common. What useful computations can be performed on a dataset when reading all of it is prohibitively expensive? This question, fundamental to several fields, is at the heart of the research area, called sublinear-time algorithms, that has provided important insights into fast approximate computation. In this talk, we will consider types of computational tasks central to sublinear-time algorithms: approximation, testing, and learning. We will see examples of sublinear-time algorithms in several domains. The algorithms themselves are typically simple and efficient, but their analysis requires insights into basic combinatorial, algebraic, and geometric questions. We will also discuss new directions in sublinear-time algorithms, including new computational tasks, new measures for accuracy guarantees, and new models for data access. These directions enable applications of sublinear-time algorithms in privacy, analysis of real-valued data, and situations where the data is noisy or incomplete. Mar 16, 201610:30AM Mohit Singh, Microsoft Research Redmond Computability of Maximum Entropy Distributions and its Applications in Approximation Algorithms 366 WVH (Abstract) In this talk I will discuss the problem of computing maximum entropy distributions over a discrete set of objects subject to observed marginals. While there has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, information theory, machine learning, combinatorics and algorithms, a rigorous and systematic study of how to compute such distributions had been lacking. In this talk, I will show that the problem of computing maximum entropy distributions, in a fairly general setting, is equivalent to a counting problem on the underlying set. One of the consequences of this equivalence is that, for several combinatorial settings, there is an efficient algorithm to compute max-entropy distributions. I will also talk about applications of maximum entropy distributions to design approximation algorithms for discrete optimization problems including the Traveling Salesman Problem (TSP). These results include the first improvements over the classical Christofides' algorithm from 1970's for TSP on graph metrics. Mar 15, 20164:00PM Nils Olberg, Aachen Approximation Algorithms for Group Communication Networks 366 WVH (Abstract) In the concurrent multicast problem, we are given a graph representing a communication network together with a set of sender-receiver pairs. The goal is to deliver the message of each sender to the corresponding receiver. The concurrent multicast problem and its variants are motivated by information dissemination problems arising in diverse network scenarios. In this talk, we consider two of the most prominent communication models, namely the telephone and the radio model. For each of these models, our aim to develop algorithms that give good approximation algorithms, since the underlying problems are known to be NP-hard. Using sparse partition covers we provide a first non-trivial bound for radio concurrent multicast. We further demonstrate the connection of telephone concurrent multicast to other network design problems, which motivates the development of approximation algorithms for the latter. Finally, we show that our methods can be extended to yield new results for minimum degree graph spanners. Mar 14, 201610:30AM Vipul Goyal, Microsoft Research India Advances in Non-Malleable Cryptography 366 WVH (Abstract) A central challenge in the design of secure systems is to defend against man-in-the-middle attacks, where an adversary can arbitrarily tamper with the messages exchanged by two parties over a communication channel. Starting with the early nineties, an important research goal in cryptography has been to build non-malleable'' cryptographic protocols that are resilient to such attacks. In this talk, I will describe my work that culminates this two-decade long research quest by constructing round-optimal non-malleable protocols based on almost minimal cryptographic assumptions. I will also discuss how the techniques developed in these works have transcended cryptography and found applications in randomness extraction, coding theory, and complexity theory. I will also briefly talk about my work on applied cryptography and its impact. Feb 29, 201610:30AM Timothy Chan, University of Waterloo Geometric Data Structures: A Whirlwind Tour 366 WVH (Abstract) Although data structures in computational geometry have been studied since the 1970s, recent years have seen exciting new developments that deepen our theoretical understanding of some of the most fundamental problems in the area. In this talk, I will survey work on a number of these core problems, including (static and dynamic) 2D point location, 2D nearest neighbor searching, and orthogonal and nonorthogonal range searching. If time permits, I will also mention some unexpected applications of geometric data structures, to text indexing and all-pairs shortest paths. Feb 9, 201610:30AM Mary Wootters, Carnegie Mellon University Reed-Solomon Codes: from theory to practice 366 WVH (Abstract) Error correcting codes are an important tool in communication, and the family of Reed-Solomon (RS) codes is an especially important example. I'll introduce error correcting and Reed-Solomon codes, and I'll talk about three very different ways that RS codes have come up in my research. These three ways (none of which immediately has to do with communication) run the gamut from theory to practice. The first way, on the very theoretical end, is a combinatorial problem called list decoding, which has motivations in complexity theory. The second way, a bit more down-to-earth, has to do with designing schemes for distributed storage: how do we store a file on several servers robustly? The third way, on the practical side of things, is combinatorial group testing: in our work we collaborated with computational biologists to design better algorithms for high-throughput genetic screening and de novo gene sequencing. Jan 21, 20163:30PM Zhiwei Steven Wu, University of Pennsylvania Coordination Complexity: Small Information Coordinating Large Populations 366 WVH (Abstract) We initiate the study of a quantity that we call coordination complexity. In a distributed optimization problem, the information defining a problem instance is distributed among n parties, who need to each choose an action, which jointly will form a solution to the optimization problem. The coordination complexity represents the minimal amount of information that a centralized coordinator, who has full knowledge of the problem instance, needs to broadcast in order to coordinate the n parties to play a nearly optimal solution. We show that upper bounds on the coordination complexity of a problem imply the existence of good jointly differentially private algorithms for solving that problem, which in turn are known to upper bound the price of anarchy in certain games with dynamically changing populations. We show several results. We fully characterize the coordination complexity for the problem of computing a many-to-one matching in a bipartite graph by giving almost matching lower and upper bounds.Our upper bound in fact extends much more generally, to the problem of solving a linearly separable convex program. We also give a different upper bound technique, which we use to bound the coordination complexity of coordinating a Nash equilibrium in a routing game, and of computing a stable matching. Jan 6, 201612:00PM Chien-Chung Huang, Chalmers University of Technology Exact and Approximation Algorithms for Weighted Matroid Intersection 366 WVH (Abstract) We propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a $(1-\epsilon)$-approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving $W$ instances of the unweighted matroid intersection problem, where $W$ is the largest given weight. Furthermore, we can find a $(1-\epsilon)$-approximate solution via solving $O(\epsilon^{-1} \log r)$ instances of the unweighted matroid intersection problem, where $r$ is the smallest rank of the given two matroids.