Once a week, the Berkeley theory community gets together, socializes, has lunch, and then listens to an informal board presentation on open questions, new results, old results worth not forgetting, or whatever is fit to entertain a crowd of theoreticians. At the theory lunch, we do not believe in using slides, waiting until the end to ask questions, or stopping the speaker when he or she runs out of time.

Unless otherwise specified, the event occurs Wednesdays 12:00-13:00 in the Wozniak Lounge (on the 4th floor of Soda Hall). If you want to join the mailing list, click here.

- Mar 01: Anindya De on Better bounds for trace reconstruction
- Feb 22: Ben Weitz on On the Bit Complexity of Sum-of-Squares Proofs
- Feb 15: Avi Wigderson on Some basic problems and results from Invariant Theory (and its interactions with CS)
- Feb 08: Yevgeniy Dodis on Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited
- Feb 01: Marc Khoury on Restricted Constrained Delaunay Triangulations
- Jan 25: Manuel Sabin on Average-Case Fine-Grained Hardness
- Jan 18: Eylon Yogev on Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

- Dec 14: Shiri Chechik on Fully dynamic all pairs shortest paths with worst case bounds
- Dec 07: Pasin Manurangsi on Almost-polynomial Ratio ETH-hardness of Densest k-Subgraph
- Nov 30: Amir Abboud on A Sequence of Hardness Results for Longest Common Subsequence
- Nov 23:
- Nov 16:
- Nov 09: Lin Yang on Streaming Symmetric Norms via Measure Concentration
- Nov 02: Daniel Masny on CCA-secure public key encryption from low-density subset sum
- Oct 26: Alexandros Psomas on On Dynamic Fair Division
- Oct 19: Gil Cohen on Recent advances in randomness extractors and their applications
- Oct 12: Tselil Schramm on Strongly refuting random constraint satisfaction problems below the spectral threshold
- Oct 05: Nir Ailon on How Speeding Up an Algorithm Leads to Uncertainty: Fourier Transform Computation
- Sep 28: Aviad Rubinstein on Dilemma Prisoners should upgrade their data plan
- Sep 21: Kira Goldner on The FedEx Problem
- Sep 14: Igor Shinkar on On Percolation and NP-Hardness
- Sep 07: Andrea Lincoln on Deterministic Time-Space Tradeoffs for k-SUM

- May 11: Dick Karp on Rearrangement in Restricted Space
- May 04: Ran Gelles on Constant-rate coding for multiparty interactive communication is impossible
- Apr 27:
- Apr 20: Pratyay Mukherjee on Round Optimal Multi-party Computation using Fully-homomorphic Encryption
- Apr 13: Ariel Gabizon on Low-degree non-boolean dispersers for subspaces
- Apr 06: Holger Dell on Counting subgraphs modulo two
- Mar 30: Julian Shun on Sequential algorithms that are highly parallel
- Mar 23:
- Mar 16: Amit Daniely on Complexity theoretic limitations on learning
- Mar 09:
- Mar 02: Rishi Gupta on A PAC Approach to Application-Specific Algorithm Selection
- Feb 24: Benjamin Weitz on Symmetric SDP Lower Bounds for the Perfect Matching Problem
- Feb 17: Stephen Alstrup on Recent results (STOC/FOCS’15 and SODA’16) on labeling schemes and induced universal graphs
- Feb 10: Laura Florescu on Spectral thresholds in the bipartite stochastic block model
- Feb 03: Daniel Reichman on Smoothed analysis of connected graphs
- Jan 27: Miklos Racz on Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
- Jan 20: Alan Roytman on Packing small vectors

- Dec 09: Yin Tat Lee on Uniform Sampling for Matrix Approximation
- Dec 02: Di Wang on Accelerated First-order Method for Packing and Covering LPs
- Nov 25:
- Nov 18: Akshayram Srinivasan on On the Exact Cryptographic Hardness of Finding a Nash Equilibrium
- Nov 11: Greg Bodwin on The n^{4/3} Additive Spanner Bound is Tight
- Nov 04: Mark Zhandry on Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key
- Oct 28: Nihar Shah on "Multiplicative" Incentive Mechanisms for Crowdsourcing
- Oct 21: Yannai A. Gonczarowski on Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
- Oct 14: Alessandro Chiesa on Interactive oracle proofs
- Oct 07: Muli Safra on Open questions regarding boolean functions with potential applications
- Sep 30: Gautam Kamath on Optimal Testing for Properties of Distributions
- Sep 23: Nikhil Srivastava on Ramanujan Graphs from Finite Free Convolutions
- Sep 16: Tselil Schramm on Overcomplete tensor decomposition: speeding up sum-of-squares algorithms

- May 12: Lofti Zadeh on Computing with imprecise probabilities
- May 05: Fritz Sommer on A review of mathematical problems in theoretical neuroscience
- Apr 28: Thomas Watson on Barriers to average-case complexity
- Apr 21: James Lee on A remarkable relationship between cover times of graphs and random projections
- Apr 14: Dick Karp on Online algorithms for implicit hitting set problems
- Apr 07: Christos Papadimitriou on Optimal auctions
- Mar 31: Thomas Vidick on A lower bound on a decision problem
- Mar 15: Lorenzo Orecchia on Fast algorithms for balanced cut and local random walks
- Mar 03:
- Feb 24: Anindya De on Extractors via complexity amplification
- Feb 17: Ryan Williams on Improving exhaustive search implies superpolynomial lower bounds
- Feb 10: Dirk Sudhiolt on Ant Colony Optimization
- Feb 03: Christos Papadimitriou on Risk in games
- Jan 27: Sanjeev Arora on Computational complexity and information asymmetry in financial derivatives

- Nov 04: Gagang Noel on The approximability of combinatorial problems with multi-agent submodular cost functions
- Oct 28: Greg Valiant on Learning mixtures of high-dimensional Gaussians
- Oct 21: Risi Kondor on Solving quadratic programming in Fourier space
- Oct 14: Luca Trevisan on Pseudorandomness for modular sums
- Oct 07: Yaron Singer on Mechanism design with a budget constraint
- Sep 30: Grant Schoenebeck on Coordination in social networks
- Sep 23: Christos Papadimitriou on Strictly competitive games
- Sep 16: Luca Trevisan on Inverting one-way functions with circuits
- Sep 09: Silvio Lattanzi on Affiliation networks

- May 06: John Bethencourt on Signatures of reputation
- Apr 29: Vladimir Braverman on Measuring independence of datasets
- Apr 22:
- Apr 15: Jonah Sherman on Approximating sparsest cut
- Apr 08: Christos Papadimitriou on Network games
- Apr 01: Grant Schoenebeck on The theory retreat
- Mar 25:
- Mar 18: Hoeteck Wee on Monotone cryptography
- Mar 16: Alexandra Kolla on Graph sparsification
- Mar 11: Parikshit Gopalan on Finding duplicates in data streams
- Mar 04: Luca Trevisan on TBA
- Feb 25: James Cook on The security of Goldreich's one-way function candidate
- Feb 18: Sergey Yekhanin on Deterministic approximation algorithms for the nearest codeword problem
- Feb 11:
- Feb 04: Henry Lin on Reducing directed max flow to bipartite matching
- Jan 28: Jacob Abernethy on Optimal randomized paging by guessing the future
- Jan 21: Mihai Patrascu on Succincter data structures

- May 07: Kunal Talwar on Lower bounds for near neighbor search
- Apr 30: Jonathan Katz on Complete fairness in secure two-party computation
- Apr 23: Grant Schoenebeck on Integrality gaps in the Lasserre hierarchy
- Apr 16: Yaron Singer on The hardness of being truthful
- Apr 09: Jacob Abernethy on How to bet in a rigged casino using a random walk
- Apr 02: Venkat Guruswami on Compressed sensing, Euclidean sections, and the JL lemma
- Mar 26:
- Mar 19: Alexander Rakhlin on Algorithms for online bandit
- Mar 17: Greg Valiant on The complexity of Nash equilibria of action-graph games
- Mar 12: Allan Sly on MCMC on exponential random graphs
- Mar 05: Luca Trevisan on Dense subsets of pseudorandom sets and arithmetic progressions in the primes
- Feb 27: Madhur Tulsiani on Unique games on expanders
- Feb 20: James Lee on Spectral bounds without conformal mappings
- Feb 13: Ravi Kannan on Random matrices and generative models
- Feb 06: Albert Atserias on Fractional edge covers and relational joins
- Jan 30: Andrej Bogdanov on Pseudorandom generators for low-degree polynomials
- Jan 23: Prahladh Harsha on Lower bounds for probabilistically checkable proofs of proximity

- May 02: Nisheeth Vishnoi on Integrality gaps for sparsest cut
- Apr 25: Sergey Yekhanin on Locally decodable codes
- Apr 18: Luca Trevisan on Proving unsatisfiability of random k-SAT formulas
- Apr 11: Jayanth Kannan on New routing protocols
- Apr 04: Costis Daskalakis on Decoding error-correcting codes via linear programming
- Mar 28:
- Mar 21: Jacob Abernethy on Experts algorithms, random sampling, and approximating the permanent
- Mar 14:
- Mar 12: Lorenzo Orecchia on Expert algorithms
- Mar 07: Grant Schoenebeck on Integrality gaps for Lovasz-Schrijver relaxations
- Feb 28: Konstantin and Yuri Makarychev on Near-optimal algorithms for maximum constraint satisfaction problems
- Feb 21: Elchanan Mossel on Asymptotics of games
- Feb 14: Umesh Vazirani on D-wave's "quantum computer"
- Feb 07: Albert Atserias on Distinguishing SAT from polynomial-size circuits
- Jan 31: Dick Karp on Noisy binary search
- Jan 24: Robert Špalek on How negative weights make adversaries stronger

- Nov 29: Kamalika Chaudhuri on A clustering problem
- Nov 22:
- Nov 15: Sandu Popescu on Non-local correlations and communication complexity
- Nov 08: Alexandra Kolla on Honest-verifier zero knowledge
- Nov 01: Omid Etesami on Ad auctions and market equilibrium
- Oct 25: Ravi Kannan on Sampling in large matrices and tensors
- Oct 18: Iordanis Kerenidis on The one-way communication complexity of the Boolean Hidden Matching problem
- Oct 11: Nikhil Devanur on The bidirected cut relaxation of Minimum Steiner Tree
- Oct 04: Mani Narayanan on Tractable graph matching problem
- Sep 27: Costis Daskalakis on Reconstructing phylogenies from minimum information
- Sep 20: Henry Lin on Network decompositions and the power of choice in Polya urns
- Sep 13: Ben Reichardt on Fault tolerance in quantum computation
- Sep 06: Dick Karp on Sorting partial orders

- May 10: Miklos Santha on Efficient testing of groups
- May 03: Robi Krauthgamer on Algorithms in negatively curved spaces
- Apr 26: Dieter van Melkebeek on Hierarchies for semantic models of computation
- Apr 19: Tom Hayes on Eigenvalues, Dobrushin uniqueness, and randomly coloring planar graphs
- Apr 12: Shafi Goldwasser on Obfuscation
- Apr 05: Bjorn Poonen on Hilbert's 10th problem over the rationals
- Mar 29:
- Mar 22: Eric Friedman on The geometry of chomp
- Mar 15: Eva Tardos on Collusion in congestion games
- Mar 13: Kamalika Chaudhuri on Bounded-degree MST
- Mar 08: Hoeteck Wee on Finding Pessiland
- Mar 01: Luca Trevisan on Gowers uniformity, influence of variables, and probabilistically checkable proofs
- Feb 22: Satish Rao on Embedding expanders into graphs
- Feb 15: Gadiel Seroussi on Universal types and simulation of individual sequences
- Feb 08: Vijay Vazirani on Resource allocation markets
- Feb 01: Christos Papadimitriou on PPAD

- Dec 14:
- Dec 07: Bill Steiger on TBA
- Nov 30: Bobby Kleinberg on Geometric routing in hyperbolic space
- Nov 23: Luca Trevisan on The Kakeya problem
- Nov 16: Alex Russell on The hidden subgroup problem
- Nov 09: Cris Moore on Power-low degree distributions in regular graphs
- Nov 02: Luca Trevisan on Szemeredi's theorem
- Oct 26:
- Oct 19: Kunal Talwar on Approximation algorithms for unique games
- Oct 12: Moshe Babaioff on Undominated strategies
- Oct 05: Roee Engelberg on Equilibria in online games
- Sep 28: Robi Krauthgamer on Embedding edit distance in other metric spaces
- Sep 21: Dick Karp on Geometric optics, linear programming, and routing in sensor networks
- Sep 14: Alex Slivkins on Triangulation and embedding using small sets of beacons
- Sep 07: Sanjoy Dasgupta on Active learning
- Aug 31: Moni Naor on Scratch-off cryptography

- May 04: Andrea Montanari on Random satisfiability and coding problems
- Apr 27: James Lee on Negative results for sparsest cut and metric embeddings
- Apr 20: Luca Trevisan on Another Isreali breakthrough in complexity theory
- Apr 13: Scott Aaronson on Computational complexity in the physical universe
- Apr 06: Sebastien Roch on Learning phylogenies
- Mar 30: Salil Vadhan on Pseudorandom walks and the L vs RL problem
- Mar 23:
- Mar 14: Rohit Khandekar on Finding balanced cuts using single-commodity max flows
- Mar 09: Henry Lin on Selfish routing and Braess's paradox
- Mar 02: Umesh Vazirani on The hidden subgroup problem in non-abelian groups
- Feb 23: Luca Trevisan on Applied additive number theory
- Feb 16: Peter Winkler on Scheduling sequences of reals
- Feb 09: René Beier on Smoothed analysis of combinatorial optimization problems
- Feb 02: Shakhar Smorodinsky on Geometric permutations and transversal theory
- Jan 26: Vijay Vazirani on AdWords and generalized online matching
- Jan 19: Adam Kalai on Gradient descent without a gradient

- Dec 08: Tomás Feder on TBA
- Dec 01: Robi Krauthgamer on TBA
- Nov 24: Elias Koutsoupias on TBA
- Nov 17: Camil Demetrescu on Shortest paths in dynamic graphs
- Nov 10: Luca Trevisan on New result in complexity theory
- Nov 03: Gene Myers on Genome assembling and string graph
- Oct 27: Sanjeev Arora on TBA
- Oct 20:
- Oct 13: Yuval Peres on Markov type of a metric space
- Oct 06: James Lee on Euclidean embeddings of negative-type metrics
- Sep 29: Alistair Sinclair on Non-commutative circuits for the determinant
- Sep 22: John Canny on Privacy
- Sep 15: Shakhar Smorodinsky on Locally Delaunay graphs
- Sep 08: Hoeteck Wee on Amplification of hardness for one-way functions
- Sep 01: Luca Trevisan on Hierarchy theorems for probabilistic time

- May 19: Cyntia Dwork on Privacy in public databases
- May 12: Hoeteck Wee on Obfuscation
- May 07: Leonard Schulman on Clustering
- May 05: Frank McSherry on Spectral filtering and Gaussian mixtures
- Apr 28: Tim Roughgarden on Correlated equilibria
- Apr 21: Kamal Jain on Price-collecting Steiner forest
- Apr 14: Kamalika Chaudhuri on Degree-restricted MST
- Apr 07: Luca Trevisan on Inapproximability results proved using average-case assumptions
- Mar 31: Andrej Bogdanov on Pseudorandomness against degree-2 adversaries
- Mar 24:
- Mar 15: Iordanis Kerenidis on Communication complexity
- Mar 10: Ryan O'Donnell on Learning monotone functions
- Mar 03: Kobbi Nissim on Communication versus computation
- Feb 25: Nati Linial on Simplicial complexes
- Feb 18: Arnab Nilim on Optimal Markov decision problems
- Feb 11: Kris Hildrum on Peer-to-peer networks
- Feb 04: Scott Aaronson on The communication complexity of agreement
- Jan 28:
- Jan 21: Baruch Awerbuch on Adaptive routing

- Dec 10: Paul Spirakis on TBA
- Dec 03:
- Nov 26: Luca Trevisan on The average-case complexity of k-SAT
- Nov 19: Dick Karp on The min-entropy set-cover problem
- Nov 12: Kenji Obata on Integral multicommodity flow
- Nov 05: Robert Krauthgamer on Near neighbor search in general metric spaces
- Oct 29: Jonathan Shewchuk on Unfolding three-dimensional meshes
- Oct 22: James Lee on TBA
- Oct 15: David Wagner on Security against side channel attacks
- Oct 08: David Williamson on Intranet search problem
- Oct 01: Scott Aaronson on Non-uniform BQP versus EXP
- Sep 24: Daniele Micciancio on TBA
- Sep 17: Sridhar Rajagopalan on Sorting-based streaming algorithms
- Sep 10: Sanjoy Dasgupta on Hierarchical clustering
- Sep 03: Christos Papadimitriou on TBA

- May 15: Roded Sharan on A fully dynamic algorithm for cographs
- May 08: Tom Bohman on On the Shannon capacities of the complements of odd cycles
- May 01: James Lee on Bounded geometries, fractals, and low-distortion embeddings
- Apr 24: Luca Trevisan on Exponential time algorithms for 3SAT and 3-coloring
- Apr 17: Dorit Aharonov on TBA
- Apr 10: Andrej Bogdanov on Worst-case to average-case reductions in NP
- Apr 03: James Lee on A paper by Oded Regev
- Mar 27:
- Mar 20: Elchanan Mossel on Pseudorandom generators in NC0
- Mar 13: Luca Trevisan on A paper by Impagliazzo and Kabanets
- Mar 06: Vladlen Koltun on Open problems in combinatorial geometry
- Feb 27: Robert Krauthgamer on Polylogarithmic inapproximability
- Feb 20: Eran Halperin on The intregrality gap of the group steiner tree problem
- Feb 13: Muli Safra on TBA
- Feb 06: Christos Papadimitriou on TBA
- Jan 30: Kunal Talwar on Embeddings of general metrics in tree metrics

- Dec 04: Robert Krauthgamer on Planar separators
- Nov 27:
- Nov 20: Elchanan Mossel on Error correction of random bits
- Nov 13: James O'Brien on An energy driven approach to linkage unfolding
- Nov 06: Eran Halperin on A stocastic process on the hypercube
- Oct 30: Luca Trevisan on Amplification of average-case complexity within NP
- Oct 23: Dimitris Achlioptas on Random k-SAT
- Oct 16: Chris Harrelson on The k-traveling repairman problem
- Oct 09: Satish Rao on Graph separator theorems
- Oct 02: James Lee on Embedding graphs into the integer lattice
- Sep 25: Luca Trevisan on Testing that a function depends on k variables or less
- Sep 18: Iordanis Kerenidis on Locally decodable codes
- Sep 11:
- Sep 04: Shakhar Smorodinsky on A coloring problem

- May 09: Jonathan Shewchuk on Duality in computational geometry
- May 02: Andrej Bogdanov on Property testing of bipartiteness
- Apr 25:
- Apr 18: Milena Mihail on The spectra of power-law graphs
- Apr 11: Amin Saberi on The complexity of combinatorial auctions
- Apr 04: Scott Aaronson on Quantum Fourier sampling
- Mar 28:
- Mar 21: Luca Trevisan on Data compression
- Mar 14: Robert Krauthgamer on Property testing of dimensionality
- Mar 07: Wim van Dam on Adiabatic quantum computing
- Feb 28: Dana Randall on Simulated tempering
- Feb 21: Vijay Vazirani on Trellis codes
- Feb 14: Ziv Bar-Yossef on Communication complexity
- Feb 07: Luca Trevisan on Average-case complexity
- Jan 31: Eyal Amir on Treewidth approximation
- Jan 24: Alistair Sinclair on Random balanced permutations

- Nov 22:
- Dec 06: Iordanis Kerenidis on Collaborative filtering
- Nov 29: Satish Rao on Disjoint paths
- Nov 22:
- Nov 15: Kenji Obata on Lower bound for property testing
- Nov 08: Sivan Toledo on Linear algebraic algorithms
- Nov 01: David Wagner on Homomorphic signature schemes
- Oct 25: Christos Papadimitriou on Computational game theory
- Oct 18: Yuval Rabani on Directed multicuts
- Oct 11: Amir Shpilka on Lower bounds for matrix product
- Oct 04: Subhash Khot on A class of two-query PCPs
- Sep 27: Luca Trevisan on Sub-linear time MST approximation
- Sep 20: Beini Zhou on Black-box and non-black-box zero knowledge
- Sep 13: Sanjeev Arora on The nondeterministic hierarchy theorem
- Sep 11: Venkat Guruswami on Hypergraph coloring