Main / Home Page

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

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

- 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

- 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.

Page last modified on January 15, 2015, at 03:55 PM by 1