This is the theory seminar archive. For the current theory seminar calendar click here.
Spring 2022
Arnab Bhattacharyya
Monday, March 29, 2022, 2:00pm
Algorithms for learning and testing statistical and causal relations
Details
Shuchi Chawla
Wednesday, April 6, 2022, 1:00pm
Pandora's Box with Correlations: Learning and Approximation
Details
Ivan Mihajlin
Monday, April 11th, 2022, 2:00pm
A Better-than-3logn Depth Lower Bound for De Morgan Formulas
with Restrictions on Top Gates.
Gaurav Mahajan
Monday, April 18th, 2022, 2:00pm
Statistical and Computational Issues in Reinforcement Learning (with Linear Function Approximation)
Daniel Grier
Monday, May 2, 2022, 11:00am
The Complexity of Near-Term Quantum Computers
Kaushik Shankar
Monday, May 9th, 2022, 2:00 pm
Mathematical Tools for Quantum Differential Privacy
Sebastien Bubeck
Wednesday, May 11th, 2022, 1:00 pm
Set Chasing, with an application to online shortest path
Daniel Kane
Monday, May 16th, 2022, 2:00pm
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Huy Tuan Pham
Monday, May 23rd, 2022, 2:00pm
On the Kahn-Kalai Expectation Threshold Conjecture
Robert Robere
Monday, June 6th, 2022, 2:00 pm
Separations and Intersections in Proof Complexity & TFNP
Winter 2022
Jessica Sorrell (UCSD)
Monday, January 10, 2022, 2:00pm
Reproducibility in Learning
Details
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
Details
Noah Fleming (UCSD CSE)
Monday, January 31, 2022, 2:00pm
Semi-algebraic proofs and algorithms
Details
Hantao Yu, UCSD Mathematics
Monday, February 14, 2022, 2:00pm
Active learning of polynomial threshold functions
Details
Fall 2021
Ray Li (Stanford)
Monday, October 4, 2021, 2:00pm
Approximating graph diameter: algorithms, hardness, and hardness of hardness
Details
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
Details
Daniel Beaglehole (UCSD)
Monday, October 18, 2021, 2:00pm
Learning to Hash Robustly, with Guarantees
Details
Preetum Nakkiran (UCSD)
Monday, October 25, 2021, 2:00pm
Theory for Deep Learning, and Deep Learning for Theory
Details
Psi Vesely (UCSD)
Monday, November 1, 2021, 2:00pm
Proofs for Inner Pairing Products and Applications
Details
Gabrielle De Micheli (UCSD)
Monday, November 8, 2021, 2:00pm
Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation
Details
Saeed Seddghin (TTIC)
Monday, November 15, 2021, 2:00pm
Playing the Election Game: Solving Blotto and Beyond
Details
Robi Bhattacharjee (UCSD)
Monday, November 22, 2021, 2:00pm
Online k-means Clustering on Arbitrary Data Streams
Details
Jonathan Tidor (MIT)
Monday, November 29, 2021, 2:00pm
Testing linear-invariant properties
Details
Spring 2021
All talks are on Monday 2-3pm to be held on Zoom Meeting. The zoom link is https://ucsd.zoom.us/my/csetheoryseminar. The password is the name of this seminar (6 lowercase letters).
Guy Moshkovitz (CUNY)
Monday, March 29, 2021, 2:00pm
An Optimal Inverse Theorem
Details
Or Zamir (IAS)
Monday, April 5, 2021, 2:00pm
Breaking the 2^n barrier for 5-coloring and 6-coloring
Details
Dor Minzer (MIT)
Monday, April 12, 2021, 2:00pm
Optimal tiling of the Euclidean space using permutation-symmetric bodies
Details
Gaurav Mahajan (UCSD)
Monday, April 19, 2021, 2:00pm
Towards a Theory of Generalization in Reinforcement Learning
Details
Rahul Ilango (MIT)
Monday, April 26, 2021, 2:00pm
Computing Constant-round Communication Complexity is Hard
Details
Russell Impagliazzo (UCSD)
Monday, May 3, 2021, 2:00pm
Boosting Simple Learners Simply
Details
Arya Mazumdar (UCSD)
Monday, May 10, 2021, 2:00pm
Learning Mixtures and Trace Reconstruction
Details
Ali Vakilian (MIT)
Monday, May 17, 2021, 2:00pm
Approximation Algorithms for Fair Clustering
Details
Winter 2021
Jeroen Zuiddam (NYU)
Monday, January 4, 2020, 2:00pm
Tensor Tools for Problems in Combinatorics and Complexity
Details
Robi Bhattacharjee (UCSD)
Monday, January 11, 2020, 2:00pm
No-substitution Online k-means Clustering with Adversarial Order
Details
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
Details
Fotis Iliopoulos (Princeton)
Monday, February 1, 2020, 2:00pm
Efficiently list-edge coloring multigraphs asymptotically optimally
Details
Omri Weinstein (Columbia)
Monday, February 8, 2020, 2:00pm
Arithmetic Data Structure Lower Bounds and Binary Compressed Sensing
Details
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
Details
Sam McGuire (UCSD)
Monday, March 1, 2020, 2:00pm
Lower bounds for the dense model theorem and computational entropy
Details
Gillat Kol (Princeton)
Monday, March 8, 2020, 2:00pm
Interactive Error Correcting Codes and the Magical Power of Adaptivity
Details
Fall 2020
Jonathan Moshieff (CMU)
Monday, October 12, 2020, 2:00pm
Thresholds for local properties of random and LDPC codes
Details
Rahul Ilango (MIT)
Monday, October 19, 2020, 2:00pm
Towards Hardness for the Minimum Circuit Size Problem
Details
Cyrus Rashtchian (UCSD)
Monday, October 26, 2020, 2:00pm
Matrix Queries for Solving Linear Algebra, Statistics, and Graph Problems
Details
Mark Bun (Boston University)
Monday, November 2, 2020, 2:00pm
An Equivalence between Private
Details
Andrea Lincoln (UC, Berkeley)
Monday, November 9, 2020, 2:00pm
New Techniques for Proving Fine-Grained Average-Case Hardness
Details
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: https://ucsd.zoom.us/my/csetheoryseminar , use password "theory"), unless noted otherwise.
Ivan Mikhailin (UCSD)
Monday, March 30, 2020, 2:00pm
A new approach to KRW conjecture
Details
Sam Buss (UCSD)
Monday, April 6, 2020, 2:00pm
CDCL Sat Solvers, and DRAT proofs with and without new extension variables
Details
Rayan Saab (UCSD)
Monday, April 13, 2020, 2:00pm
Binary data embeddings: Theory and Applications
Details
Eric Price (UT Austin)
Monday, April 20, 2020, 2:00pm
Separations and equivalences between turnstile streaming and linear sketching
Details
Jelani Nelson (UC Berkeley)
Monday, April 27, 2020, 2:00pm
Optimal terminal dimensionality reduction in Euclidean space
Details
Christos Tzamos (UW Madison)
Monday, May 4, 2020, 2:00pm
PAC Learning of Halfspaces with Noise: Efficient algorithms for the Massart and Tsybakov models
Details
Manuel Sabin
Monday, May 11, 2020, 2:00pm
How Do We Define "Fair" Responsibly?
Details
Prashant Vasudevan
Monday, May 18, 2020, 2:00pm
Cryptography from Information Loss
Details
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
Details
Winter 2020
David Zuckerman (UT Austin)
Monday, January 13, 2020, 2:00pm
Nearly Optimal Pseudorandomness From Hardness
Details
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
Details
Greta Panova (USC)
Monday, January 27, 2020, 2:00pm
Geometric Complexity Theory from an Algebro-Combinatorial perspective
Details
Nengkun Yu (University of Technology Sydney)
Monday, February 3, 2020, 2:00pm
Quantum Property Testing: Tomography and Identity Testing
Details
David Conlon (Caltech)
Monday, February 10, 2020, 2:00pm
The random algebraic method
Details
Monday, February 17, 2020, 2:00pm
No seminar (Presidents day)
Peter Nelson (Waterloo)
Wednesday, February 19, 2020, 2:00pm
Binary submatroids
Details
Sourya Roy (UC Riverside)
Monday, February 24, 2020, 2:00pm
Locally Testable Non-Malleable Codes
Details
Jiapeng Zhang (Harvard)
Monday, March 2, 2020, 2:00pm
Improved query-to-communication theorems via robust sunflowers
Details
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
Details
Grigory Yaroslavtsev (Indiana University, Bloomington)
Monday, October 14, 2019, 2:00pm
Advances in Hierarchical Clustering of Vector Data
Details
Russell Impagliazzo (UC San Diego)
Monday, October 21, 2019, 2:00pm
A Unified Approach to Smooth Boosting
Details
Cyrus Rashtchian (UC San Diego)
Monday, October 28, 2019, 2:00pm
Reconstructing Trees from Traces
Details
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
Details
Jessica Sorrell (UC San Diego)
Monday, November 25, 2019, 2:00pm
Efficient, Noise-Tolerant, and Private Learning via Boosting
Details
Michal Moshkovitz (UC San Diego)
Monday, December 2, 2019, 2:00pm
Unexpected Effects of Online K-means Clustering
Details
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
Details
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
Details
Ilias Diakonikolas (USC)
Monday, February 4, 2019, 2:00pm
The Degree-d Chow Parameters Problem
Details
Andrew Suk (UCSD)
Monday, February 11, 2019, 2:00pm
Multicolor Ramsey numbers for semi-algebraic graphs
Details
Monday, February 18, 2019, 2:00pm
No seminar (presidents day)
Yuval Ishai (Technion)
Monday, February 25, 2019, 2:00pm
Homomorphic Secret Sharing
Details
Leonard Schulman (Caltech)
Monday, March 4, 2019, 2:00pm
Invitation to Causal Inference
Details
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
Details
Shai Vardi (Caltech)
Monday, October 9, 2017, 2:00pm
Randomly coloring graphs of bounded treewidth
Details
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
Details
Clément Canonne (Columbia)
Monday, October 30, 2017, 2:00pm
When Fourier SIIRVs: Fourier-Based Testing for Families of Distributions
Details
Nikhil Bansal (TU Eindhoven)
Monday, November 6, 2017, 2:00pm
A fast polynomial space algorithm for Subset Sum
Details
Thomas Rothvoss (University of Washington)
Monday, November 13, 2017, 2:00pm
The matching polytope has exponential extension complexity
Details
Avishay Tal (Stanford)
Monday, November 20, 2017, 2:00pm
Computing Requires Larger Formulas than Approximating
Details
Tselil Schramm (Berkeley)
Monday, November 27, 2017, 2:00pm
Spectral Algorithms Capture Sum-of-Squares on Average
Details
Yin Tat Lee (University of Washington)
Monday, December 4, 2017, 2:00pm
KLS conjecture and log-Sobolev constant
Details
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
Details
Sanjam Garg (UC Berkeley)
"Identity-Based Encryption from the Diffie-Hellman Assumption"
Monday, April 17, 2017, 2:00pm
Details
Russell Impagliazzo (UCSD)
"Algorithmic Dense Model Theorems, Generative Adversarial Networks and Regularity"
Monday, April 24, 2017, 2:00pm
Details
Mihir Bellare (UCSD)
"Cryptography in the Age of Mass Surveillance"
Monday, May 1, 2017, 2:00pm
Details
Stefan Schneider (UCSD)
"On the Fine-grained Complexity of One-Dimensional Dynamic Programming"
Monday, May 8, 2017, 2:00pm
Details
Shachar Lovett (UCSD)
"The decision tree complexity of k-SUM is near-linear"
Monday, May 15, 2017, 2:00pm
Details
Alain Passelègue (ENS/UCLA)
"Private Circuits for Multiplication"
Monday, May 22, 2017, 2:00pm
Details
Chris Umans (CalTech)
"On cap sets and the group-theoretic approach to matrix multiplication"
Monday, June 5, 2017, 2:00pm
Details
Winter 2017
Omer Tamuz (Caltech)
Monday, January 9, 2017, 2:00pm
Quasi-regular sequences and optimal schedules for security games
Details
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
Details
Paul Beame (University of Washington)
Monday, January 30, 2017, 2:00pm
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Details
Nikhil Srivastava (Berkeley)
Monday, February 6, 2017, 2:00pm
Ramanujan Graphs from Finite Free Convolutions
Details
Mohit Singh (Georgia Institute of Technology)
Monday, February 13, 2017, 2:00pm
Constrained Subset Selection Problems, Permanents and Inequalities on Stable Polynomials
Details
Ilias Diakonikolas (University of Southern California)
Monday, February 27, 2017, 2:00pm
Computational
Details
Sivaramakrishnan Ramamoorthy (University of Washington)
Monday, March 6, 2017, 2:00pm
Lower bounds on non-adaptive data structures for median and predecessor search
Details
Konstantin Makarychev (Northwestern University)
Monday, March 13, 2017, 2:00pm
Solving optimization problems with a diseconomy of scale
Details
Spring 2016
Benjamin Perez (UCSD)
"Algebraic Number Theory for Crytographers"
Monday, April 4, 2016, 2:00pm
Details
Marco Carmosino (UCSD)
"Learning Algorithms from Natural Proofs"
Monday, April 11, 2016, 2:00pm
Details
Jiawei Gao (UCSD)
"Orthogonal Vectors is hard for first-order properties on sparse graphs"
Monday, April 18, 2016, 2:00pm
Details
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
Details
Kaave Hosseini (UCSD)
"The structure of protocols for XOR functions"
Monday, May 2, 2016, 2:00pm
Details
Stefan Schneider (UCSD)
"Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility"
Monday, May 9, 2016, 2:00pm
Details
Antonita Kolokolova (Memorial University of Newfoundland)
"The power of expander-based reasoning"
Monday, May 16, 2016, 2:00pm
Details
Winter 2016
Leonard Schulman (Caltech)
"Analysis of a Classical Matrix Preconditioning Algorithm"
Monday, January 11, 2016, 2:00pm
Details
Ananda Theertha Suresh (UCSD)
"Estimating the number of unseen species: How far can one foresee?"
Monday, January 25, 2016, 2:00pm
Details
Thomas Vidick (Caltech)
"Anchoring games for parallel repetition"
Monday, Feb 8, 2016, 2:00pm
Details
Adam Sheffer (Caltech)
"Few distinct distances implies no heavy lines"
Monday, Feb 22, 2016, 2:00pm
Details
Ilias Diakonikolas (USC)
"Density estimation via piecewise polynomial approximation in sample near-linear time"
Monday, Feb 29, 2016, 2:00pm
Details
Fall 2015
Shachar Lovett (UCSD)
"Nonclassical polynomials as a barrier to polynomial lower bounds"
Tuesday, September 29, 2015, 2:00pm
Details
Kobbi Nissim (Ben-Gurion University and CRCS@Harvard)
"Learning threshold functions under Differential Privacy"
Tuesday, October 13, 2015, 1:00pm
Details
Sanjoy Dasgupta (UCSD)
"An approximation algorithm for hierarchical clustering"
Tuesday, October 27, 2015, 1:00pm
Details
Michael Walter (UCSD)
"Analysis of Lattice Reduction Algorithms"
Tuesday, November 3, 2015, 1:00pm
Details
Shachar Lovett (UCSD)
"Algebraic Attacks against Random Local Functions and Their Countermeasures"
Tuesday, November 10, 2015, 1:00pm
Details
Mihir Bellare (UCSD)
"Closed Doors and Open Windows: Cryptography in the Age of Mass Surveillance"
Tuesday, November 17, 2015, 1:00pm
Details
James Aisenberg (UCSD)
"2-D Tucker is PPA complete"
Tuesday, November 24, 2015, 1:00pm
Details
Jiapeng Zhang (UCSD)
"Barriers to Black-Box Constructions of Traitor Tracing Systems"
Tuesday, November 31, 2015, 1:00pm
Details
Spring 2015
Ilya Mironov (Stanford)
"Cryptographic Reverse Firewalls"
Monday, April 6, 2015, 2:00pm
Details
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
Details
Alexander Kulikov (St. Petersburg Department of Steklov Institute of Mathematics)
"Linear circuit size upper and lower bounds"
Monday, April 13, 2015, 2:00pm
Details
David Kempe (University of South California)
"Incentivizing Exploration"
Monday, April 20, 2015, 2:00pm
Details
Paul Kirchner (ENS Paris)
"Subexponential algorithm for the subset-sum problem"
Monday, April 27, 2015, 2:00pm
Details
Shaddin Dughmi (University of South California)
"Algorithmic Bayesian Persuasion"
Monday, May 4, 2015, 2:00pm
Details
Akshay Balsubramani (UCSD)
"Non-Asymptotic Extensions to the Law of the Iterated Logarithm"
Monday, May 11, 2015, 2:00pm
Details
Kaave Hosseini (UCSD)
"On the structure of spectrum of small sets"
Monday, May 18, 2015, 2:00pm
Details
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
Details
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
Details
Omer Reingold
"Guilt-Free Interactive Data Analysis: The Reusable Holdout"
Monday, October 13, 2014, 11:00am (DLS talk, no regular seminar)
Details
Monday, October 20, 2014, 2:00pm
No seminar (STOC)
Daniel Kane (UCSD)
"Pseudorandom generators for Polynomial Threshold functions"
Monday, October 27, 2014, 2:00pm
Details
Silas Richelson (UCLA)
"An Algebraic Approach to Non-Malleability"
Monday, November 3, 2014, 2:00pm
Details
Leo Ducas (UCSD)
"Advances on Fully Homomorphic Encryption"
Monday, November 10, 2014, 2:00pm
Details
Igors Stepanovs (UCSD)
"Poly-Many Hardcore Bits for Any One-Way Function"
Monday, November 17, 2014, 2:00pm
Details
Kaave Hosseini (UCSD)
"Improved lower bounds for Arithmetic Regularity Lemma"
Monday, November 24, 2014, 2:00pm
Details
Marco Carmosini (UCSD)
"Tighter Connections between Derandomization and Circuit Lower Bounds"
Monday, December 1, 2014, 2:00pm
Details
Micahel Forbes (Simons Institute)
"Dimension Expanders via Rank Condensers"
Monday, December 8, 2014, 2:00pm
Details
Spring 2014
Leo Ducas (UCSD)
"The Versatility of Discrete Gaussians over Lattices"
Monday, April 7, 2014, 2:00pm
Details
Mario Szegedy (Rutgers)
"Impossibility Theorems and the Universal Algebraic Toolkit"
Monday, April 14, 2014, 2:00pm
Details
Victor Vianu (UCSD)
"Query determinacy and rewriting"
Monday, April 21, 2014, 2:00pm
Details
Vineet Bafna (UCSD)
"Algorithms Strategies for genomics and genetics"
Monday, April 28, 2014, 2:00pm
Details
Michael Walter (UCSD)
"Fast Lattice Point Enumeration with Minimal Overhead"
Monday, May 5, 2014, 2:00pm
Details
Jacques Verstraete (UCSD)
"Extremal Problems for Linear Dependencies"
Monday, May 12, 2014, 2:00pm
Details
Sourav Chakraborty (Chennai Mathematical Institute)
"Testing of Boolean Function Isomorphism"
Monday, May 19, 2014, 2:00pm
Details
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
Details
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
Details
Timon Hertli (ETH Zurich)
"Breaking the PPSZ Barrier for Unique 3-SAT"
Monday, January 27th, 2014, 2:00pm
Details
Russell Impagliazzo (UCSD)
"Fourier Concentration from Shrinkage"
Monday, February 3rd, 2014, 2:00pm
Details
Alexandr Andoni (Microsoft Research)
"Parallel Algorithms for Geometric Graph Problems"
Monday, February 10th, 2014, 2:00pm
Details
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
Details
Klim Efremenko (U. Chicago)
"List and Unique Coding of Interactive Communication"
Monday, February 24th, 2014, 2:00pm
Details
Shang-Hua Teng (USC)
"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"
Monday, March 3rd, 2014, 2:00pm
Details
Fall 2013
Leo Ducas (UCSD)
"The Chaitin's Constant"
Monday, September 30th, 2013, 2:00pm
Details
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
Details
Bjorn Tackmann (ETH Zurich)
"Constructive Cryptography - Introduction and Applications"
Monday, October 21th, 2013, 2:00pm
Details
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
Details
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
Details
Summer 2013
Jordi Levy (IIIA)
"The Nature of Industrial SAT Instances"
Monday, July 29, 2013, 2:00pm
Details
Chris Beck (Princeton)
"Strong ETH holds for regular resolution"
Thursday, August 1, 2013, 11:00am
Details
Russell Impagliazzo (UCSD)
"Finding Heavy Hitters from Lossy or Noisy Data"
Monday, August 5, 2013, 2:00pm
Details
Valentine Kabanets (Simon Fraser University)
"Mining Circuit Lower Bound Proofs for Meta-Algorithms"
Monday, August 12, 2013, 2:00pm
Details
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
Details
Daniele Micciancio (UCSD)
"An equational approach to secure multiparty computation"
Monday, April 8, 2013, 2:00pm
Details
Shweta Agrawal (UCLA)
"Discrete Gaussian Leftover Hash Lemma over Infinite Domains"
Monday, April 15, 2013, 2:00pm
Details
Shachar Lovett (UCSD)
"Non-Malleable Codes from Additive Combinatorics"
Monday, April 22, 2013, 2:00pm
Details
Yi-Kai Liu (NIST)
"Building one-time memories from isolated qubits"
Thursday, April 25, 2013, 2:00pm
Details
Chris Peikert (Georgia Tech)
"Practical Bootstrapping with Polylogarithmic Overhead"
Monday, April 29, 2013, 2:00pm
Details
Daniel Dadush (NYU)
"On the Lattice Smoothing Parameter Problem"
Monday, May 6, 2013, 2:00pm
Details
Benny Sudakov (UCLA)
"The phase transition in random graphs - a simple proof"
Wednesday, May 15, 2013, 11:00pm
Details
Mihir Bellare (UCSD)
"Semantic Security for the Wiretap Channel"
Monday, May 20, 2013, 2:00pm
Details
Russell Impagliazzo (UCSD)
"Simultaneons security and reliability amplification for unknown channels"
Wednesday, May 29, 2013, 12:00pm
Details
Spring 2012
Paul Valiant (UC, Berkeley)
''Central Limit Theorems and Tight Lower Bounds for Entropy Estimation''
Monday, April 2, 2012, 2:00 pm
Details
Shachar Lovett (Institute for Advanced Studies)
''Subspace-evasive sets''
Monday, April 9, 2012, 2:00 pm
Details
Shayan Oveis Gharan (Stanford)
''Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities''
Monday, April 16, 2012, 2:00 pm
Details
Madhur Tulsiani (Toyota Technological Institute)
''Towards An Optimal Query Efficient PCP?''
Monday, April 23, 2012, 2:00 pm
Details
Zvika Brakerski (Stanford University)
''Fully Homomorphic Encryption from LWE''
Monday, April 30, 2012, 2:00 pm
Details
Eva Tardos (Cornell University)
''Near-Optimal Greedy Mechanisms''
Monday, May 7, 2012, 11:00 am
Details
Andrew Drucker (MIT)
''New Limits to Instance Compression for Hard Problems''
Monday, May 14, 2012, 2:00 pm
Details
Alexandra Kolla (UIUC)
''Maximal Inequality for Spherical Means on the Hypercube''
Monday, June 4, 2012, 2:00 pm
Details
Russell Impagliazzo (UCSD)
''Pseudorandomness from Shrinkage''
Monday, June 11, 2012, 2:00 pm
Details
Winter 2012
Sandy Irani (UC, Irvine)
''Generating Quantum Gibbs States''
Monday, March 12, 2012, 2:00 pm
Details
Virginia Williams (UC, Berkeley)
''Multiplying matrices faster''
Wednesday, March 21, 2012,11:00 am
Details
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