Title: Polynomials and Multiplicities I Speaker: Shubhangi Saraf, Rutgers University [Part 1] [Part 2] Abstract: This will be a tutorial about applications of polynomials and multiplicities to codes and extractors. I will talk about the list-decoding of Reed-Solomon codes, analyzing Kakeya sets, and about multiplicity codes. Title: Polynomials and Multiplicities II Speaker: Swastik Kopparty, [...]
Theory Lunch: Jelani Nelson – April 26, 2013
April 26, 2013 By
Title: New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows Speaker: Jelani Nelson, IAS & Princeton [Complete Video] Abstract: Many off-the-shelf algorithms for compressed sensing, like linear programming, rely on the compressed sensing matrix satisfying a sufficient condition called the “Restricted Isometry Property” (RIP). These algorithms also run faster if the compressed sensing [...]
Theory Lunch: Roy Schwartz – April 19, 2013
April 23, 2013 By
Title: Submodular Maximization Speaker: Roy Schwartz, Microsoft Research [Complete Video] Abstract: The study of combinatorial problems with a submodular objective has attracted much attention in recent years, and is partly motivated by the fact that such problems arise in diverse settings such as combinatorial optimization, algorithmic game theory, economics, machine learning and social networks. We [...]
Theory Lunch: Ankur Moitra – April 5, 2013
April 5, 2013 By
Title: A Polynomial Time Algorithm for Lossy Population Recovery Speaker: Ankur Moitra, IAS/CCI [Complete Video] Abstract: We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate [...]
Theory Lunch: Amit Chakrabarti – March 15, 2013
March 16, 2013 By
Title: Certifying Equality with Limited Interaction Speaker: Amit Chakrabarti, Dartmouth College [Complete Video] Abstract: The EQUALITY problem — where Alice and Bob must decide if their respective inputs are equal — is usually one’s first encounter with communication complexity. Its deterministic and randomized complexity were settled decades ago, but we find several new things to [...]
Center Meeting: Grothendieck Inequalities – March 8, 2013
March 8, 2013 By
Title: Algorithmic Applications of the Noncommutative Grothendieck Inequality Speaker: Assaf Naor, Courant Institute, New York University [Part 1] [Part 2] Abstract: In 1953 Grothendieck proved an inequality of immense importance to several areas of mathematics, as well as having interesting applications to combinatorial optimization. In the same paper Grothendieck also conjectured the validity of a [...]
Theory Lunch: Kunal Talwar – March 01, 2013
March 1, 2013 By
Title: The Geometry of Approximate Differential Privacy Speaker: Kunal Talwar, Microsoft Research, Silicon Valley Video: [Part 1] [Part 2] Abstract: In this talk, I will discuss trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries, and has [...]
Theory Lunch: Tim Roughgarden — February 22, 2013
February 21, 2013 By
Title: Simple and Prior-Independent Auctions Speaker: Tim Roughgarden, Stanford University [Complete Video] Abstract: Auctions tailored to a specific prior distribution over inputs are often complex and depend on the details of the distribution. On the other hand, strong impossibility results hold under the worst-case input assumptions. We survey the compelling positive results that have been [...]
Theory Lunch: Uri Zwick – February 15, 2013
February 15, 2013 By
Title: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm Speaker: Uri Zwick, Tel Aviv University [Complete Video] Abstract: The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to require an exponential number of steps to solve some linear [...]
Center Meeting: Edge Disjoint Paths – February 8, 2013
February 9, 2013 By
Title: Edge Disjoint Paths in Networks Speaker: Sanjeev Khanna, University of Pennsylvania [Complete Video] (audio starts at 00:01:45) Abstract: A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a collection of source-destination pairs in a network, and the goal is to maximize the number of pairs that can be [...]