Main / Home Page

Theory Reading Group

Tuesdays 4:00-5:00 pm in Gates 459

Upcoming talks:

• Apr 19, 2011 -- Dan -- Witnessed k-distance by Guibas, Merigot, Morozov

Previous talks:

• Mar 14, 2011 -- Eric -- Fast SDP algorithms for constraint satisfaction problems by Steurer
• Feb 7, 2011 -- Kshipra -- A tight bound on approximating arbitrary metrics by tree metrics by Fakcharoenphol, Rao, Talwar
• Jan 31, 2011 -- Qiqi -- On the Rate of Error Correcting Code
• Jan 19, 2011 -- Semih -- The space complexity of approximating the frequency moments by Alon, Matias, and Szegedy
• Nov 16, 2010 -- Peerapong -- Primal-dual RNC approximation of covering integer programs by Rajagopalan and Vazirani.
• Nov 2, 2010 -- Mike -- Margulis expanders
• Oct 5, 2010 -- Ian -- Undirected connectivity in log-space by Reingold
• May 27, 2010 -- Qiqi -- A Combinatorial, Primal-Dual approach to Semidefinite Programs by Arora and Kale
• May 20, 2010 -- Shipra -- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming by Laurent
• May 13, 2010 -- Michael -- Cost-Distance: Two Metric Network Design by Meyerson, Munagala, and Plotkin
• May 6, 2010 -- Rajendra -- A Geometric Approach to Lower Bounds for Approximate Near Neighbor Search by Panigrahy, Talwar and Wieder, FOCS 08
• Apr 29, 2010 -- Kshipra -- PRIMES is in P by Agrawal, Kayel, and Saxena, 2002
• Apr 15, 2010 -- Aneesh -- Locality-sensitive hashing by Gionis, Indyk and Motwani, VLDB 99
• Mar 12, 2010 -- Dan -- Applying Parallel Computation Algorithms in the Design of Serial Algorithms by Nimrod Megiddo
• Mar 5, 2010 -- Florian -- Differential Privacy: A survey of results by Cynthia Dwork
• Feb 26, 2010 -- Pranav -- The geometry of graphs and some of its algorithmic applications, Linial, London, Rabinovich
• Feb 19, 2010 -- Ian -- Expander Flows, Geometric Embeddings, and Graph Partitioning, Arora, Rao, Vazirani, STOC 2004.
• Feb 12, 2010 -- Ananth -- Fully Homomorphic Encryption using Ideal Lattices, Craig Gentry, STOC 2009.
• Feb 5, 2010 -- Shaddin -- useful but generally unknown facts about combinatorial optimization
• Jan 22, 2010 -- Kshipra -- Goemans-Williamson MAX-CUT algorithm: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming by Goemans and Williamson, JACM 1995 / .879-approximation algorithms for MAX CUT and MAX 2SAT STOC 1994
• Nov 30, 2009 -- Peerapong -- Assembling approximately optimal binary search trees efficiently using arithmetics by Kujala
• Nov 16, 2009 -- Qiqi -- The incompressibility method.
• Nov 2, 2009 -- Pranav -- Trust Networks & Structural Balance Theory. From Networks, Crowds, and Markets: Reasoning About a Highly Connected World by Easley and Kleinberg.
• Oct 19, 2009 -- Shipra -- Market Equilibrium via a Primal-Dual-Type Algorithm by Devanur, Papadimitriou, Saberi, Vazirani, FOCS 02.
• Oct 5, 2009 -- Ian -- A constructive proof of the Lovasz Local Lemma by Moser, STOC 09 best paper & A constructive proof of the general Lovasz Local Lemma by Moser and Tardos
• May 21, 2009 -- Shaddin -- Approximating Submodular Functions Everywhere by Goemans, Harvey, Iwata and Mirrokni, SODA 09
• May 14, 2009 -- Shipra -- Matroids, secretary problems, and online mechanisms by Moshe Babaioff, Nicole Immorlica, Robert Kleinberg, SODA 2007
• Apr 16, 2009 -- Pranav -- Online story scheduling in web advertising by Dasgupta, Ghosh, Nazerzadeh, Raghavan, SODA 2009
• Apr 8, 2009 -- Rajendra -- Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform by Nir Ailon and Bernard Chazelle, STOC 2006
• Mar 4, 2009 -- Mukund -- The expected utility theorem.
• Feb 25, 2009 -- Aneesh -- Perfect Matchings in \~O(n^{1.5}) Time in Regular Bipartite Graphs by Ashish Goel and Sanjeev Khanna, under submission.
• Feb 18, 2009 -- Ian -- Algorithmic Barriers from Phase Transitions by Dimitris Achlioptas, Amin Coja-Oghlan, FOCS 2008
• Feb 4, 2009 -- Kshipra -- Optimal mechanism design and money burning by Jason Hartline, Tim Roughgarden, STOC 2008
• Jan 28, 2009 -- Michael -- Expanders via random spanning trees by Navin Goyal, Louis Rademacher and Santosh Vempala
• Jan 14, 2009 -- Pranav -- Approximation algorithms for budgeted learning problems by Sudipto Guha, Kamesh Munagala, STOC 2007
• Dec 3, 2008 -- Bahman -- AdWords and generalized online matching by Mehta, Saberi, Vazirani, Vazirani, FOCS 2005
• Nov 19, 2008 -- Shipra -- Maximizing non-monotone submodular functions by Uriel Feige, Vahab Mirrokni and Jan Vondrak , FOCS 2007

General Notes

• Suggested papers/topics -- feel free to add any papers you find interesting.
• Join the cs-theory-rg mailing list to hear about upcoming talks
• Ian Post (i*t*p at stanford period edu) organizes the reading group
• This is a collaborative Wiki that anyone can edit! Here are help pages to get you started:
  • Basic Editing describes how to create pages in PmWiki.
  • Practice editing pages in the WikiSandbox.