Theory Seminar (Archive)

This is the theory seminar archive. For the current theory seminar calendar click here.

Winter 2022

Jessica Sorrell (UCSD)
Monday, January 10, 2022, 2:00pm
Reproducibility in Learning

Parthe Pandit (now at HDSI, UCSD)
Monday, January 24, 2022, 2:00pm
Bridging Continuous and Discrete Optimization: A story of Independent Sets and the Tragedy of the Commons

Noah Fleming (UCSD CSE)
Monday, January 31, 2022, 2:00pm
Semi-algebraic proofs and algorithms

Hantao Yu, UCSD Mathematics
Monday, February 14, 2022, 2:00pm
Active learning of polynomial threshold functions



Fall 2021

Ray Li (Stanford)
Monday, October 4, 2021, 2:00pm
Approximating graph diameter: algorithms, hardness, and hardness of hardness

Gill Williamson (UCSD)
Monday, October 11, 2021, 2:00pm
Sets of Instances to Subset Sum Target Zero that are Solvable in Polynomial Time but Very Hard to Find

Daniel Beaglehole (UCSD)
Monday, October 18, 2021, 2:00pm
Learning to Hash Robustly, with Guarantees

Preetum Nakkiran (UCSD)
Monday, October 25, 2021, 2:00pm
Theory for Deep Learning, and Deep Learning for Theory

Psi Vesely (UCSD)
Monday, November 1, 2021, 2:00pm
Proofs for Inner Pairing Products and Applications

Gabrielle De Micheli (UCSD)
Monday, November 8, 2021, 2:00pm
Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation

Saeed Seddghin (TTIC)
Monday, November 15, 2021, 2:00pm
Playing the Election Game: Solving Blotto and Beyond

Robi Bhattacharjee (UCSD)
Monday, November 22, 2021, 2:00pm
Online k-means Clustering on Arbitrary Data Streams

Jonathan Tidor (MIT)
Monday, November 29, 2021, 2:00pm
Testing linear-invariant properties

Spring 2021

All talks are on Monday 2-3pm to be held on Zoom Meeting. The zoom link is The password is the name of this seminar (6 lowercase letters).

Guy Moshkovitz (CUNY)
Monday, March 29, 2021, 2:00pm
An Optimal Inverse Theorem

Or Zamir (IAS)
Monday, April 5, 2021, 2:00pm
Breaking the 2^n barrier for 5-coloring and 6-coloring

Dor Minzer (MIT)
Monday, April 12, 2021, 2:00pm
Optimal tiling of the Euclidean space using permutation-symmetric bodies

Gaurav Mahajan (UCSD)
Monday, April 19, 2021, 2:00pm
Towards a Theory of Generalization in Reinforcement Learning

Rahul Ilango (MIT)
Monday, April 26, 2021, 2:00pm
Computing Constant-round Communication Complexity is Hard

Russell Impagliazzo (UCSD)
Monday, May 3, 2021, 2:00pm
Boosting Simple Learners Simply

Arya Mazumdar (UCSD)
Monday, May 10, 2021, 2:00pm
Learning Mixtures and Trace Reconstruction

Ali Vakilian (MIT)
Monday, May 17, 2021, 2:00pm
Approximation Algorithms for Fair Clustering

Winter 2021

Jeroen Zuiddam (NYU)
Monday, January 4, 2020, 2:00pm
Tensor Tools for Problems in Combinatorics and Complexity

Robi Bhattacharjee (UCSD)
Monday, January 11, 2020, 2:00pm
No-substitution Online k-means Clustering with Adversarial Order

Monday, January 18, 2020, 2:00pm
No seminar (Martin Luther King day)

Eshan Chattopadhyay (Cornell)
Monday, January 25, 2020, 2:00pm
Explicit Designs and Extractors

Fotis Iliopoulos (Princeton)
Monday, February 1, 2020, 2:00pm
Efficiently list-edge coloring multigraphs asymptotically optimally

Omri Weinstein (Columbia)
Monday, February 8, 2020, 2:00pm
Arithmetic Data Structure Lower Bounds and Binary Compressed Sensing

Monday, February 15, 2020, 2:00pm
No seminar (Presidents' day)

Shubhangi Saraf (Rutgers)
Monday, February 22, 2020, 2:00pm
Reconstruction algorithms for low-rank tensors

Sam McGuire (UCSD)
Monday, March 1, 2020, 2:00pm
Lower bounds for the dense model theorem and computational entropy

Gillat Kol (Princeton)
Monday, March 8, 2020, 2:00pm
Interactive Error Correcting Codes and the Magical Power of Adaptivity

Fall 2020

Jonathan Moshieff (CMU)
Monday, October 12, 2020, 2:00pm
Thresholds for local properties of random and LDPC codes

Rahul Ilango (MIT)
Monday, October 19, 2020, 2:00pm
Towards Hardness for the Minimum Circuit Size Problem

Cyrus Rashtchian (UCSD)
Monday, October 26, 2020, 2:00pm
Matrix Queries for Solving Linear Algebra, Statistics, and Graph Problems


Mark Bun (Boston University)
Monday, November 2, 2020, 2:00pm
An Equivalence between Private Classification and Online Prediction

Andrea Lincoln (UC, Berkeley)
Monday, November 9, 2020, 2:00pm
New Techniques for Proving Fine-Grained Average-Case Hardness

Rachel Lin (UW)
Monday, November 23, 2020, 2:00pm
Indistinguishability Obfuscation from Well-Founded Assumptions

Sam McGuire (UCSD)
Monday, November 30, 2020, 2:00pm
Log-rank and lifting for AND functions

Spring 2020

All talks are on Monday 2-3pm to be held on Zoom Meeting (meeting link: , use password "theory"), unless noted otherwise.

Ivan Mikhailin (UCSD)
Monday, March 30, 2020, 2:00pm
A new approach to KRW conjecture

Sam Buss (UCSD)
Monday, April 6, 2020, 2:00pm
CDCL Sat Solvers, and DRAT proofs with and without new extension variables

Rayan Saab (UCSD)
Monday, April 13, 2020, 2:00pm
Binary data embeddings: Theory and Applications

Eric Price (UT Austin)
Monday, April 20, 2020, 2:00pm
Separations and equivalences between turnstile streaming and linear sketching

Jelani Nelson (UC Berkeley)
Monday, April 27, 2020, 2:00pm
Optimal terminal dimensionality reduction in Euclidean space

Christos Tzamos (UW Madison)
Monday, May 4, 2020, 2:00pm
PAC Learning of Halfspaces with Noise: Efficient algorithms for the Massart and Tsybakov models

Manuel Sabin
Monday, May 11, 2020, 2:00pm
How Do We Define "Fair" Responsibly?

Prashant Vasudevan
Monday, May 18, 2020, 2:00pm
Cryptography from Information Loss

No Talk (Memorial Day)
Monday, May 25, 2020, 2:00pm

Jessica Sorrell (UCSD)
Monday, June 1, 2020, 2:00pm
Simpler Statistically Sender Private Oblivious Transfer from Ideals of Cyclotomic Integers

Winter 2020

David Zuckerman (UT Austin)
Monday, January 13, 2020, 2:00pm
Nearly Optimal Pseudorandomness From Hardness

Monday, January 20, 2020, 2:00pm
No seminar (Martin Luther King day)

Ragesh Jaiswal (IIT Delhi)
Wednesday, January 22, 2020, 4:00pm
D^2-Sampling and k-Means Clustering

Greta Panova (USC)
Monday, January 27, 2020, 2:00pm
Geometric Complexity Theory from an Algebro-Combinatorial perspective

Nengkun Yu (University of Technology Sydney)
Monday, February 3, 2020, 2:00pm
Quantum Property Testing: Tomography and Identity Testing

David Conlon (Caltech)
Monday, February 10, 2020, 2:00pm
The random algebraic method

Monday, February 17, 2020, 2:00pm
No seminar (Presidents day)

Peter Nelson (Waterloo)
Wednesday, February 19, 2020, 2:00pm
Binary submatroids

Sourya Roy (UC Riverside)
Monday, February 24, 2020, 2:00pm
Locally Testable Non-Malleable Codes

Jiapeng Zhang (Harvard)
Monday, March 2, 2020, 2:00pm
Improved query-to-communication theorems via robust sunflowers

Fall 2019

Monday, Septmber 30, 2019, 2:00pm
Social intro meeting

Shachar Lovett (UC San Diego)
Monday, October 7, 2019, 2:00pm
Towards the sunflower conjecture

Grigory Yaroslavtsev (Indiana University, Bloomington)
Monday, October 14, 2019, 2:00pm
Advances in Hierarchical Clustering of Vector Data

Russell Impagliazzo (UC San Diego)
Monday, October 21, 2019, 2:00pm
A Unified Approach to Smooth Boosting

Cyrus Rashtchian (UC San Diego)
Monday, October 28, 2019, 2:00pm
Reconstructing Trees from Traces

Monday, November 4, 2019, 2:00pm
No seminar

Monday, November 11, 2019, 2:00pm
No Seminar (Veterans day)

Max Hopkins (UC San Diego)
Monday, November 18, 2019, 2:00pm
High Dimensional Expansion and the Johnson Graph: a Unified Approach to Small-set Expansion

Jessica Sorrell (UC San Diego)
Monday, November 25, 2019, 2:00pm
Efficient, Noise-Tolerant, and Private Learning via Boosting

Michal Moshkovitz (UC San Diego)
Monday, December 2, 2019, 2:00pm
Unexpected Effects of Online K-means Clustering

Winter 2019

Monday, January 7, 2019, 2:00pm
No seminar (SODA)

Nima Anari (Stanford)
Monday, January 14, 2019, 2:00pm
Log-Concave Polynomials and Matroids

Monday, January 21, 2019, 2:00pm
No seminar (MLK day)

Alon Gonen (Princeton)
Monday, January 28, 2019, 2:00pm
Learning in Non-convex Games with an Optimization Oracle

Ilias Diakonikolas (USC)
Monday, February 4, 2019, 2:00pm
The Degree-d Chow Parameters Problem

Andrew Suk (UCSD)
Monday, February 11, 2019, 2:00pm
Multicolor Ramsey numbers for semi-algebraic graphs

Monday, February 18, 2019, 2:00pm
No seminar (presidents day)

Yuval Ishai (Technion)
Monday, February 25, 2019, 2:00pm
Homomorphic Secret Sharing 

Leonard Schulman (Caltech)
Monday, March 4, 2019, 2:00pm
Invitation to Causal Inference

Kamyar Azizzadenesheli (Caltech)
Monday, March 11, 2019, 2:00pm
Interactive Learning in Structured and Partially Observable Domains

Fall 2017

Eshan Chattopadhyay (Institute for Advanced Study)
Monday, October 2, 2017, 2:00pm
Towards Optimal Randomness Extractors and Ramsey Graphs

Shai Vardi (Caltech)
Monday, October 9, 2017, 2:00pm
Randomly coloring graphs of bounded treewidth

Monday, October 16, 2017, 2:00pm
No seminar (FOCS)

Swastik Kopparty (Rutgers)
Monday, October 23, 2017, 2:00pm
Recent results on locally testable codes and locally decodable codes

Clément Canonne (Columbia)
Monday, October 30, 2017, 2:00pm
When Fourier SIIRVs: Fourier-Based Testing for Families of Distributions

Nikhil Bansal (TU Eindhoven) 
Monday, November 6, 2017, 2:00pm
A fast polynomial space algorithm for Subset Sum

Thomas Rothvoss (University of Washington)
Monday, November 13, 2017, 2:00pm
The matching polytope has exponential extension complexity

Avishay Tal (Stanford)
Monday, November 20, 2017, 2:00pm
Computing Requires Larger Formulas than Approximating

Tselil Schramm (Berkeley)
Monday, November 27, 2017, 2:00pm
Spectral Algorithms Capture Sum-of-Squares on Average

Yin Tat Lee (University of Washington)
Monday, December 4, 2017, 2:00pm
KLS conjecture and log-Sobolev constant

Spring 2017

Daniele Micciancio (UCSD)
"A quick introduction to Lattice Cryptography"
Monday, April 3, 2017, 2:00pm

Alexander Golevnev (NYU)
"The Minrank of Random Graphs"
Monday, April 10, 2017, 2:00pm

Sanjam Garg (UC Berkeley)
"Identity-Based Encryption from the Diffie-Hellman Assumption"
Monday, April 17, 2017, 2:00pm

Russell Impagliazzo (UCSD)
"Algorithmic Dense Model Theorems, Generative Adversarial Networks and Regularity"
Monday, April 24, 2017, 2:00pm

Mihir Bellare (UCSD)
"Cryptography in the Age of Mass Surveillance"
Monday, May 1, 2017, 2:00pm

Stefan Schneider (UCSD)
"On the Fine-grained Complexity of One-Dimensional Dynamic Programming"
Monday, May 8, 2017, 2:00pm

Shachar Lovett (UCSD)
"The decision tree complexity of k-SUM is near-linear"
Monday, May 15, 2017, 2:00pm

Alain Passelègue (ENS/UCLA)
"Private Circuits for Multiplication"
Monday, May 22, 2017, 2:00pm

Chris Umans (CalTech)
"On cap sets and the group-theoretic approach to matrix multiplication"
Monday, June 5, 2017, 2:00pm

Winter 2017

Omer Tamuz (Caltech)
Monday, January 9, 2017, 2:00pm
Quasi-regular sequences and optimal schedules for security games

Ran Gelles (Bar Ilan University)
Wednesday, January 18, 2017, 1:00pm (NOTE THE UNUSUAL DAY AND TIME)
Optimal Resilience for Short-Circuit Noise in Formulas

Paul Beame (University of Washington)
Monday, January 30, 2017, 2:00pm
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube

Nikhil Srivastava (Berkeley)
Monday, February 6, 2017, 2:00pm
Ramanujan Graphs from Finite Free Convolutions

Mohit Singh (Georgia Institute of Technology)
Monday, February 13, 2017, 2:00pm
Constrained Subset Selection Problems, Permanents and Inequalities on Stable Polynomials

Ilias Diakonikolas (University of Southern California)
Monday, February 27, 2017, 2:00pm
Computational Efficiency and Robust Statistics

Sivaramakrishnan Ramamoorthy (University of Washington)
Monday, March 6, 2017, 2:00pm
Lower bounds on non-adaptive data structures for median and predecessor search

Konstantin Makarychev (Northwestern University)
Monday, March 13, 2017, 2:00pm
Solving optimization problems with a diseconomy of scale

Spring 2016

Benjamin Perez (UCSD)
"Algebraic Number Theory for Crytographers"
Monday, April 4, 2016, 2:00pm

Marco Carmosino (UCSD)
"Learning Algorithms from Natural Proofs"
Monday, April 11, 2016, 2:00pm

Jiawei Gao (UCSD)
"Orthogonal Vectors is hard for first-order properties on sparse graphs"
Monday, April 18, 2016, 2:00pm

Valentin Kabanets (Simon Fraser University)
"Pseudorandomness when the odds are against you: Derandomizing the PPSZ algorithm for k-SAT"
Monday, April 25, 2016, 2:00pm

Kaave Hosseini (UCSD)
"The structure of protocols for XOR functions"
Monday, May 2, 2016, 2:00pm

Stefan Schneider (UCSD)
"Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility"
Monday, May 9, 2016, 2:00pm

Antonita Kolokolova (Memorial University of Newfoundland)
"The power of expander-based reasoning"
Monday, May 16, 2016, 2:00pm

Winter 2016

Leonard Schulman (Caltech)
"Analysis of a Classical Matrix Preconditioning Algorithm"
Monday, January 11, 2016, 2:00pm

Ananda Theertha Suresh (UCSD)
"Estimating the number of unseen species: How far can one foresee?"
Monday, January 25, 2016, 2:00pm

Thomas Vidick (Caltech)
"Anchoring games for parallel repetition"
Monday, Feb 8, 2016, 2:00pm

Adam Sheffer (Caltech)
"Few distinct distances implies no heavy lines"
Monday, Feb 22, 2016, 2:00pm

Ilias Diakonikolas (USC)
"Density estimation via piecewise polynomial approximation in sample near-linear time"
Monday, Feb 29, 2016, 2:00pm

Fall 2015

Shachar Lovett (UCSD)
"Nonclassical polynomials as a barrier to polynomial lower bounds"
Tuesday, September 29, 2015, 2:00pm

Kobbi Nissim  (Ben-Gurion University and CRCS@Harvard)
"Learning threshold functions under Differential Privacy"
Tuesday, October 13, 2015, 1:00pm

Sanjoy Dasgupta  (UCSD)
"An approximation algorithm for hierarchical clustering"
Tuesday, October 27, 2015, 1:00pm

Michael Walter  (UCSD)
"Analysis of Lattice Reduction Algorithms"
Tuesday, November 3, 2015, 1:00pm

Shachar Lovett  (UCSD)
"Algebraic Attacks against Random Local Functions and Their Countermeasures"
Tuesday, November 10, 2015, 1:00pm

Mihir Bellare  (UCSD)
"Closed Doors and Open Windows: Cryptography in the Age of Mass Surveillance"
Tuesday, November 17, 2015, 1:00pm

James Aisenberg  (UCSD)
"2-D Tucker is PPA complete"
Tuesday, November 24, 2015, 1:00pm

Jiapeng Zhang  (UCSD)
"Barriers to Black-Box Constructions of Traitor Tracing Systems"
Tuesday, November 31, 2015, 1:00pm

Spring 2015

Ilya Mironov (Stanford)
"Cryptographic Reverse Firewalls"
Monday, April 6, 2015, 2:00pm

Noam Solomon (Tel Aviv University) - NOTE THE SPECIAL TIME
"Incidences between points and lines and extremal configuration of lines in Euclidean spaces"
Thursday, April 9, 2015, 2:00pm

Alexander Kulikov (St. Petersburg Department of Steklov Institute of Mathematics)
"Linear circuit size upper and lower bounds"
Monday, April 13, 2015, 2:00pm

David Kempe (University of South California)
"Incentivizing Exploration"
Monday, April 20, 2015, 2:00pm

Paul Kirchner (ENS Paris)
"Subexponential algorithm for the subset-sum problem"
Monday, April 27, 2015, 2:00pm

Shaddin Dughmi (University of South California)
"Algorithmic Bayesian Persuasion"
Monday, May 4, 2015, 2:00pm

Akshay Balsubramani (UCSD)
"Non-Asymptotic Extensions to the Law of the Iterated Logarithm"
Monday, May 11, 2015, 2:00pm

Kaave Hosseini (UCSD)
"On the structure of spectrum of small sets"
Monday, May 18, 2015, 2:00pm

Monday, May 25, 2015, 2:00pm
No seminar (memorial day)

Alexander Sherstov (UCLA) - NOTE THE SPECIAL TIME
"The Power of Asymmetry in Constant-Depth Circuits"
Thursday, May 28, 2015, 2:00pm

Thomas Vidick (Caltech)
Monday, June 1, 2015, 2:00pm

Fall 2014

Pranjal Awasthi (Princeton University)
"Learning Halfspaces with Noise"
Monday, October 6, 2014, 2:00pm


Omer Reingold
"Guilt-Free Interactive Data Analysis: The Reusable Holdout"
Monday, October 13, 2014, 11:00am (DLS talk, no regular seminar)

Monday, October 20, 2014, 2:00pm
No seminar (STOC)

Daniel Kane (UCSD)
"Pseudorandom generators for Polynomial Threshold functions"
Monday, October 27, 2014, 2:00pm

Silas Richelson (UCLA)
"An Algebraic Approach to Non-Malleability"
Monday, November 3, 2014, 2:00pm


Leo Ducas (UCSD)
"Advances on Fully Homomorphic Encryption"
Monday, November 10, 2014, 2:00pm


Igors Stepanovs (UCSD)
"Poly-Many Hardcore Bits for Any One-Way Function"
Monday, November 17, 2014, 2:00pm


Kaave Hosseini (UCSD)
"Improved lower bounds for Arithmetic Regularity Lemma"
Monday, November 24, 2014, 2:00pm


Marco Carmosini (UCSD)
"Tighter Connections between Derandomization and Circuit Lower Bounds"
Monday, December 1, 2014, 2:00pm


Micahel Forbes (Simons Institute)
"Dimension Expanders via Rank Condensers"
Monday, December 8, 2014, 2:00pm

Spring 2014

Leo Ducas (UCSD)
"The Versatility of Discrete Gaussians over Lattices"
Monday, April 7, 2014, 2:00pm

Mario Szegedy (Rutgers)
"Impossibility Theorems and the Universal Algebraic Toolkit"
Monday, April 14, 20142:00pm

Victor Vianu (UCSD)
"Query determinacy and rewriting"
Monday, April 21, 2014, 2:00pm

Vineet Bafna (UCSD)
"Algorithms Strategies for genomics and genetics"
Monday, April 28, 2014, 2:00pm

Michael Walter (UCSD)
"Fast Lattice Point Enumeration with Minimal Overhead"
Monday, May 5, 2014, 2:00pm

Jacques Verstraete (UCSD)
"Extremal Problems for Linear Dependencies"
Monday, May 12, 2014, 2:00pm

Sourav Chakraborty (Chennai Mathematical Institute)
"Testing of Boolean Function Isomorphism"
Monday, May 19, 2014, 2:00pm

Monday, May 26, 2014, 2:00pm (no seminar, memorial day)

Monday, June 2, 2014, 2:00pm (no seminar, STOC)

Winter 2014

January 8th-10th, 2014 (no seminar; Complexity and Coding Theory workshop)

Valeria Nikolaenko (Stanford)
"Fully Key Homomorphic Encryption and Applications: Compressed Garbled Circuits and Arithmetic ABE with Short Keys"
Monday, January 13th, 2014, 2:00pm

Monday, January 20th, 2014: No Seminar (MLK holiday)

Sasha Rubin (TU Wien & IST Austria)
"Memoryless Determinacy of Cycle Games"
Wednesday, January 22nd, 2014, 2:00pm

Timon Hertli (ETH Zurich)
"Breaking the PPSZ Barrier for Unique 3-SAT"
Monday, January 27th, 2014, 2:00pm

Russell Impagliazzo (UCSD)
"Fourier Concentration from Shrinkage"
Monday, February 3rd, 2014, 2:00pm

Alexandr Andoni (Microsoft Research)
"Parallel Algorithms for Geometric Graph Problems"
Monday, February 10th, 2014, 2:00pm

Monday, February 17th, 2014: No Seminar (President's day)

Moritz Hardt (IBM Research)
"On the Provable Convergence of Alternating Minimization for Matrix Completion"
Tueday, February 18th, 2014, 2:00pm

Klim Efremenko (U. Chicago)
"List and Unique Coding of Interactive Communication"
Monday, February 24th, 2014, 2:00pm

Shang-Hua Teng (USC)
"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"
Monday, March 3rd, 2014, 2:00pm

Fall 2013

Leo Ducas (UCSD)
"The Chaitin's Constant"
Monday, September 30th, 2013, 2:00pm

Mohan Paturi (UCSD)
"Exact Complexity and Satisfiability"
Monday, October 7th, 2013, 2:00pm

Shachar Lovett (UCSD)
"Communication is Bounded by Root of Rank"
Monday, October 14th, 2013, 2:00pm

Bjorn Tackmann (ETH Zurich)
"Constructive Cryptography - Introduction and Applications"
Monday, October 21th, 2013, 2:00pm

Monday, October 28th, 2013 No seminar (FOCS)

Daniel Moeller (UCSD)
"Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching"
Monday, November 4th, 2013, 2:00pm

Marco Carmosino (UCSD)
"Counting Solutions to Problems in NL, and the Computational Complexity of Linear Algebra"
Monday, November 18th, 2013, 2:00pm

Daniele Micciancio (UCSD)
"Locally Dense Codes"
Monday, November 25th, 2013, 2:00pm

Mohammad Hajiabadi (U. Victoria)
"How encryption with standard security copes under stronger forms of attack, with applications to computational soundness"
Monday, December 2, 2013, 2:00pm

Summer 2013

Jordi Levy (IIIA)
"The Nature of Industrial SAT Instances"
Monday, July 29, 2013, 2:00pm

Chris Beck (Princeton)
"Strong ETH holds for regular resolution"
Thursday, August 1, 2013, 11:00am

Russell Impagliazzo (UCSD)
"Finding Heavy Hitters from Lossy or Noisy Data"
Monday, August 5, 2013, 2:00pm

Valentine Kabanets (Simon Fraser University)
"Mining Circuit Lower Bound Proofs for Meta-Algorithms"
Monday, August 12, 2013, 2:00pm

Spring 2013

Ankur Moitra (IAS and Princeton)
"New Algorithms for Nonnegative Matrix Factorization and Beyond"
Monday, April 1, 2013, 11:00pm

Ankur Moitra (IAS and Princeton)
"Disentangling Gaussians"
Monday, April 1, 2013, 2:00pm

Daniele Micciancio (UCSD)
"An equational approach to secure multiparty computation"
Monday, April 8, 2013, 2:00pm

Shweta Agrawal (UCLA)
"Discrete Gaussian Leftover Hash Lemma over Infinite Domains"
Monday, April 15, 2013, 2:00pm

Shachar Lovett (UCSD)
"Non-Malleable Codes from Additive Combinatorics"
Monday, April 22, 2013, 2:00pm

Yi-Kai Liu (NIST)
"Building one-time memories from isolated qubits"
Thursday, April 25, 2013, 2:00pm

Chris Peikert (Georgia Tech)
"Practical Bootstrapping with Polylogarithmic Overhead"
Monday, April 29, 2013, 2:00pm

Daniel Dadush (NYU)
"On the Lattice Smoothing Parameter Problem"
Monday, May 6, 2013, 2:00pm

Benny Sudakov (UCLA)
"The phase transition in random graphs - a simple proof"
Wednesday, May 15, 2013, 11:00pm

Mihir Bellare (UCSD)
"Semantic Security for the Wiretap Channel"
Monday, May 20, 2013, 2:00pm

Russell Impagliazzo (UCSD)
"Simultaneons security and reliability amplification for unknown channels"
Wednesday, May 29, 2013, 12:00pm

Spring 2012

Paul Valiant (UC, Berkeley)
''Central Limit Theorems and Tight Lower Bounds for Entropy Estimation''
Monday, April 2, 2012, 2:00 pm 

Shachar Lovett (Institute for Advanced Studies)
''Subspace-evasive sets''
Monday, April 9, 2012, 2:00 pm

Shayan Oveis Gharan (Stanford)
''Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities''
Monday, April 16, 2012, 2:00 pm

Madhur Tulsiani (Toyota Technological Institute)
''Towards An Optimal Query Efficient PCP?''
Monday, April 23, 2012, 2:00 pm

Zvika Brakerski (Stanford University)
''Fully Homomorphic Encryption from LWE''
Monday, April 30, 2012, 2:00 pm

Eva Tardos (Cornell University)
''Near-Optimal Greedy Mechanisms''
Monday, May 7, 2012, 11:00 am

Andrew Drucker (MIT)
''New Limits to Instance Compression for Hard Problems''
Monday, May 14, 2012, 2:00 pm

Alexandra Kolla (UIUC)
''Maximal Inequality for Spherical Means on the Hypercube''
Monday, June 4, 2012, 2:00 pm

Russell Impagliazzo (UCSD)
''Pseudorandomness from Shrinkage''
Monday, June 11, 2012, 2:00 pm

Winter 2012

Sandy Irani (UC, Irvine)
''Generating Quantum Gibbs States''
Monday, March 12, 2012, 2:00 pm

Virginia Williams (UC, Berkeley)
''Multiplying matrices faster''
Wednesday, March 21, 2012,11:00 am

Fall 2011

Title: Computational Complexity in Differential Privacy
Speaker: Salil Vadhan, Harvard (on sabbatical at Microsoft Research SVC and Stanford)
Date and Place: Tuesday, October 11, 2011, 2:00pm-3:00pm, CSE 1202

Title: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
Speaker: Petros Mol, UCSD
Date and Place: Monday, October 3, 2011, 2:00pm-3:20pm, CSE 4140

Spring 2011

Title: Pseudorandom generators, the BQP vs. PH problem and beating the hybrid argument
Speaker: Chris Umans, CalTech
Date and Place: Monday, May 23, 2011, 2-3:20 PM, CSE 4140

Title: Higher Order Principal Components: Complexity and Applications
Speaker: Santosh Vempala, Georgia Tech
Date and Place: Monday, May 16, 2011, 2-3:20 PM, CSE 4140

Title: How to Compute on Encrypted Data: New Developments in Fully Homomorphic Encryption
Speaker: Vinod Vaikuntanathan, MSR and U. Toronto
Date and Place: Monday, May 2, 2011, 2-3:20 PM, CSE 4140

Title: Left Over Hash Lemma, Revisited
Speaker: Yevgeniy Dodis, NYU
Date and Place: Monday, April 25, 2011, 2-3:20 PM, CSE 4140

Title: Enumerative algorithms for the Shortest and Closest Lattice Vector Problems in any norm via M-Ellipsoid coverings
Speaker: Daniel Dadush, Georgia Tech
Date and Place: Monday, April 18, 2011, 2-3:20 PM, CSE 4140

Title: The many entropies of one-way functions
Speaker: Omer Reingold, Microsoft Research
Date and Place: Monday, April 11, 2011, 2-3:20 PM, CSE 4140

Title: General questions about extremal graphs
Speaker: Laszlo Lovasz
Date and Place: Thursday, April 7, 2011, 11:00 AM-12:00 PM, NSB (Natural Sciences Building)

Title: Kyoto Prize Lecture
Speaker: Laszlo Lovasz
Date and Place: Tuesday, April 5, 2011, 3:30-5:00 PM, Price Center West Ballroom

Title: TBA
Speaker: William Matthews, UCSD
Date and Place: Monday, April 4, 2011, 2-3:20 PM, CSE 4140

Title: Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
Speaker: Daniel Lokshtanov, UCSD
Date and Place: Monday, March 28, 2011, 2-3:20 PM, CSE 4140

Winter 2011

Title: Non-uniform ACC Circuit LowerBounds
Speaker: Ryan Williams, IBM
Date and Place: Tuesday, March 8, 2011, 3-4 PM, APM (MATH) 6402 (Halkin room)

Title: Matrix Rigidity -- Quadratic Lower Bounds and Open Questions
Speaker: Satya Lokam, Microsoft Research
Date and Place: Monday, March 7, 2011, 2-3:20 PM, CSE 4140

Title: Security proofs for RSA-OAEP in the Standard Model
Speaker: Adam O'Neil, UT Austin
Date and Place: Monday, February 28, 2011, 2-3:20 PM, CSE 4140

Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences
Speaker: Virginia Vassilevska Williams
Date and Place: Wednesday, February 23, 2011, 11am-12pm, CSE 1202

Title: The Sparsification Lemma
Speaker: Mohan Paturi, UCSD
Date and Place: Monday, February 14, 2011, 2-3:20 PM, CSE 4140

Title: Efficient Learning Gaussian Mixtures
Speaker: Gregory Valiant, UC Berkeley
Date and Place: Monday, February 7, 2011, 2-3:20 PM, CSE 4140

Title: How the cryptanalysis of RSA is (not so) secretly coding theory
Speaker: Nadia Heninger, Princeton/MIT
Date and Place: Tuesday, February 1, 2011, 11am-12pm, CSE 4217

Title: Exact Complexity and Satisfiability
Speaker: Mohan Paturi, UCSD
Date and Place: Monday, January 31, 2011, 2-3:20 PM, CSE 4140

Title: The Permanents of Gaussian Matrices
Speaker: Scott Aaronson, MIT
Date and Place: Monday, January 24, 2011, 2-3:20 PM, CSE 4140

Title: The Computational Complexity of Linear Optics
Speaker: Scott Aaronson, MIT
Date and Place: Monday, January 24, 2011, 11am-12pm, CSE 1202

Title: Robust Simulations and Significant Separations
Speaker: Lance Fortnow, Northwestern
Date and Place: Monday, January 10, 2011, 2-3:20 PM, CSE 4140

Fall 2010

Title: Homomorphic Signatures for Polynomial Functions
Speaker: David Freeman, Stanford
Date and Place: Monday, November 22, 2010, 2-3:20 PM, CSE 4140

Title: Expressive encryption from hard lattice problems.
Speaker: Shweta Agarwal, UT Austin
Date and Place: Monday, November 8, 2010, 2-3:20 PM, CSE 4140
References: Lattice Basis Delegation in Fixed Dimension and Shorter Ciphertext HIBE, Agrawal, Boneh and Boyen (CRYPTO 2010)
Efficient Lattice (H)IBE in the Standard Model, Agrawal, Boneh and Boyen (Eurocrypt, 2010)

Title: The effects of diversity in aggregation games.
Speaker: Andrea Vattani, UCSD
Date and Place: Monday, November 1, 2010, 2-3:20 PM, CSE 4140
References: The effects of diversity in aggregation games , Mol, Vattani, and Voulgaris

Title: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
Speaker: Panagiotis Voulgaris, UCSD
Date and Place: Monday, October 18, 2010, 2-3:20 PM, CSE 4140
References: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations, Micciancio and Voulgaris

Title: Linkage clustering and continuum percolation
Speaker: Sanjoy Dasgupta, UCSD
Date and Place: Monday, October 11, 2010, 2-3:20 PM, CSE 4140
References: Rates of convergence for the cluster tree, Chaudhuri and Dasgupta

Title: Uniquely Represented Data Structures with Applications to Privacy
Speaker: Daniel Golovin, CalTech
Date and Place: Monday, October 4, 2010, 2-3:20 PM, CSE 4140
References: Strongly History-Independent Hashing with Applications, Blelloch and Golovin

Title: Chromatic Coding
Speaker: Daniel Lokshtanov, UCSD Simons Foundation Postdoctoral Fellow
Date and Place: Monday, September 27, 2010, 2-3:20 PM, CSE 4140
References: Fast FAST, Alon, Lokshtanov and Saurabh
Color Coding, Alon, Yuster and Zwick