CS 7530 Randomized Algorithms - Projects
Spring 2010
[Main Page]
[Lectures]
Schedule of presentations:
- Thursday April 22:
-
Alessio Guerrieri
- Fast FAST (Feedback Arc Set in Tournaments) [Alon-Lokshtanov-Saurabh]
-
Geoffroy Chambre -
Applications of Bloom filters [Broder,Mitzenmacher]
-
Charlie Morn --
Simulated annealing for faster volume computation [Lovasz,Vempala]
- Tuesday April 27
-
Akash Kumar: -
Randomized algorithm for primality testing via
fingerprinting of polynomials [Agarwal,Biswas]
-
Romain Jobredeaux -
Deterministic algorithm for primality testing [Agarwal,Kayal,Saxena]
- Pramod Gupta - Concentration inequalities beyond Chernoff bounds
- Thursday April 29
-
Matthew Kennedy -
Improved power of 2 choices with "Always go left" [Vocking]
-
Geoffroy Gabellec -
Random walk algorithm for random k-SAT [Aleknovich/Ben-Sasson]
-
Samuel Papin -
A new generic algorithm for hard knapsacks [Howgrave-Graham,Joux]
- Tuesday May 4, 3-4:30pm.
(Note, this is during finals week. This is
the allotted time for our final exam.)
-
Akshay Gupte -
Approximate Graph Coloring by
Semidefinite Programming [Karger,Motwani,Sudan]
-
Abhinav Shantanam -
Random Sampling of 3-colourings in Z^2 [Goldberg,Martin,Paterson]
-
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.