# Theory Seminar

## Upcoming talks

### Progress in Error-Correction: A Survey

Monday, May 8, 2017, 3:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: Error-correcting codes play a crucial role in safeguarding data against the adverse effects of noise during communication and storage. They are also powerful tools that in the arsenal of theoretical computer science and combinatorics. The central challenge in coding theory is to construct codes with minimum possible redundancy for different error models and requirements on the decoder, along with efficient algorithms for error-correction using those codes. Much progress has been made toward this quest in the nearly seven decades since the birth of coding theory. Several fundamental problems, however, are still outstanding, and exciting new directions continue to emerge to address current technological demands as well as connections to computational complexity and cryptography.

This talk will survey some of our recent works on error-correction in various models, such as:

• worst-case errors, where we construct list decodable codes with redundancy as small as the target error fraction;
• i.i.d. errors, where we show polar codes enable efficient error-correction even as the redundancy approaches Shannon capacity;
• bit deletions, where we give codes that can correct the largest known fraction of deletions;
• single symbol erasure, a model of renewed importance for tackling node failures in distributed storage, where we give novel repair algorithms for Reed-Solomon codes as well as simple new codes with low-bandwidth repair mechanisms.

Speaker bio: Venkatesan Guruswami (Venkat) is a Professor in the Computer Science Department at Carnegie Mellon University. He received his Bachelor’s degree from the Indian Institute of Technology at Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. He was a visiting researcher at Microsoft Research New England during Spring 2014.

Venkat’s research interests span several topics including coding and information theory, complexity of approximate optimization and constraint satisfaction, pseudorandomness, and computational complexity.Venkat currently serves as the Editor-in-Chief of the ACM Transactions on Computation Theory, and on the editorial boards of the Journal of the ACM, SIAM Journal on Computing, and Research in the Mathematical Sciences. He served as the program committee chair for the 2015 IEEE Symposium on Foundations of Computer Science, and is a Technical Program co-chair of the 2018 IEEE International Symposium on Information Theory.He was an invited speaker at the 2010 International Congress of Mathematicians on the topic of “Mathematical Aspects of Computer Science.” Venkat is a recipient of the EATCS Presburger Award, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and the IEEE Information Theory Society Paper Award.

### Using Pricing to Manage the Cloud

Thursday, May 11, 2017, 1:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: Infrastructure-as-a-Service (IaaS) provides shared computing resources that users can access over the Internet, which has revolutionized the way that computing resources are utilized. Instead of buying and maintaining their own physical servers, users can lease virtualized compute and storage resources from shared cloud servers and pay only for the time that they use the leased resources. Yet as more and more users take advantage of this model, cloud providers face highly dynamic user demands for their resources, making it difficult for them to maintain consistent quality-of-service (QoS). We propose to use price incentives to manage these user demands. We investigate two types of pricing: spot pricing and volume discounts. Spot pricing creates an auction in which users can submit bids for spare cloud resources; however, these resources may be withdrawn at any time if users’ bids are too low and/or resources become unavailable due to other users’ demands. Volume discount pricing incentivizes users to submit longer-term jobs, which provide more stable resource utilization. We develop new user demand models to characterize behavior under these pricing schemes, and design optimal pricing and resource utilization strategies for both users and cloud providers.

Speaker bio: Carlee Joe-Wong is an assistant professor in the ECE department at Carnegie Mellon University, working at CMU’s Silicon Valley Campus. She received her Ph.D. from Princeton University in 2016 and is primarily interested in incentives and resource allocation for computer and information networks. In 2013–2014, Carlee was the Director of Advanced Research at DataMi, a startup she co-founded from her data pricing research. She received the INFORMS ISS Design Science Award in 2014 and the Best Paper Award at IEEE INFOCOM 2012, and was a National Defense Science and Engineering Graduate Fellow (NDSEG) from 2011 to 2013.

### Littlewood-Offord-Erdos type inequalities for polynomials of random variables

Tuesday, May 16, 2017, time TBA

MSR Redmond, Building 99, Room TBA

Abstract: Let Q = a_1 x_1 + … + a_n x_n where a_i are non-zero real numbers, and x_i are +-1 random variables. A classical result of Littlewood-Offord-Erdos showed that Pr (Q=0) is O( n^{-1/2} ). We are going to discuss the general case when Q is a polynomial (in the x_i) with arbitrary degree.

We will present several new results/methods, together with applications from random matrix theory and complexity theory.

Speaker bio: Currently, Van Vu holds the Percey F. Smith chair of mathematics at Yale University, after spending time at IAS, Microsoft Research, UC San Diego and Rutgers. His honors include a Sloan Fellowship (2002), the Polya Prize (2008), and the Fulkerson Prize (2012).

## Previous talks

### Streaming Lower Bounds for Approximating MAX-CUT

Monday, April 17, 2017, 3:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\e_* > 0$ such that any randomized streaming algorithm that computes a $(1+\e_*)$-approximation to MAX-CUT requires $\Omega(n)$ space on an $n$ vertex graph. By contrast, there are algorithms that produce a $(1+\e)$-approximation in space $O(n/\e^2)$ for every $\e > 0$. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the literature~\cite{Ber67}. The prior state of the art ruled out $(2-\epsilon)$-approximation in $\tilde{O}(\sqrt{n})$ space or $(1+\e)$-approximation in $n^{1-O(\e)}$ space, for any $\epsilon > 0$.

Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given some edges of a graph and they wish to determine if the union of these edges is $\e$-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of $\Omega(\sqrt{n})$ for this task when $\e=1/2$, and $n^{1-O(\e)}$ for every $\e>0$, even when one of the players is given a candidate bipartition of the promised to be bipartite with respect to this partition or $\e$-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an $n^{1-O(\e)}$communication protocol for this problem. In this work, we give an $\Omega(n)$ lower bound on the communication complexity of the original problem (without the extra information) for $\e=\Omega(1)$ in the three-player setting. Obtaining this $\Omega(n)$ lower bound on the communication complexity is the main technical result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity.

Speaker bio: Michael Kapralov is an Assistant Professor in the School of Computer and Communication Sciences at EPFL. He completed his PhD at Stanford where he was advised by Ashish Goel. After graduating from Stanford, I spent two years as a postdoc at the Theory of Computation Group at MIT CSAIL, and then a year at the IBM T.J. Watson Research Center. Michael is interested in theoretical foundations of big data analysis. Most of his algorithmic work is in sublinear algorithms, where specific directions include streaming, sketching, sparse recovery and Fourier sampling.

### Victoria Kostina (Caltech)

Thursday, April 13, 2017, 3:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: Consider a flying drone controlled from the ground by an observer who communicates with it via wireless. We are interested in how well the drone can be controlled via a channel that accepts r bits/sec. Formally, the controller of a linear stochastic system aims to minimize a quadratic cost function in the state variables and control signal, known as the linear quadratic regulator (LQR). We characterize the optimal tradeoff between the communication rate r bits/sec and the limsup of the expected cost b.

We consider an information-theoretic rate-cost function, which quantifies the minimum mutual information between the channel input and output, given the past, that is compatible with a target LQR cost. We provide a lower bound to the rate-cost function, which applies as long as the system noise has a probability density function, and which holds for a general class of codes that can take full advantage of the memory of the data observed so far and that are not constrained to have any particular structure.

Perhaps surprisingly, the bound can be approached by a simple variable-length lattice quantization scheme, as long as the system noise satisfies a smoothness condition. The quantization scheme only quantizes the innovation, that is, the difference between the controller’s belief about the current state and the encoder’s state estimate.

Speaker bio: Victoria Kostina joined Caltech as an Assistant Professor of Electrical Engineering in the fall of 2014. Previously, she worked as a postdoctoral researcher at Princeton with Prof. Sergio Verdu and as a Research Fellow at Simons Institute for the Theory of Computing.

Her research interests lie in information theory, random processes, coding, wireless communications, and control.

### Introduction to sampling-based motion planning

Tuesday, April 11, 2017, 3:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: Motion planning is a fundamental research area in robotics with applications in diverse domains such as graphical animation, surgical planning, computational biology and computer games. The basic problem of motion planning is concerned with finding a collision-free path for a robot in a workspace cluttered with obstacles.

Sampling-based algorithms, which were first described about two decades ago, have revolutionized the field of robotics by providing simple yet effective tools to cope with challenging instances of motion planning involving many degrees of freedom, and complex physical constraints. These algorithms, which trade completeness with applicability in practical settings, aim to capture the structure of the problem by randomly sampling robot configurations and connecting nearby samples.

In this talk I will give a brief introduction to sampling-based motion planning, with an emphasis on their theoretical properties. In particular, I will mention the seminal work of Karaman and Frazzoli (2011), and a recent connection between sampling-based techniques and random geometric graphs.

Speaker bio: Kiril Solovey is a Ph.D. student at the School of Computer Science, Tel-Aviv University, Israel, under the guidance of Dan Halperin. His research interests include sampling-based techniques for robot motion planning, multi-robot systems, and computational geometry. Kiril is a Clore Scholar and a recipient of the Best Student Paper award at Robotics: Science and Systems 2015.

### Towards More Efficient Optimization Algorithms

Tuesday, March 14, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: Many computational tasks can be solved via classical optimization methods such as gradient descent, SGD, LP, or SDP. In this talk, I will argue that this path of algorithm design may be restrictive and less efficient.

I will show instead how to develop novel optimization tools to enrich the dimension of algorithm design. In particular, I will present a “linear-coupling” framework, and apply it to obtain the fastest first-order algorithms for (1) packing LP, (2) stochastic convex optimization, and (3) stochastic non-convex optimization.

Speaker bio: Dr. Allen-Zhu is a postdoc member at IAS, and received his Sc.D. from MIT in 2015. He is a two-time IOI Gold Medalist, USACO World Champion, ACM/ICPC World-Final Gold Medalist, Google Codejam World 2nd-Place Winner, and recipient of a Simons Award and a Microsoft Azure Research Award. He publishes mostly in ICML, NIPS, STOC, and SODA.

### Algorithm design for massive data

Friday, March 3, 2017, 3:30 pm

MSR Redmond, Building 99, Room 1915

Abstract: The modern era is undergoing an explosive growth in the amount of available data, and quadratic or even linear-time algorithms can fall short of efficiency. Solving problems in this new scenario has become a major challenge for the computer science community. In this talk, I will highlight how the algorithmic perspective brings novel insights and leads to efficient methods for important problems in the big data environment.

I will first talk about algorithm design in massively parallel computing models. I will describe new algorithmic techniques to solve sequential dynamic programming problems under these models. The new parallel algorithms are near-optimal for a variety of classic dynamic programming problems, including longest increasing subsequence, optimal binary search tree, and weighted interval scheduling.

Second I will talk about algorithms for reconstructing the underlying structure of large data using random samples. I will present a density estimation framework based on piecewise polynomial approximation of probability distributions. The framework yields efficient density estimation algorithms for a wide range of structured distributions with near-optimal data usage.

Speaker bio: Xiaorui Sun is a computer scientist focused on algorithmic foundations of massive data. His research interest lies in massively parallel computing, sublinear algorithms, algorithmic graph theory and machine learning. Xiaorui graduated from Columbia University in 2016, under the supervision of Xi Chen. Currently, He is a Google Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley.

### New (provable) techniques for learning and inference in probabilistic graphical models

Tuesday, February 7, 2017, 10:30 am

MSR Redmond, Building 99, Room 1915

Abstract: A common theme in machine learning is succinct modeling of distributions over large domains. Probabilistic graphical models are one of the most expressive frameworks for doing this.

The two major tasks involving graphical models are learning and inference. Learning is the task of calculating the best fit graphical model from raw data, while inference is the task of answering probabilistic queries for a known graphical model (for example what is the marginal distribution of one of the variables or what is the distribution of a subset of variables, after conditioning on the values of some other subset of variables). Learning can be thought of as finding a graphical model that “explains” the raw data, while the inference queries extract the “knowledge” the graphical model contains.

This talk will concern new provable algorithms for performing both of these tasks. In the context of inference, I will talk about a new understanding of a class of algorithms for calculating partition functions, called variational methods through a combination of convex programming hierarchies — a recent area of interest in the area of combinatorial optimization — and entropy approximations based on low-order moments of a distribution. In the context of learning, I will talk about a new algorithm for learning noisy-or Bayesian networks, which are used for modeling the causal structure of diseases and symptoms. The approach is based on tensor decompositions, but deals with a substantial amount of structured noise which stems from the non-linear nature of the problem.

Speaker bio: I work in the intersection of machine learning and theoretical computer science, with the primary goal of designing provable and practical algorithms for problems arising in machine learning. Broadly, this includes tasks like clustering, maximum likelihood estimation, inference, and learning generative models. All of these tend to be non-convex in nature and intractable in general. However, in practice, a plethora of heuristics like gradient descent, alternating minimization, convex relaxations, and variational methods work reasonably well. In my research, I try to understand what are realistic conditions under which we can give guarantees of the performance of these algorithms, as well as devise new, more efficient methods.

### Community Detection in the Stochastic Block Model: Acyclic Belief Propagation

Monday, February 6, 2017, 10:30 am

MSR Redmond, Building 99, Room 1915

Abstract: The stochastic block model is one of the simplest models for a random graph with different types of vertices, known as communities. In this talk I will describe an efficient algorithm that distinguishes between vertices from different communities with nontrivial accuracy whenever the SBM’s parameters are above the Kesten-Stigum threshold, proving half of a conjecture by Decelle et al. I will also show that given exponential time it is sometimes possible to distinguish between communities with nontrivial accuracy below the KS threshold.

Speaker bio: Colin Sandon grew up in Vermont. He received his bachelor’s degree in math from MIT in 2012 with minors in Physics and Economics. He is a 2010 Putnam Fellow and a member of Phi Beta Kappa. He is currently a graduate student studying community detection in the stochastic block model at Princeton, and he expects to receive his PhD in 2017.

### Conformal growth rates and spectral geometry on unimodular random graphs

Friday, February 3, 2017, 15:30

MSR Redmond, Building 99, Room 1927

Abstract:

Speaker bio: James is a professor in computer science at the University of Washington.

### On statistical learning via the lens of compression

Friday, February 3, 2017, 10:00 am

MSR Redmond, Building 99, Room 1927

Abstract: Generalization and simplification are deeply related to each other: simpler explanations often reveal principles that apply more generally, and predictive scientific theories often boil down to a few simple (and deep) laws. This talk is about a manifestation of the “generalization–simplification” link within learning theory.

We will consider the following formal frameworks for generalization’ and simplification’.(i) Vapnik’s general learning setting — a standard statistical framework that formalizes generalization.(ii) Sample compression schemes — a combinatorial framework that formalizes simplification.This framework captures a common property of many learning procedures, like procedures for learning geometric shapes or algebraic structures.

First, we will consider the setting of binary classification. Littlestone and Warmuth showed that in this setting, the ability to simplify implies the ability to generalize, and asked whether the other direction holds. We will give an affirmative answer to this question.

We then extend the equivalence between compression and generalization to multiclass categorization, and to Vapnik’s general learning setting.

If time allows, we will demonstrate how this equivalence can be used to translate “statistical statements” (within the generalization setting) to “combinatorial statements” (within the compression setting), and vice versa. This translation reveals properties that may be difficult to find otherwise. For example, we will prove a separation result between agnostic and realizable-case learnability using Ramsey theory.

No knowledge in machine learning will be assumed in the talk.

This talk is based on joint works with Ofir David and Amir Yehudayoff.

Speaker bio: Shay is a research fellow at the Simons Institute for the Theory of Computing. He obtained his PhD from the Technion on July ’16, under the supervision of Amir Shpilka and Amir Yehudayoff. After graduating he has spent some time at MSR Hertzeliya, and at University of California San Diego. His research interests lie in the spectrum between combinatorics and theoretical computer science. These include machine learning, communication complexity, discrete geometry, and extremal combinatorics. In his PhD, he studied various aspects of data compression and representation – mostly in the contexts of machine learning and interactive communication complexity. In the past two years, he has mostly focused on theoretical machine learning.

### Protecting People from Algorithms (and Vice Versa)

Monday, January 30, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: Computing technologies today have made it much easier to gather personal data. Algorithms are constantly analyzing such personal information and making consequential decisions on people. The extensive use of algorithms also imposes the risks of algorithms mistreating people such as privacy violation or unfair discrimination. There is also a risk of people mistreating algorithms. For example, in a strategic environment people may have incentives to misreport their data to the algorithms for their own benefits.

In this talk, I will first present an overarching theme in my research—protecting people and algorithms from each other. In particular, my work seeks to (1) protect people from algorithms in developing algorithms with privacy and fairness guarantees and (2) aims to protect algorithms from people in providing algorithms that incentivize people’s truthful behavior.

I will then present two results in my work on differential privacy, a rigorous algorithmic notion for data privacy. The first result focuses on a fundamental problem in differential privacy—private query release. I will present a scalable algorithm that can accurately and privately answer a large collection of counting queries for high-dimensional data. In the second result, I will focus on a general framework for solving a family of economic optimization problems in a privacy-preserving manner. I will also demonstrate how differential privacy can be used as a novel tool to incentive truth-telling when the algorithms need to elicit input data from self-interested participants.

Speaker bio: Steven is currently a PhD candidate in computer science at the University of Pennsylvania, where he is co-advised by Michael Kearns and Aaron Roth. His primary research interests are in developing theory and algorithms for privacy-preserving data analysis. He has also been studying machine learning in economic environments, where he designs algorithms that learn from observed economic behavior and create desired incentives for the participants. His more recent research focuses on fairness in machine learning, where the goal is to provide fair decision-making algorithms that learn from personal data.

During the summer of 2015 and the spring of 2016, he was a research intern at Microsoft Research in New York City (MSR-NYC), and during the summer of 2016, he was also a research intern at Microsoft Research New England (MSR-NE).

### Complexity of Simplicity in Mechanism Design

Friday, January 27, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: Classical work in economics imposes two constraints on mechanism design: Individual Rationality (“you are better off participating in the mechanism than staying at home”) and Incentive Compatibility (“agents act selfishly”). In recent years it has been shown that even in very simple settings, the mechanism that is optimal (in theory) is extremely complicated. As an important step toward bridging theory and practice, we want to add a third constraint: Simplicity.

Speaker bio: Aviad Rubinstein is a PhD candidate at UC Berkeley, advised by Christos Papadimitriou. His research looks, through the “Lens of Computation”, at a variety of fundamental problems from evolution, statistics, stopping theory, and game theory. He is supported by a Microsoft Research PhD Fellowship. His papers were recently awarded the FOCS 2016 Best Paper Award, as well as Best Student Paper Awards at ITCS 2017, FOCS 2016, ITCS 2016, and STOC 2015.

### Regression, Elimination, and Sampling on Graphs

Monday, January 23, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: In this talk, we will survey a range of recent results on graph algorithms and optimization. We start by covering topics in regression and semi-supervised learning on graphs. Here, we will see new theoretical results using both combinatorial algorithms and optimization-based approaches, as well as practical applications of these methods. Next, we’ll take a look at some results on linear system solvers: the asymptotically fastest known solver for Laplacian matrices and the simplest known Laplacian solver. The latter is based on a novel notion of approximate Gaussian elimination and entirely avoids the need for graph-based algorithmic constructions. We’ll touch briefly on how simpler algorithms also allow us to develop nearly-linear time solvers for block-structured generalizations of Laplacians. Then, we will learn how advances in matrix martingale theory and ideas from approximate Gaussian elimination have led to new results in graph algorithms, including simple and powerful algorithms for semi-streaming graph sparsification and the first algorithm for sampling random spanning trees faster than matrix multiplication in weighted graphs. Finally, we will discuss some future challenges in the fields of algorithms and optimization.

Speaker bio: Rasmus Kyng is a PhD student at Yale University. His advisor is Prof Daniel Spielman. Before attending Yale, he received a BA in Computer Science from the University of Cambridge in 2011. His research interests include graph algorithms, optimization, applied and theoretical machine learning, and linear systems.

### New Algorithms for High-Dimensional Data

Thursday, January 19, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: A popular approach in data analysis is to represent a dataset in a high-dimensional feature vector space, and reduce a given task to a geometric computational problem. As it turns out, the running times of most of the classic geometric algorithms suffer from an exponential dependence on the dimension and are typically not applicable to the high-dimensional regime. This necessitates the development of new algorithmic approaches that overcome this “curse of dimensionality”. In this talk I will give an overview of my work in this area. In particular:

* I will describe new algorithms for the high-dimensional Nearest Neighbor Search (NNS) problem. Our algorithms improve, for the first time, upon the popular Locality-Sensitive Hashing (LSH) approach. The main insight behind the new algorithms is the use of hash functions that are *data dependent*, i.e., , that are carefully tailored to a given dataset. In contrast, prior algorithms used generic, data-oblivious hash families.

* Next, I will outline how to make the core component of the above algorithms—the optimal LSH for cosine distance—practical. This yields an implementation of LSH which is competitive with the state of the art heuristics for the NNS problem.

* Finally, I will show how to determine the limits of distance-preserving data sketching, i.e., vector compression methods that approximately preserve the distances between vectors. In particular, I will show the first non-trivial lower bound for the sketching complexity of the well-studied Earth Mover Distance.

The common theme that unifies these and other algorithms for high-dimensional data is the use of “efficient data representations”: randomized hashing, sketching, dimensionality reduction, metric embeddings, and others. One goal of the talk is to describe a holistic view of all of these techniques.

Speaker bio: Ilya Razenshteyn is a final year PhD student at MIT CSAIL advised by Piotr Indyk. His interests are revolving around algorithms for massive datasets with geometric structure. He graduated from the mathematics department of Moscow State University back in 2012.

### Leveraging Privacy in Data Analysis

Tuesday, January 17, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: My research focuses on applying differential privacy to problems in economics, statistical hypothesis testing, and adaptive data analysis in machine learning. At a high level, a differential private algorithm limits the sensitivity of the outcome to any individual data entry from an input dataset. We can leverage the stability guarantees of differential privacy to answer new questions in various areas outside theoretical computer science. This requires developing new differentially private algorithms as well as implementing existing techniques in novel ways. The results from my research can be split roughly into two main areas: 1) incorporating privacy as an additional constraint into an otherwise classical problem; 2) using privacy as a tool to solve new problems where privacy may not be a primary concern.

Typically in machine learning an analyst wants to be able to draw valid conclusions from a sample that generalizes to the population it was sampled from. The practice of data analysis has become an intrinsically adaptive process, where a particular dataset may be reused for several, adaptively chosen analyses. Unfortunately, much of the existing theory in statistical inference assumes that each analysis is selected independently of the data. Thus applying the classical theory to this adaptive setting leads to spurious results due to overfitting; in fact, this is suspected to be behind the prevalence of false discovery in empirical science [Simmons et al., 2011, Gelman and Loken, 2014, Wasserstein and Lazar, 2016]. In a surprising result from Dwork et al. 2015, they showed that differential privacy can help preserve statistical validity in adaptive data analysis. Building on this connection, my coauthors and I show that differential privacy can be used to perform statistically valid, adaptive hypothesis tests [Rogers, Roth, Smith, Thakkar 2016]. We then explore natural extensions of differential privacy that are better catered to adaptive data analysis, including allowing the privacy parameters to be chosen as a function of outcomes from previously run analyses [Rogers, Roth, Ullman, Vadhan 2016].

Speaker bio: Ryan Rogers is a Ph.D. candidate in the Applied Mathematics and Computational Sciences department at the University of Pennsylvania where he is advised by Michael Kearns and Aaron Roth. He has been a research intern at Microsoft in New York and at Harvard University’s Privacy Tools Project. He was president and co-founder of the SIAM student chapter at Penn. Prior to Penn, he graduated with distinction from Part III of the Mathematical Tripos at the University of Cambridge and earned his bachelors in mathematics and religious studies from Stetson University. Before graduate school, he worked at United Space Alliance as a computer scientist on the Space Station Training Facility at the Johnson Space Center in Houston, TX. In his free time, he enjoys rowing, hiking and mountain biking.

### Adventures with sum-of-squares (and randomness)

Monday, January 9, 2017, 10:30 am

MSR Redmond, Building 99, Room 1927

Abstract: The sum-of-squares hierarchy is a family of semidefinite programs that can capture any combinatorial optimization problem, allowing one to trade runtime for accuracy. The class of problems that sum-of-squares can solve efficiently is still not well-characterized—recently this has been a topic of intensive study in the theoretical computer science community, as the hierarchy has the potential to resolve long-standing open problems in the theory of approximation algorithms. In this talk, I will describe my own efforts towards characterizing the sum-of-squares hierarchy, through the lens of average-case problems. I’ll talk about sum-of-squares algorithms for refuting random constraint satisfaction problems, about sum-of-squares lower bounds for planted clique and other average-case problems, and about using sum-of-squares algorithms to obtain fast spectral algorithms.

Speaker bio: Tselil is a fifth year PhD student in Computer Science at UC Berkeley, advised by Prasad Raghavendra and Satish Rao, and supported by a National Science Foundation Fellowship and a UC Berkeley Chancellor’s Fellowship. Her research interests include spectral algorithms, spectral graph theory, convex programming, and approximation algorithms. Recently, her work has especially focused on understanding the power and limitations of the sum-of-squares semidefinite programming hierarchy.

## Archive (pre-2017)

Theory Seminar archive (including links to videos): 2003-2009, 2009-2016