AFLB

From ResearchWiki

Revision as of 19:04, 21 January 2010

The Algorithms For Lunch Bunch

Thursdays at 12:30.

Spring 2010

Jan 8, 2010

• Abstracts of papers accepted to ICS2010. Full versions of the papers is here.
  • Suresh: Computational Complexity and Information Asymmetry in Financial Products. Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge
  • Parasaran: Playing Games without Observing Payoffs (Adam Tauman Kalai, Michal Feldman, and Moshe Tennenholtz)
  • Jeff: Local Algorithms for Finding Interesting Individuals in Large Networks (Mickey Brautbar and Michael Kearns)
  • John: Pan-Private Streaming Algorithms (Cynthia Dwork Moni Naor Toni Pitassi Guy Rothblum Sergey Yekhanin)

Jan14, 2010

Jeff: Combinatorial view of Markov chain Monte Carlo.

Jan 21, 2010

SODA recaps Part I: Parasaran and Jeff

Parasaran

• Finding the Jaccard Median Flavio Chierichetti. Ravi Kumar. Sandeep Pandey. Sergei Vassilvitskii
• A Model of Computation for MapReduce Howard Karloff. Siddharth Suri. Sergei Vassilvitskii

Jeff

Jan 28, 2010

SODA recaps Part II: Suresh and John

Suresh -- Poincare inequalities:

• Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. Alexandr Andoni, T. S. Jayram, and Mihai Pătraşcu
• Towards a Calculus for Non-Linear Spectral Gaps. Manor Mendel and Assaf Naor

John:

• Convergence, Stability, and Discrete Approximation of Laplace Spectra Tamal K. Dey, Pawas Ranjan, and Yusu Wang
• Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures Seth Pettie

Feb 4, 2010

Feb 11, 2010

Fall 2009

Oct 30, 2009

All: Discussion of topics for Spring 2010 Algorithms Seminar on Graph Algorithms

• planarity testing
• advanced MSTs ? randomized MST
• other randomized graph algorithms
• treewidth/pathwidth
• minors
• robertson seymour (in brief)
• Baker decomposition for planar graphs
• Klein-Borradaile results on new decompositions
• shortest paths, matrix mult, new developments
• evasiveness in graph properties, and the topological angle
• Spectral graph theory?

Nov 7, 2009

• John, Raj: Practice talks for FWCG 09
• Parasaran: Geometry of Soft Clusterings

Nov 14, 2009

No AFLB (FWCG 2009)

Nov 21, 2009

Review of FWCG papers:

• Wei Zeng, Rik Sarkar, Feng Luo, Xianfeng Gu, and Jie Gao. Resilient Routing for Sensor Networks Using Hyperbolic Embedding of Universal Covering Space
• Gary L. Miller, Todd Phillips, and Donald R. Sheehy. Approximating Voronoi Diagrams with Voronoi Diagrams

(2 page abstracts here)

Dec 4, 2009

• Graph isomorphism and volumes of convex bodies. Shmuel Friedland. Presented by Christopher Earl

Papers for discussion

• Natural Algorithms (this one might be easier to read) (Chazelle, SODA 09 Best paper)
• A constructive proof of the general Lovasz Local Lemma (Moser, earlier version STOC 09 Best Student Paper)
• Affiliation Networks (Lattanzi, Sivakumar, STOC 09)
• Quantum Proofs for Classical Theorems (Drucker, Wolf)
• Unique games survey (Harb)
• Sorting and Selection with Imprecise Comparisons (Ajtai, Feldman, Hassidim, Nelson, ICALP 09)
• Homology Flows, Cohomology Cuts (Chambers, Erickson and Nayyeri, STOC 09)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Monique Laurent. Mathematics of Operations Research, Vol. 28, No. 3 (May, 2003), pp. 470-496