CS 7530 Randomized Algorithms - Projects

Spring 2010

[Main Page] [Lectures]

 

Schedule of presentations:

  1. Thursday April 22:
    1. Alessio Guerrieri - Fast FAST (Feedback Arc Set in Tournaments) [Alon-Lokshtanov-Saurabh]
    2. Geoffroy Chambre - Applications of Bloom filters [Broder,Mitzenmacher]
    3. Charlie Morn -- Simulated annealing for faster volume computation [Lovasz,Vempala]
  2. Tuesday April 27
    1. Akash Kumar: - Randomized algorithm for primality testing via fingerprinting of polynomials [Agarwal,Biswas]
    2. Romain Jobredeaux - Deterministic algorithm for primality testing [Agarwal,Kayal,Saxena]
    3. Pramod Gupta - Concentration inequalities beyond Chernoff bounds
  3. Thursday April 29
    1. Matthew Kennedy - Improved power of 2 choices with "Always go left" [Vocking]
    2. Geoffroy Gabellec - Random walk algorithm for random k-SAT [Aleknovich/Ben-Sasson]
    3. Samuel Papin - A new generic algorithm for hard knapsacks [Howgrave-Graham,Joux]
  4. Tuesday May 4, 3-4:30pm.
    (Note, this is during finals week. This is the allotted time for our final exam.)
    1. Akshay Gupte - Approximate Graph Coloring by Semidefinite Programming [Karger,Motwani,Sudan]
    2. Abhinav Shantanam - Random Sampling of 3-colourings in Z^2 [Goldberg,Martin,Paterson]
    3. Rajiv Iyer - The Small-World Phenomenon: An Algorithmic Perspective [Kleinberg]
Each presentation will be at most 25 minutes, and needs to be via a laptop/computer,
so you'll need to use powerpoint, LaTex, or some equivalent program.

The paper has to use randomness in some way, but otherwise there are no restrictions.
It should be on a topic you are interested in. Come to talk
to me if you'd like my help in figuring out an appropriate paper.
Once you've decided on a paper, email me your choice.

In the last homework you will write a few pages of lecture notes on the details of the main result in your paper choice.
This will help get you ready for your presentation.