### 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: Algorithm

## SVD and Eigenvectors for Big Data

People generally believe that a PC can handle SVD for matrices only up to thousands by thousands. Textbooks also suggest that it is not wise to compute singular vectors one by one. In this post, I’ll refute both statements. In particular, … Continue reading

Posted in Algorithm, Optimization
Leave a comment

## Faster Than SGD 1: Variance Reduction

SGD is well-known for large-scale optimization. In my mind, there are two (and only two) fundamental improvements since the original introduction of SGD: (1) variance reduction, and (2) acceleration. In this guest post at Princeton’s OptiML group, I’d love to conduct … Continue reading

Posted in Algorithm, Learning Theory, Optimization
Leave a comment

## Faster Comp-Geometry via Optimization

If one wants to compute the minimum enclosing ball (MinEB) of a set of points, would you believe that the running time can be improved by a significant factor if we randomly rotate the space? While seemingly very counter-intuitive because a … Continue reading

Posted in Algorithm, Optimization
Leave a comment

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