### Blogroll

### Archives

- January 2017 (1)
- November 2016 (1)
- July 2016 (2)
- June 2016 (3)
- May 2016 (1)
- June 2012 (3)
- May 2012 (1)
- May 2011 (1)
- March 2011 (1)
- January 2011 (5)
- December 2010 (2)
- November 2010 (2)

### Categories

- Readings (13)
- Research (22)
- Algorithm (9)
- Cryptogaphy (2)
- Game Theory (1)
- Learning Theory (6)
- Optimization (8)

- Story (2)

# Category Archives: Readings

## Spielman-Teng-A: A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Spielman-Teng’s 2004 paper [ST04] on almost-linear Laplacian linear solver has been divided and re-written into three very technically involved ones [ST08a], [ST08b] and [ST08c]. I am planning to write memos for all of them, while this post is the Part … Continue reading

Posted in Algorithm, Readings
Leave a comment

## Spielman-Teng-B: Spectral Sparsification of Graphs (Part II)

Spielman-Teng’s 2004 paper [ST04] on almost-linear Laplacian linear solver has been divided and re-written into three very technically involved papers [ST08a], [ST08b] and [ST08c]. I am planning to write memos for all of them, while this post is the Part … Continue reading

Posted in Algorithm, Readings
Leave a comment

## Spielman-Teng-B: Spectral Sparsification of Graphs (Part I)

Posted in Algorithm, Readings
Leave a comment

## Constant Factor Approximation of Vertex-Cuts in Planar Graphs

There has been a long time I couldn’t remember to write memos for the papers I’ve read, and it’s time for me to come back to this blog, coz my memory is fading all the time and blogging is a … Continue reading

Posted in Algorithm, Readings
Leave a comment

## Learning Algorithms for DT, DNF, AC0 and r-juntas

This is a section of my reading notes to Prof. Ryan O’Donnell’s <Analysis of Boolean Functions>, I’ve summarized the learning algorithms in this post, which also functions as a personal reference. Class Random Examples Membership Queries poly-size DTs Theorem 5 Theorem … Continue reading

Posted in Learning Theory, Readings
Leave a comment

## Almost Perfect Bisection 2

This time I’m going to introduce <A polylogarithmic approximation of the minimum bisection> by Uriel Feige and Robert Krauthgamer. I will transfer my language to minimum bisection rather than maximum bisection, as they two transform to each other for obvious … Continue reading

## Almost Perfect Bisection 1

During the ICS 2011, Yuan Zhou from CMU introduced a new algorithm for finding bisections from an almost bipartite graph. He raised an interesting open question to me, which incentivizes me to go through his paper and two related ones. … Continue reading

Posted in Algorithm, Readings
Leave a comment