Theory Lunch Archives
Schedules from Fall 2001 to Spring 2007
Spring 2007 Schedule
- May 2 (last theory lunch of Spring'07), Nisheeth Vishnoi
on integrality gaps for sparsest cut
- April 25, Sergey Yekhanin on
locally decodable codes
- April 18, Luca Trevisan on
proving unsatisfiability of random ksat formulas
- April 11, Jayanth Kannan on
new routing protocols
- April 4, Costis Daskalakis
on decoding error-correcting codes via linear programming
- March 28, no lunch
- March 21, Jacob Abernethy on
experts algorithms, random sampling, and approximating the permanent
- March 14, no lunch
- March 12, (in 410 Hearst Mining Building)
Christos Papadimitriou on theory at Berkeley and Lorenzo Orecchia on expert
algorithms
- March 7, Grant Schoenebeck
on integrality gaps for Lovasz-Schrijver relaxations
- February 28, Konstantin
and Yuri Makarychev on
near-optimal algorithms for maximum constraint satisfaction problems
- February 21, Elchanan Mossel
on asymptotics of games
- February 14, Umesh Vazirani
on D-wave's "quantum computer"
- February 7, Albert Atserias on distinguishing SAT from polynomial-size circuits
- January 31, Dick Karp on noisy binary search
- January 24, Robert Špalek on how negative weights make adversaries stronger
Fall 2006 Schedule
- November 29, Kamalika Chaudhuri on a clustering problem
- November 22, no lunch
- November 15, Sandu Popescu on non-local correlations and communication complexity
- November 8, Alexandra Kolla on honest-verifier zero knowledge
- November 1, Omid Etesami on ad auctions and market equilibrium
- October 25, Ravi Kannan on sampling in large matrices and tensors
- October 18, Iordanis Kerenidis on the one-way communication complexity of the Boolean Hidden Matching problem
- October 11, Nikhil Devanur on the bidirected cut relaxation of Minimum Steiner Tree
- October 4, Mani Narayanan on a tractable graph matching problem
- September 27 Costis Daskalakis on reconstructing phylogenies from minimum
information
- September 20 Henry Lin on network decompositions and the power of choice in Polya
urns
- September 13 Ben Reichardt on fault tolerance in quantum computation
- September 6, Dick Karp on sorting partial orders
Spring 2006 Schedule
- May 10, Miklos Santha on efficient
testing of groups
- May 3, Robi Krauthgamer on
algorithms in negatively curved spaces
- April 26, Dieter van Melkebeek
on hierarchies for semantic models of computation
- April 19, Tom Hayes
on eigenvalues, Dobrushin uniqueness, and randomly coloring planar graphs
- April 12, Shafi Goldwasser
on obfuscation
- April 5, Bjorn Poonen
on Hilbert's 10th problem over the rationals
- March 29, Spring Break
- March 22, Eric Friedman
on the geometry of chomp
- March 15, Eva Tardos on collusion in congestion games
- March 13 12:30, 410 Hearst Mining Building [note unusual
day, time and place], Kamalika Chaudhuri
on bounded-degree MST
- March 8, Hoeteck Wee on
finding Pessiland
- March 1, Luca Trevisan
on Gowers uniformity, influence
of variables, and probabilistically checkable proofs
- February 22, Satish Rao
on embedding expanders into graphs
- February 15, Gadiel Seroussi on universal types and simulation
of individual sequences
- February 8, Vijay Vazirani
on resource allocation markets (see papers here
and here)
- February 1, Christos
Papadimitriou
on PPAD
Fall 2005 Schedule
- December 14, free lunch
- December 7, Bill Steiger
- November 30, Bobby Kleinberg
on geometric routing in hyperbolic space
- November 23, Luca Trevisan
on the Kakeya problem
- November 16, Alex Russell on
the hidden subgroup problem
- November 9, Cris Moore on
power-low degree distributions in regular graphs
- November 2, Luca Trevisan
on Szemeredi's theorem
- October 26 no lunch (FOCS)
- October 19, Kunal Talwar on
approximation algorithms for unique games
- October 12, Moshe Babaioff
on undominated strategies
- October 5, Roee Engelberg
on equilibria in online games
- September 28, Robi Krauthgamer on
embedding edit distance in other metric spaces
- September 21,[In 410 Hearst Mining]
Dick Karp
on geometric optics, linear programming, and routing in sensor networks
- September 14, Alex Slivkins
on triangulation
and embedding using small sets of beacons
- September 7, Sanjoy Dasgupta
on active learning
- August 31, Moni Naor
on scratch-off cryptography
Spring 2005 Schedule
- May 4, Andrea Montanari on random satisfiability and coding problems
- April 27, James Lee on
negative results for sparsest cut and metric embeddings
- April 20, Luca Trevisan
on another
Isreali breakthrough in complexity theory
- April 13, [In 380 Soda] Scott Aaronson on computational complexity in the physical universe
- April 6, Sebastien Roch on learning phylogenies
- March 30, Salil Vadhan on
pseudorandom walks and the L vs RL problem
- March 23 spring break
- March 14 [In 380 Soda, 12:30] Rohit Khandekar on finding balanced cuts using single-commodity max flows (note: March 14 is a Monday)
- March 9 [In 380 Soda] Henry Lin on selfish routing and Braess's paradox
- March 2, Umesh Vazirani on the hidden subgroup problem in non-abelian groups
- February 23, Luca Trevisan on applied additive number theory, see papers here, here, here, here and here
- February 16, [In 410 Hearst Mining] Peter Winkler on scheduling sequences of reals
- February 9 [In 410 Hearst Mining] René Beier on smoothed analysis of combinatorial optimization problems
- February 2, Shakhar Smorodinsky on geometric permutations and transversal theory
- January 26 [In 410 Hearst Mining] Vijay Vazirani on AdWords and Generalized Online Matching
- January 19, Adam Kalai on doing gradient descent without a gradient
Fall 2004 Schedule
- December 8, Tomás Feder
- December 1, Robi Krauthgamer
- November 24, Elias Koutsoupias
- November 17, Camil Demetrescu on shortest paths in dynamic graphs
- November 10, [In 400 Cory] Luca Trevisan on a new result in complexity theory
- November 3, Gene Myers on genome assembling and string graphs
- October 27, [In 400 Cory] Sanjeev Arora
- October 20, FOCS, no lunch
- October 13, Yuval Peres on the Markov type of a metric space
- October 6, James Lee on Euclidean embeddings of negative-type metrics
- September 29, [In 400 Cory] Alistair Sinclair on non-commutative circuits for the determinant
- September 22, John Canny on privacy
- September 15, [In 400 Cory] Shakhar Smorodinsky on locally Delaunay graphs
- September 8, Hoeteck Wee on amplification of hardness for one-way functions
- September 1, Luca Trevisan on hierarchy theorems for probabilistic time (see papers here and here)
Spring 2004 Schedule
- May 19, Cynthia
Dwork on privacy in public databases
- May 12, Hoeteck Wee on obfuscation (talk given by Luca Trevisan)
- May 7, Leonard
Schulman on clustering
- May 5, Frank
McSherry on spectral filtering and Gaussian mixtures
- April 28, Tim Roughgarden
on correlated equilibria
- April 21, [In 400 Cory] Kamal
Jain on price-collecting Steiner forest
- April 14, Kamalika
Chaudhuri on degree-restricted MST
- April 7, Luca Trevisan on
inapproximability results proved using average-case assumptions
- March 31, Andrej Bogdanov
on pseudorandomness against degree-2 adversaries
- March 24, no lunch
- March 15, [In 380 Soda at 1pm], Jordan
Kerenidis on communication complexity
- March 10, Ryan O'Donnell on learning monotone functions
- March 3, Kobbi Nissim on communication
versus computation
- February 25, [In 400 Cory] Nati Linial on
simplicial complexes
- February 18, [In 400 Cory] Arnab Nilim on optimal Markov
decision problems
- February 11, Kris Hildrum
on peer-to-peer networks
- February 4, Scott Aaronson
on the communication complexity of agreement
- January 28, no lunch
- January 21, Baruch
Awerbuch on adaptive routing
Fall 2003 Schedule
-
December 10, Paul
Spirakis
-
December 3, no lunch
-
November 26, Luca Trevisan on
the average-case complexity of k-SAT
-
November 19, [In 400 Cory] Richard
Karp on the min-entropy set-cover problem
-
November 12, Kenji Obata on integral
multicommodity flow
-
November 5, Robert Krauthgamer on
near neighbor search in general metric spaces
-
October 29, [In 380 Soda] Jonathan
Shewchuk on unfolding three-dimensional meshes
-
October 22, James Lee
-
October 15, David Wagner on
security against side channel attacks
-
October 8, David Williamson on
an intranet search problem
-
October 1, Scott Aaronson
on non-uniform BQP versus EXP
-
September 24, Daniele Micciancio
-
September 17, Sridhar Rajagopalan on sorting-based streaming algorithms
-
September 10 [In 400 Cory] Sanjoy Dasgupta
on hierarchical clustering
-
September 3, Christos Papadimitriou
Spring 2003 Schedule
-
May 15, Roded Sharan, on
a fully dynamic algorithm for cographs
-
May 8, Tom Bohman On the Shannon
capacities of the complements of odd cycles
-
May 1, James
Lee
on bounded geometries, fractals, and low-distortion embeddings
-
April 24 [In 373 Soda], Luca Trevisan
on exponential time algorithms for 3SAT and 3-coloring
-
April 17 [In 373 Soda] Dorit
Aharonov
-
April 10 [In 373 Soda] Andrej
Bogdanov
on worst-case to average-case reductions in NP
-
April 3 [In 373 Soda] James
Lee
on a paper
by Oded Regev
-
March 27, no lunch
-
March 20, Elchanan Mossel
on pseudorandom generators in NC0
-
March 13, Luca Trevisan
on a paper
by Impagliazzo and Kabanets
-
March 6, Vladlen Koltun
on open problems in combinatorial geometry
-
February 27, Robert Krauthgamer
on polylogarithmic inapproximability
-
February 20, Eran Halperin
on the intregrality gap of the group steiner tree problem
-
February 13 [In 373 Soda], Muli
Safra
-
February 6, Christos Papadimitriou
-
January 30, Kunal Talwar
on embeddings of general metrics in tree metrics
Fall 2002 Schedule
-
December 4, Robert Krauthgamer
on planar separators
-
November 27, no lunch
-
November 20, Elchanan Mossel
on error correction of random bits
-
November 13, James O'Brien
on an energy driven approach to linkage unfolding
-
November 6, Eran Halperin
on a stocastic process on the hypercube
-
October 30, Luca Trevisan
on amplification of average-case complexity within NP
-
October 23, Dimitris
Achlioptas on random k-SAT
-
October 16 [In 373 Soda], Chris
Harrelson on the k-traveling repairman problem
-
October 9, Satish
Rao on graph separator theorems
-
October 2, James Lee on
embedding graphs into the integer lattice
-
September 25 [In 380 Soda] Luca
Trevisan on testing that a function depends on k variables or less
-
September 18, Jordan Kerenidis
on locally decodable codes
-
September 4, Shakhar Smorodinsky
on
a coloring problem
Spring 2002 Schedule
-
May 9, Jonathan Shewchuk
on duality in computational geometry
-
May 2, Andrej Bogdanov
on property testing of bipartiteness
-
April 25, faculty retreat
-
April 18, Milena Mihail on the spectra of power-law graphs
-
April 11, Amin Saberi on
the complexity of combinatorial auctions
-
April 4, Scott Aaronson
on quantum Fourier sampling
-
March 28, Spring Break
-
March 21, Luca Trevisan
on data compression
-
March 14, Robi Krauthgamer
on property testing of dimensionality
-
March 7, Wim van Dam
on adiabatic quantum computing
-
February 28, Dana Randall
on simulated tempering
-
February 21, Vijay
Vazirani on Trellis Codes
-
February 14, Ziv Bar-Yossef
on communication complexity
-
February 7, Luca Trevisan
on average-case complexity
-
January 31, Eyal Amir on
treewidht approximation
-
January 24, Alistair Sinclair
on random balanced permutations
Fall 2001 Schedule
-
December 13, free lunch, no speaker: we'll wish happy holydays to
each other
-
December 6, Jordan Kerenidis
on collaborative filtering
-
November 29, Satish Rao
on disjoint paths
-
November 22, no lunch, bracing for the turkey dinner
-
November 15, Kenji Obata
on lower bound for property testing [In 373 Soda]
-
November 8, Sivan Toledo
on linear algebraic algorithms
-
November 1, David Wagner
on homomorphic signature schemes
-
October 25, Christos Papadimitriou
on computational game theory
-
October 18, Yuval Rabani
on directed multicuts
-
October 11, Amir Shpilka
on lower bounds for matrix product
-
October 4, Subhash Khot on a
class of two-query PCPs
-
September 27, Luca Trevisan
on sub-linear time MST approximation
-
September 20, Beini Zhou on
Black-box and non-black-box Zero Knowledge
-
September 13, Sanjeev Arora
on the nondeterministic hierarchy theorem.
-
September 6, Venkatesan
Guruswami on hypergraph coloring