Apr 14, 2016 2: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, 2016 1: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 nonconvex problems arising in learning applications. In the third example, we show that even basic statistical estimation tasks require large summaries.

Apr 4, 2016 10: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 blackbox 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 singleitem 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, 2016 10:30AM

Sofya Raskhodnikova, Penn State
SublinearTime 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 sublineartime algorithms, that has provided important insights into fast approximate computation.
In this talk, we will consider types of computational tasks central to sublineartime algorithms: approximation, testing, and learning. We will see examples of sublineartime 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 sublineartime algorithms, including new computational tasks, new measures for accuracy guarantees, and new models for data access. These directions enable applications of sublineartime algorithms in privacy, analysis of realvalued data, and situations where the data is noisy or incomplete.

Mar 16, 2016 10: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 maxentropy 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, 2016 4: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 senderreceiver 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 NPhard.
Using sparse partition covers we provide a first nontrivial 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, 2016 10:30AM

Vipul Goyal, Microsoft Research India
Advances in NonMalleable Cryptography
366 WVH
(Abstract)
A central challenge in the design of secure systems is to defend against maninthemiddle 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 ``nonmalleable'' cryptographic protocols that are resilient to such attacks.
In this talk, I will describe my work that culminates this twodecade long research quest by constructing roundoptimal nonmalleable
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, 2016 10: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 allpairs shortest paths.

Feb 9, 2016 10:30AM

Mary Wootters, Carnegie Mellon University
ReedSolomon Codes: from theory to practice
366 WVH
(Abstract)
Error correcting codes are an important tool in communication, and the family of ReedSolomon (RS) codes is an especially important example. I'll introduce error correcting and ReedSolomon 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 downtoearth, 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 highthroughput genetic screening and de novo gene sequencing.

Jan 21, 2016 3: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 manytoone 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, 2016 12:00PM

ChienChung 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.
