Theory Lunch
If you are not on the mailing list, click here .
You can also subscribe to the RSS feed .
Once a week, the Berkeley theory community gets together,
socializes, has lunch, and then listens to an informal blackboard 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 (we may, however, set the room on fire if the talk runs late).
Fall 2009 Schedule
Wednesdays, noon, Wozniak Lounge (4th floor, Soda Hall ), unless otherwise specified
Spring 2009 Schedule
May 6, John Bethencourt
on signatures of reputation
April 29, Vladimir Braverman on measuring independence of datasets
April 22, Faculty Retreat April 15, Jonah Sherman on approximating sparsest cut
April 8, Christos
Papadimitriou on network games
April 1, Grant
Schoenebeck on the theory retreat
March 25, Spring Break March 18, Hoeteck Wee
on monotone cryptography
March 16, 12:30, 410 Hearst Mining Building Alexandra Kolla on graph sparsification
March 11, Parikshit Gopalan on finding duplicates in data streams
March 4, Luca Trevisan
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, no lunch Feb 4, 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
Spring 2008 Schedule
May 7, Kunal Talwar
April 30, Jonathan Katz on complete
fairness in secure two-party computation
April 23, Grant
Schoenebeck
April 16, Yaron Singer on
the hardness of being truthful
April 9, Jacob Abernethy on how to bet in a rigged casino using a random walk
April 2, Venkat Guruswami on compressed sensing, Euclidean sections, and the JL lemma
March 26, Spring Break
March 19, Alexander Rakhlin
on algorithms for online bandit
March 17, 410 Hearst Mining Building Greg Valiant
on the complexity of Nash equilibria of action-graph games
March 12, Allan Sly on MCMC on exponential random graphs
March 5, Luca Trevisan on
dense subsets of pseudorandom sets and arithmetic progressions in the primes
February 27, Madhur Tulsiani
on unique games on expanders
February 20, James Lee on spectral bounds without conformal mappings
February 13, Ravi
Kannan on random matrices and generative models
February 6, Albert Atserias on fractional edge covers and relational joins
January 30 [373 Soda ], Andrej Bogdanov
on pseudorandom generators for low-degree polynomials
January 23, 410 Hearst Mining Building Prahladh Harsha
on lower bounds for Probabilistically Checkable Proofs of Proximity