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 [...]
Center Meeting: Compressed Sensing/Sparse Recovery – April 12, 2013
April 9, 2013 By
Program: 10:00-11:00 PI meeting (for PIs only) 11:00-12:00 Deanna Needell, Analysis and Synthesis Methods in Compressed Sensing 12:00- 1:00 lunch 1:00- 2:00 Andrea Montanari, Finding Cliques in Large Random Graphs, Sparse PCA and Iterative Thresholding 2:00- 2:30 break 2:30- 3:30 Piotr Indyk, Faster Algorithms for the Sparse Fourier Transform Title: Analysis and Synthesis Methods [...]
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 [...]
Workshop: Natural Algorithms and the Sciences — May 20-21, 2013
April 2, 2013 By
Organizers: Mark Braverman and Bernard Chazelle Description: The workshop brought together researchers from computer science, mathematics, physics, biology, and engineering to explore interactions among algorithms, dynamical systems, statistical physics, and complexity theory (in all senses of the term). Dates: The workshop will go from May 20 to May 21 and will be held at Nassau Inn in Princeton, [...]
Theory Lunch: Umesh Vazirani – March 28, 2013
March 28, 2013 By
Title: Quantum Hamiltonian Complexity: Through the Computational Lens Speaker: Umesh Vazirani, UC Berkeley [Complete Video] (note: audio cuts out for roughly 7 minutes at around 00:39:30) Abstract: Much as probabilistic thinking did starting in the early 80s, quantum computing is expanding the core questions of complexity theory in fundamental new directions. For example, here is [...]
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 [...]