Theory Seminar (Archive)

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

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