Monthly Archives: January 2011

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

Posted in Algorithm, Readings | 1 Comment

Course Study Group with Xiaorui Sun

Most people agree that there’s a huge difference between learning by oneself, and learning inside the classroom. The knowledge might be automatically erased from one’s mind if she refuses to do the homework. A month ago, some professor said to … Continue reading

Posted in Story | 2 Comments

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

Review of a course in cryptography – Part 2/2

Continued from the previous post. This second part reviews the commitment scheme, the zero-knowledge, the digital signatures and the lattices. Lecture 15-16: Commitment Schemes A commitment scheme between the sender and the receiver satisfies two security properties: hiding and biding. … Continue reading

Posted in Cryptogaphy, Readings | 2 Comments

Review of a course in cryptography – Part 1/2

Due to two cancellations of my flight, I was trapped in the USA with a lonely X’mas. To cheer me up, I self-learned the lecture notes of 6.875 in MIT, taught by Prof Silvio Micali in 2010. I’m not a … Continue reading

Posted in Cryptogaphy, Readings | Leave a comment