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.

- Feb 20: Paris Syminelakis on Algorithms for Kernel Evaluation in High Dimensions
- Feb 13: Chinmay Nirkhe on Good approximate quantum LDPC codes from spacetime Hamiltonians
- Feb 06: Sam Hopkins on How to Estimate the Mean of a Random Vector, Efficiently
- Jan 30: Nima Anari on Matroids Expand
- Jan 23: Dorit Aharnov on Stoquastic PCP vs. Randomness

- Dec 05: Arun Ganesh on Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
- Nov 28: Mohammad Hajiabadi on Trapdoor Functions from the Computational Diffie-Hellman Assumption
- Nov 21:
- Nov 14:
- Nov 07:
- Oct 31:
- Oct 24:
- Oct 17:
- Oct 10:
- Oct 03:
- Sep 26: Urmila Mahadev on Classical Homomorphic Encryption for Quantum Circuits
- Sep 19: Aloni Cohen on Towards Modeling Singling Out
- Sep 12: Nick Spooner on Multi-prover interactive proofs: Classical, quantum, and no-signaling
- Sep 05: Avi Wigderson on Group actions beget polytopes

- May 02: Vijay Vazirani on Distributive Lattices, Stable Matchings, and Robust Solutions
- Apr 25: Fotis Iliopoulos on A New Perspective on Stochastic Local Search and the Lovasz Local Lemma
- Apr 18: Ilya Razenshteyn on Nearest Neighbors for General Distances
- Apr 11: Aaron Schild on Spectral Subspace Sparsification
- Apr 04: Henry Yuen on How complex can entangled games be?
- Mar 28:
- Mar 21: Dima Kogan on The Discrete-logarithm Problem with Preprocessing
- Mar 14:
- Mar 07: Sam Hopkins on High-dimensional clustering, mixture models, and sum of squares proofs
- Feb 28: Manuel Sabin on Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity
- Feb 21: Thodoris Lykouris on Small-loss bounds for online learning with partial information
- Feb 14: Ido Nachum on Learners that Use Little Information
- Feb 07: Emanuele Natale on State-Efficient Plurality Consensus in Population Protocols
- Jan 31: Vijay Bhattiprolu on Approximability of matrix p-to-q norms
- Jan 24:

- Dec 06: Akshayaram Srinivasan on Two-round Multiparty Secure Computation under Minimal Assumptions
- Nov 29: Aviad Rubinstein on Distributed PCP Theorems for Hardness of Approximation in P
- Nov 22:
- Nov 15: Pasin Manurangsi on Parameterized Inapproximability of Dominating Set
- Nov 08: Ilias Diakonikolas on Computational Lower Bounds for Statistical Estimation Problems
- Nov 01: Jingcheng Liu on The Ising Partition Function: Zeros and Deterministic Approximation
- Oct 25: Fan Wei on Local max-cut in smoothed polynomial time
- Oct 18: Igor Shinkar on Testing Linearity against No-Signaling Strategies
- Oct 11: Thatchaphol Saranurak on Expander decomposition
- Oct 04: Aaron Schild on Localization of electrical flows
- Sep 27: Igor Pak on Complexity of short generating functions
- Sep 20: Raghu Meka on Learning discrete markov random fields with nearly optimal runtime and sample complexity
- Sep 13: Aleksander Madry on Matrix Scaling and Balancing via Second-order Optimization
- Sep 06: Nima Anari on Strongly Rayleigh Measures in Counting and Optimization
- Aug 30: Euiwoong Lee on An Algorithm for k-Vertex Separator and Applications to Vertex Deletion Problems

- May 10: Luca Trevisan on Some simple distributed network processes
- May 03: Tom Gur on Distribution Testing Lower Bounds via Reductions from Communication Complexity
- Apr 26: Alexandra Kolla on Signings, expander graphs and perfect 2-matchings
- Apr 12: Huacheng Yu on Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- Apr 05: Arnab Bhattacharyya on On lower bounds for locally correctable codes
- Mar 29:
- Mar 22: Andrej Bogdanov on Threshold Secret Sharing Requires a Linear-Size Alphabet
- Mar 15:
- Mar 08: Alireza Rezaei on An MCMC Approach for Sampling Determinantal Point Processes and Strongly Rayleigh Measures
- 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: Akshayaram 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

- Apr 29: Shay Solomon on Dynamic Approximate Matchings: A Density-Sensitive Approach
- Apr 22: Yaron Singer on Combinatorial Optimization under Noise
- Apr 15: Sam Wong on The cutting plane method and submodular minimization
- Apr 08:
- Apr 01: Prasad Raghavendra on Multiplicative weight updates and lower bounds for LP/SDP size
- Mar 25:
- Mar 18:
- Mar 11: Ron Lavi on Competition among asymmetric sellers with fixed supply
- Mar 04:
- Feb 25: Jingcheng Liu on Approximate counting via correlation decay
- Feb 18:
- Feb 11: Antonio Blanca on Giant components and mixing times
- Feb 04: Aviad Rubinstein on Nash equilibrium and birthday repitition
- Jan 28: Jonah Brown-Cohen on Combinatorial optimization via polymorphisms

- Dec 10: Sid Barman on An Approximate Version of Caratheodory's Theorem and Its Algorithmic Applications
- Dec 03:
- Nov 26:
- Nov 19: George Piliouras on Games, Dynamics, and Average-case analysis
- Nov 12:
- Nov 05: Jamie Morgenstern on Simple Mechanisms with Simple Stragies
- Oct 29:
- Oct 22: Tselil Schramm on A Better Approximation for Correlation Clustering
- Oct 15: Gary Miller on Generalized Laplacians
- Oct 08: Sanjam Garg on Indistinguishability Obfuscation: Definition and Amplification from NC^1 to General Circuits
- Oct 01: James Lee on Expansion Beyond The Spectral Gap: Curvature, Entropy, and Coupling
- Sep 24:
- Sep 17: Luca Trevisan on The Riemann Hypothesis for Graphs
- Sep 10: Christos Papadimitriou on Learning on the cheap

- Apr 30: Dimitris Achlioptas on The Local Lemma as a Random Walk
- Apr 23: Mario Szegedy on Impossibility Theorems and the Universal Algebraic Toolkit
- Apr 16:
- Apr 09: Seung Woo Shin on DWave
- Apr 02: Justin Thaler on A Crash Course on Fast Interactive Proofs
- Mar 19:
- Mar 12:
- Mar 05: Jonathan Herman on Social Connectivity - Coalescence Process of Connected Components of a Random Acquaintances Graph Determined by Collisions of Random Walks
- Feb 26:
- Feb 19: Shai Vardi on Local Computation
- Feb 12: Gregory Valiant on Instance-Optimal Testing
- Feb 05: Rishi Gupta on Model-Independent Algorithms for Social Networks

- Dec 03: Ning Tan on Symmetric LP and SDP relaxation
- Nov 27:
- Nov 20: Matt Weinberg on An algorithmic proof of Border's theorem
- Nov 13: Seung Woo Shin on The D-Wave Controversy
- Nov 06: Dominik Scheder on How to leak the darkest secrets in relative safety
- Oct 30:
- Oct 23: Guoming Wang on A quantum algorithm for approximating the effective resistances of electrical networks
- Oct 16: Aviad Rubinstein on Reconstructing a Distribution Over Permutations
- Oct 09: Nihar Shah on Secret Sharing Across a Network with Low Communication Cost
- Oct 02: Anindya De on Limit theorems for Gaussian chaoses and applications
- Sep 25: Paul Christiano on Manipulation-proof reputation systems via online learning
- Sep 18: Sev Gharibian on Approximation algorithms for quantum constraint satisfaction problems
- Sep 11: James Lee on Lifts of polytopes, approximation, and linear programming

- May 08: Dick Karp and Alistair Sinclair on The Simons Institute
- May 01: Dick Karp on Algorithms for Finding Good Coins and Significant Disease Associations
- Apr 24: Anupam Gupta on Sparsest Cut for Bounded Treewidth Graphs
- Apr 17: Shayan Oveis-Gharan on New Approaches to the Traveling Salesman Problem
- Apr 10: Yaron Singer on Adaptive Seeding in Social Networks (and other Animals)
- Apr 03: James Lee on Information theory against an adversary (or for Umesh, Quantum hypothesis testing)
- Mar 20:
- Mar 13: Ilan Adler on A direct reduction of PPAD Lemke-verified linear complementarity problems to bimatrix games
- Mar 06: Nihar Shah on Codes for efficient and reliable distributed storage
- Feb 27: Christos Papadimitriou on Game Theoretic Modeling of the Web
- Feb 20: Paul Christiano on A Coordination Game in Networks
- Feb 13: Siu Man Chan on Pebble Games and Complexity
- Feb 06: Ravi Kannan on Non-negative Matrix Factorization
- Jan 30: Anindya De on The Sum-of-Squares Hierarchy and Max Cut

- 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