AFLB
From ResearchWiki
The Algorithms For Lunch Bunch
Thursdays at 12:30.
Contents |
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
