Back to Events

Seminar Series

December 12

Barna Saha: Space & Time Efficient Algorithms for "Bounded Difference" Problems

Barna Saha, UMass Amherst

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-12-12 16:00:00 2017-12-12 17:00:00 America/New_York Barna Saha: Space & Time Efficient Algorithms for "Bounded Difference" Problems Abstract: Many fundamental sequence problems exhibit "bounded difference property", that is whenever the input changes slightly, the change in the output is also bounded. Some examples include the longest increasing subsequence problem (studied since Schensted, 1961), the string edit distance computation (studied since Levenshtein, 1965), the language edit distance problem (studied since Aho and Peterson, 1972), RNA Folding (studied since Jacobson and Nussinov, 1980) etc. For all these problems, there exist simple polynomial time algorithms based on dynamic programming. Dynamic programming is one of the most systematic ways of developing polynomial time algorithms, but it often suffers from high space and time complexity. In this talk, I will show a simple technique of amnesic dynamic programming using which we can improve either on time or space complexity of bounded difference problems allowing for additive approximations. For some of these problems, it is also possible to design an exact algorithm that runs faster than the corresponding dynamic programming using a reduction to bounded-difference (min,+)-matrix multiplication. Time permitting, I will discuss how this raises serious doubts to the All Pairs Shortest Path conjecture which is the cornerstone to show cubic-hardness of a large collection of fundamental graph and matrix problems. The talk is mainly based on my FOCS 2017 paper and will also allude to a joint work with Karl Bringmann, Fabrizio Grandoni and Virginia Vassilevska Williams that appeared in FOCS 2016. Patil/Kiva G449

December 05

Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares

Pravesh Kothari

Part Of

4:00P
- 5:00P

Location

G449
Add to Calendar 2017-12-05 16:00:00 2017-12-05 17:00:00 America/New_York Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares Abstract: We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These better guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers.Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample. G449

November 28

Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Kasper Green Larsen, Asst. Professor, Dept. of Computer Science, Aarhus University

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-11-28 16:00:00 2017-11-28 17:00:00 America/New_York Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds Abstract: In this talk, we prove the first super-logarithmic lower bounds on thecell probe complexity of dynamic boolean (a.k.a. decision) data structureproblems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower boundsand use it to prove a ??(lg^(1.5)n)lower bound on the operational time of a wide range of boolean datastructure problems, most notably, on the query time of dynamic rangecounting over F2 ([Pat'07]). Proving an ?(lgn)lower bound for this problem was explicitly posed as one of fiveimportant open problems in the late Mihai Patrascu's obituary [Tho'13].This result also implies the first ?(lgn)lower bound for the classical 2D range counting problem, one of themost fundamental data structure problems in computational geometry andspatial databases. We derive similar lower bounds for boolean versionsof dynamic polynomial evaluation and 2D rectangle stabbing, and for the(non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of ``weakly" simulating dynamicdata structures using efficient one-waycommunication protocols with small advantage over random guessing. Thissimulation involves a surprising excursion to low-degree (Chebychev)polynomials which may be of independent interest, and offers an entirelynew algorithmic angle on the ``cell sampling" method of Panigrahy etal. [PTW'10].Joint work with: Omri Weinstein and Huacheng Yu Patil/Kiva G449

November 14

Venkatesan Guruswami: Promise Constraint Satisfaction

Venkatesan Guruswami, CMU

Part Of

4:00P
- 5:00P

Location

PATIL/KIVA G449
Add to Calendar 2017-11-14 16:00:00 2017-11-14 17:00:00 America/New_York Venkatesan Guruswami: Promise Constraint Satisfaction Abstract: Given a 5-SAT instance admitting an assignment satisfying at least 2 literals in each clause, can one efficiently find a satisfying assignment that sets at least one literal to true in each clause? Given a 5-uniform hypergraph admitting a red-blue coloring of its vertices with exactly two red vertices in each hyperedge, can one efficiently find a red-blue coloring that leaves no hyperedge monochromatic? Given a graph admitting a homomorphism to the 7-cycle, can one efficiently 3-color it? The answers to these questions are: No (unless P=NP), yes, and open respectively. These are examples of *promise* constraint satisfaction problems (PCSP), where in the decision version, we need to distinguish instances satisfiable according to one set of predicates, from those that are unsatisfiable even under relaxed versions of those predicates. PCSPs generalize normal CSPs where the two sets of predicates are identical. The (recently resolved) famous dichotomy conjecture states that every CSP is either polytime decidable or NP-hard. Further, the tractable cases are precisely those admitting closure operations (called “polymorphisms”) that preserve the predicates defining the CSP. The landscape of PCSPs reveals several new phenomena and challenges on both the algorithmic and hardness fronts compared to the CSP world. This talk will describe some of our forays into better understanding PCSPs, which revolve around the notion of “weak polymorphisms.” We will sketch our hardness proof (with P. Austrin and J. Håstad) for the above promise k-SAT problem, based on a characterization of the weak polymorphisms as juntas. We will discuss a body of work (with J. Brakensiek) that develops the weak polymorphism framework to prove new hardness results for graph coloring and establish a complexity dichotomy for the case of Boolean symmetric PCSP. Numerous intriguing problems about PCSPs and the state of polymorphisms remain open, and we will mention a couple of them. PATIL/KIVA G449

November 07

Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions

Omer Paneth, MIT

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-11-07 16:00:00 2017-11-07 17:00:00 America/New_York Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions Abstract: The round complexity of zero-knowledge protocols is a long-standing open question in the theory of cryptography. Its study over the past three decades has revealed connections to other fundamental concepts such as non-black-box reductions and succinct proof systems. In the first part of the talk, I will survey the history of the question. In the second part, I will present a new result that resolves the question under a new hardness assumption. Roughly, the assumption asserts the existence of shrinking hash functions such that no polynomial-time algorithm, with advice of size k, can output much more than k colliding inputs. I will motivate this assumption and discuss additional applications. Based on joint works with Nir Bitansky, Zvika Brakerski, Yael Kalai and Vinod Vaikuntanathan. Patil/Kiva G449

October 31

Structure, randomness and universality

Noga Alon

Part Of

4:00P
- 5:00P

Location

G449 (Patil/Kiva)
Add to Calendar 2017-10-31 16:00:00 2017-10-31 17:00:00 America/New_York Structure, randomness and universality Abstract: What is the minimum possible number of vertices of a graph that contains every k-vertex graph as an induced subgraph ? What is the minimum possible number of edges in a graph that contains every k-vertex graph with maximum degree 3 as a subgraph ? These questions and related one were initiated by Rado in the 60s, and received a considerable amount of attention over the years, partly motivated by algorithmic applications. The study of the subject combines probabilistic arguments and explicit, structured constructions. I will survey the topic focusing on a recent asymptotic solution of the first question, where an asymptotic formula, improving earlier estimates by several researchers, is obtained by combining combinatorial and probabilistic arguments with group theoretic tools. G449 (Patil/Kiva)

October 24

Relative Error Tensor Low Rank Approximation

David Woodruff

Part Of

4:00P
- 5:00P

Location

G449 (Patil/Kiva)
Add to Calendar 2017-10-24 16:00:00 2017-10-24 17:00:00 America/New_York Relative Error Tensor Low Rank Approximation Abstract: We consider relative error low rank approximation of tensors with respect to the Frobenius norm: given an order-q tensor A, output a rank-k tensor B for which |A-B|_F?(1+?)OPT, where OPT =inf_{rank-k A?} |A?A?|_F. Despite the success on obtaining relative error low rank approximations for matrices, no such results were known for tensors. One structural issue is there may be no rank-k tensor A' achieving the above infinum. Another, computational issue, is that an efficient relative error low rank approximation algorithm for tensors would allow one to compute the tensor rank, which is NP-hard. We bypass these issues via (1) bicriteria and (2) parameterized complexity solutions. As an example, we give an algorithm which outputs a rank (k/?)^{q-1} tensor B for which |A?B|_F ? (1+?)OPT in nnz(A)+n?poly(k/?) time in the real RAM model for an n x n x ... n tensor. Here nnz(A) is the number of non-zero entries in A. For outputting a rank-k tensor, or even a bicriteria solution with rank-Ck for a certain constant C>1, we show an exp(k^{1-o(1)}) time lower bound under the Exponential Time Hypothesis. Our results also give the first relative error low rank approximations for tensors for a large number of robust error measures for which nothing was known, as well as column row and tube subset selection problems, generalizing and strengthening results for CUR decompositions of matrices. Based on joint with Zhao Song (UT Austin) and Peilin Zhong (Columbia). G449 (Patil/Kiva)

October 03

September 26

Learning discrete Markov random fields with nearly optimal runtime and sample complexity

Adam Klivans

Part Of

4:00P
- 5:00P

Location

32-G449
Add to Calendar 2017-09-26 16:00:00 2017-09-26 17:00:00 America/New_York Learning discrete Markov random fields with nearly optimal runtime and sample complexity Abstract: We give an algorithm for learning the structure of an undirected graphical model over a binary alphabet that has nearly optimal runtime and sample complexity. We make no assumptions on the structure of the graph. For Ising models, this subsumes and improves on all prior work. For higher-order MRFs, these are the first results of their kind.Our approach is new and uses a multiplicative-weight update algorithm. Our algorithm-- Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).Joint work with Raghu Meka 32-G449

September 19

Identity-Based Encryption from the Diffie-Hellman Assumption

Sanjam Garg

Part Of

4:00P
- 5:00P

Location

32-G449
Add to Calendar 2017-09-19 16:00:00 2017-09-19 17:00:00 America/New_York Identity-Based Encryption from the Diffie-Hellman Assumption Abstract: In this talk, I will describe a new construction of identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without using groups with pairings). This construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. The presented construction bypasses known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.(Based on joint work with Nico Döttling) 32-G449

September 06

Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity

Russell Impagliazzo
UC San Diego

Part Of

4:00P
- 5:00P

Location

32-G449
Add to Calendar 2017-09-06 16:00:00 2017-09-06 17:00:00 America/New_York Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity Abstract: A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object interacts with a class of tests, and to approximately determine the outcome of these tests.For example, a scientist is trying to find a mathematical model explaining observed data about some phenomenon, such as kinds of butterflies in a forest. A minimal criterion for success is that the model should accurately predict the results of future observations. When is this possible? This general situation arises in many contexts in computer science and mathematics. In machine learning, the object might be a distribution on data points, high dimensional real vectors, and the tests might be half-spaces. The goal would be to learn a simple representation of the data that determines the probability of any half-space or possibly intersections of half spaces. In computational complexity, the object might be a Boolean function or distribution on strings, and the tests are functions of low circuit complexity. In graph theory, the object is a large graph, and the tests are the cuts In the graph; the representation should determine approximately the size of any cut. In additive combinatorics, the object might be a function or distribution over an Abelian group, and the tests might be correlations with linear functions or polynomials.This talk is to illustrate the connections between these various contexts. In particular, we'll show direct reductions between:\begin{description}\item[Boosting:] From machine learning, a boosting algorithm converts a weak learner, that finds a hypothesis that has a small correlation to an unknown , to a strong learner, that finds a hypothesis agreeing with the function almost everywhere.\item[Hard-core distributions:] From complexity theory, a hard-core distribution lemma says that any Boolean function which cannot be computed with success more than $1-\delta$ on random inputs, has a sub-distribution of size $2 \delta$ where the function is pseudo-random\item[Dense model theorems:] Initially from additive combinatorics. Dense model theorems say that any distribution either has a simple witness that it is small (has low min-entropy) or has a simple indistinguishable distribution that is large (high min-entropy). \item[GAN-type algorithms:] From machine learning, generative adversarial networks (GANs) are algorithms that use a distinguisher that finds differences between a target distribution and a sampling algorithm in order to refine the sampling algorithm. Algorithmic versions of dense model theorems can be viewed as analogous to GAN's in many ways, but can have stronger provable guarantees.\item[Regularity lemmas:] Initially from graph theory, a regularity lemma shows that an arbitrary mathematical object has a simply described approximation. \end{description}Many of these connections were pointed out by Trevisan Tulsiani and Vadhan, and by Reingold, Trevisan, Tulsiani and Vadhan. However, our reductions are more black-box, giving us greater versatility.While many of our connections are used to prove known results in new ways, we also obtain some novel improvements and generalizations, both by exploiting the generality of these reductions and the wide assortment of boosting algorithms, and by applying these results recursively.Related work:Klivans and Servedio, Boosting and Hard-core Sets, FOCS 99.Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Dense Subsets of Pseudorandom Sets. FOCS 2008: 76-85Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. IEEE Conference on Computational Complexity 2009: 126-136Russell Impagliazzo, Algorithmic Dense Model Theorems and Weak RegularitySita Gakkhar Russell Impagliazzo Valentine Kabanets. Hardcore Measures, Dense Models and Low Complexity ApproximationsRobert E. Schapire: The Strength of Weak Learnability (Extended Abstract). FOCS 1989: 28-33 : 01 June 2005 A desicion-theoretic generalization of on-line learning and an application to boosting Yoav Freund, Robert E. SchapireYoav Freund, Robert E. Schapire: Game Theory, On-Line Prediction and Boosting. COLT 1996: 325-332Russell Impagliazzo: Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545Thomas Holenstein: Key agreement from weak bit agreement. STOC 2005: 664-673Boaz Barak, Ronen Shaltiel, Avi Wigderson: Computational Analogues of Entropy. RANDOM-APPROX 2003: 200-215Alan M. Frieze, Ravi Kannan: The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS 1996: 12-20Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions. SIAM J. Comput. 39(6): 2336-2362(2010)Noga Alon, Assaf Naor: Approximating the Cut-Norm via Grothendieck’s Inequality. SIAM J. Comput. 35(4): 787-803 (2006)Green, Ben; Tao, Terence (2008). “The primes contain arbitrarily long arithmetic progressions”. Annals of Mathematics. 167 (2): 481–547.Tao, Terence; Ziegler, Tamar (2008). “The primes contain arbitrarily long polynomial progressions”. Acta Mathematica. 201 (2): 213–305 32-G449

May 03

May 02

Yuval Peres: Trace reconstruction for the deletion channel

Yuval Peres, Microsoft Research, Redmond

Part Of

4:00P
- 5:00P

Location

Kiva G449
Add to Calendar 2017-05-02 16:00:00 2017-05-02 17:00:00 America/New_York Yuval Peres: Trace reconstruction for the deletion channel Abstract: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?The best lower bound known is linear in $n$. Until 2016, the best upper bound (due to Holenstein, Mitzenmacher, Panigrahy and Wieder 2008) was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis; this bound is sharp for reconstruction algorithms that only use this statistical information. (Joint work with Fedor Nazarov, STOC 2017; similar results were obtained independently and concurrently by De, O’Donnell and Servedio). In very recent work with Alex Zhai, we showed that If the string $x$ is random and $q<1/2$, then a subpolynomial number of traces suffices. Kiva G449

April 25

Cynthia Dwork: What's Fair?

Cynthia Dwork, Harvard University

Part Of

4:00P
- 5:00P

Location

Kiva G449
Add to Calendar 2017-04-25 16:00:00 2017-04-25 17:00:00 America/New_York Cynthia Dwork: What's Fair? Abstract: Data, algorithms, and systems have biases embedded within them reflecting designers’ explicit and implicit choices, historical biases, and societal priorities. They form, literally and inexorably, a codification of values. “Unfairness” of algorithms – for tasks ranging from advertising to recidivism prediction – has attracted considerable attention in the popular press. The talk will discuss the nascent mathematically rigorous study of fairness in classification and scoring.BIO: Cynthia Dwork is the Gordon McKay Professor of Computer Science at the Paulson School of Engineering and Applied Sciences, the Radcliffe Alumnae Professor at the Radcliffe Institute for Advanced Study, and an Affiliated Faculty Member at Harvard Law School. She has done seminal work in distributed computing, cryptography, and privacy-preserving data analysis. Her most recent foci include stability in adaptive data analysis (especially via differential privacy) and fairness in classification. Kiva G449

April 19

Andrea Montanari: The landscape of some statistical problems

Andrea Montanari, Stanford University

Part Of

4:30P
- 5:30P

Location

refreshments in the G5 Lounge - Seminar in Room 2-190
Add to Calendar 2017-04-19 16:30:00 2017-04-19 17:30:00 America/New_York Andrea Montanari: The landscape of some statistical problems Abstract: Most high-dimensional estimation and prediction methods propose to minimize a cost function(empirical risk) that is written as a sum of losses associated to each data point (each example).Studying the landscape of the empirical risk is useful to understand the computational complexityof these statistical problems. I will discuss some generic features that can be used to prove that theglobal minimizer can be computed efficiently even if the loss in non-convex.A different mechanism arises in some rank-constrained semidefinite programming problems. In this case,optimization algorithms can only be guaranteed to produce an (approximate) local optimum, but all localoptima are close in value to the global optimum.Finally I will contrast these with problems in which the effects of non-convexity are more dramatic.[Based on joint work with Yu Bai, Song Mei, Theodor Misiakiewicz and Roberto Oliveira] refreshments in the G5 Lounge - Seminar in Room 2-190

April 11

Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding

Virginia Vassilevska Williams, MIT

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-04-11 16:00:00 2017-04-11 17:00:00 America/New_York Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding Abstract:The distance product of two matrices A and B is the matrix C defined as C[i,j]=min_k A[i,k]+B[k,j].Computing the distance product of arbitrary n x n matrices is equivalent (wrt worst case runtime) to the All Pairs Shortest Paths problem on n-node graphs, a problem whose best runtime has been notoriously stuck at n^{3-o(1)} for decades. Nevertheless, when A and B are structured, sometimes truly subcubic, O(n^{3-eps}) time, for constant eps>0, algorithms are possible.An interesting structured case that has so far resisted improvements (and whose best distance product algorithm was not known to take truly subcubic time) is that of bounded difference (BD) matrices. A matrix A is said to be an L- bounded difference (L-BD) matrix if for all i,j: |A[i,j] - A[i,j+1]| <= L and |A[i,j] - A[i+1,j]| <= L. Via an approach of Leslie Valiant, any algorithm for the distance product of O(1)-BD matrices can be used to solve two other very different problems in essentially the same time: RNA-Folding (a problem formalizing how to find the secondary structure of an RNA sequence) and Context Free Language Edit Distance (a problem in which given a context free grammar defining a language L and a string x, one needs to compute the minimum, over all words y in L, of the edit distance between x and y.).In this talk I will present the first truly subcubic time algorithm for L-BD matrices for small L, thus obtaining the first truly subcubic time algorithms for RNA-Folding and Context Free Language Edit Distance.Joint work with Karl Bringmann, Fabrizio Grandoni and Barna Saha, in FOCS 2016. Patil/Kiva G449

March 21

Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective

Moni Naor, Weizmann Institute of Science

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-03-21 16:00:00 2017-03-21 17:00:00 America/New_York Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how di?cult is it to ?nd the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to ?gure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? What if we are assured that the program is small without being given explicitly?In this talk I will explore recent work on the complexity of search problems with guaranteed solution (the class TFNP) and the tight relationship with cryptographic assumptions and techniques. Based on joint works with Pavel Hubacek, Ilan Komargodski and Eylon Yogev Patil/Kiva G449

March 14

March 07

Nikhil Bansal: A fast polynomial space algorithm for Subset Sum

Nikhil Bansal

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-03-07 16:00:00 2017-03-07 17:00:00 America/New_York Nikhil Bansal: A fast polynomial space algorithm for Subset Sum Abstract: I will describe an algorithm for the subset sum problem thatruns in 2^{0.86n} time and uses polynomial space. Previously, allalgorithms with running time less than 2^n used exponential space, andobtaining such a guarantee was open. Our algorithm is based on Floyd'sspace efficient technique for cycle finding and some additivecombinatorics of subset sums.Based on joint work with Shashwat Garg, Jesper Nederlof and Nikhil Vyas Patil/Kiva G449