![]() |
Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares Tuesday, December 5, 2017 - 4:00pm to 5:00pm Abstract: |
![]() |
Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds Tuesday, November 28, 2017 - 4:00pm to 5:00pm |
![]() |
Venkatesan Guruswami: Promise Constraint Satisfaction Tuesday, November 14, 2017 - 4:00pm to 5:00pm 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? |
![]() |
Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions Tuesday, November 7, 2017 - 4:00pm to 5:00pm |
![]() |
Noga Alon: Structure, randomness and universality Tuesday, October 31, 2017 - 4:00pm to 5:00pm 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 ? |
![]() |
Sanjam Garg: Identity-Based Encryption from the Diffie-Hellman Assumption Tuesday, September 19, 2017 - 4:00pm to 5:00pm In this talk, I will describe a new construction of identity-based encryption based on the hardness |
![]() |
Russell Impagliazzo: Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity Tuesday, September 12, 2017 - 4:00pm to 5:00pm Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity |
![]() |
Yuval Peres: Trace reconstruction for the deletion channel Tuesday, May 2, 2017 - 4:00pm to 5:00pm 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 reconst |
![]() |
Cynthia Dwork: What's Fair? Tuesday, April 25, 2017 - 4:00pm to 5:00pm Abstract: Data, algorithms, and systems have biases embedded within them reflecting designers’ explicit and implicit choices, historical biases, and societal priorities. |
![]() |
Andrea Montanari: The landscape of some statistical problems Wednesday, April 19, 2017 - 4:30pm to 5:30pm Abstract: Most high-dimensional estimation and prediction methods propose to minimize a cost function |