Algorithms Seminar
From ResearchWiki
(Difference between revisions)
(→Participants) |
m (→Participants) |
||
| Line 25: | Line 25: | ||
==Participants== | ==Participants== | ||
| - | |||
* [http://www.cs.utah.edu/~suresh Suresh Venkatasubramanian], Assistant Professor, School of Computing | * [http://www.cs.utah.edu/~suresh Suresh Venkatasubramanian], Assistant Professor, School of Computing | ||
| + | * [http://www.cs.utah.edu/~piyush Piyush Rai], PhD Student, School of Computing | ||
* [http://www.cs.utah.edu/~avishek Avishek Saha], PhD Student, School of Computing | * [http://www.cs.utah.edu/~avishek Avishek Saha], PhD Student, School of Computing | ||
Revision as of 04:53, 26 August 2008
This is the home for the Algorithms Seminar at the School of Computing. For more information on algorithms at the School of Computing, subscribe to algos@cs.utah.edu
Fall 2008: CS 6963: Randomization
Tue-Thu 1045-1205 MEB 3105 Mailing list: cs6963@list.eng.utah.edu
Contents |
Course Materials
- Randomized Algorithms (Motwani and Raghavan) [MoRa]
- Probability and Computing (Mitzenmacher and Upfal) [MiUp]
Seminar format and grading
- Student presentations on material selected by me. Please read, reflect upon, and follow these presentation guidelines
- One week before presentation is scheduled: student meets with me to discuss content of the presentation
- Day before presentation: student submits summary (either notes, or slides for presentation)
- Day before presentation: non-presenters submit questions on the material
- Day after presentation: questions are addressed by presenter or questioner (on the wiki talk page)
* NOTE: Project is now optional, and does not affect grading.
- Grading will be based on
- presentation quality
- notes/summary
- feedback from other students after the presentation
- feedback given to other students (i.e participation in general)
Participants
- Suresh Venkatasubramanian, Assistant Professor, School of Computing
- Piyush Rai, PhD Student, School of Computing
- Avishek Saha, PhD Student, School of Computing
Schedule
| Date | Paper(s) | Presenter | Date | Paper(s) | Presenter |
|---|---|---|---|---|---|
| Algorithms | |||||
| Aug 26 | Introduction and course overview. Chernoff bounds yield provably better results (MoRa 4.2) Notes1 Notes2 | Suresh | Aug 28 | The Probabilistic Method I: examples, and the modification method (MiUp 6.1-6.4 (excluding 6.3) | Piyush |
| Sep 2 | The Probabilistic Method II: the Lovasz Local Lemma | Piyush | Sep 4 | Hashing I (MoRa 8.4.1-4) | Avishek |
| Sep 9 | Hashing II (MoRa 8.5) | Avishek | Sep 11 | Geometry I: Randomized incremental constructions | |
| Sep 16 | Geometry II: Random sampling (MoRa 9.9) | Sep 18 | Randomized Rounding | ||
| Sep 23 | Algebraic fingerprinting (MoRa 7.1,7.2) | Amit | Sep 25 | Pattern Matching (MoRa 7.4-7.6) | Amit |
| Sep 30 | Approximate Counting I (MoRa 6.4-6.6) | Nathan | Oct 2 | Approximate Counting II: MCMC (MoRa 11.1-11.2) | Nathan |
| Randomness and Complexity | |||||
| Oct 7 | Randomized complexity classes: Non-uniform complexity, BPP in P/poly | Avishek | Oct 9 | Where does BPP lie ? The alternating hierarchy and BPP  (lecture 7) | Avishek |
| Oct 21 | Interactive Proofs: IP and PSPACE | Oct 23 | Interactive Proofs: PCP | Scott | |
| Pseudorandomness | |||||
| Oct 28 | Expanders. | Oct 30 | Pseudorandomness via k-wise independence and expanders (two-point sampling example from MoRa 3.4) | ||
| Nov 4 | Pseudorandomness via cryptographic hardness I | Suresh | Nov 6 | Pseudorandomness via cryptographic hardness II | Suresh |
| Analyzing Randomized Algorithms | |||||
| Nov 11 | Beyond Chernoff: Limited, local, and negative dependence | Nov 13 | The method of bounded differences (McDiarmid survey Sec 3) | ||
| Nov 18 | Derandomization: method of conditional expectation, and pessimistic estimators | Nov 20 | Lower bounds: the Yao minimax principle (MoRa 2) (some notes) | ||
| Miscellaneous Topics | |||||
| Nov 25 | Random Graphs I | Piyush | Dec 2 | Random Graphs II | Piyush |
| Dec 4 | Balls and bins: The power of two choices (survey article and a presentation) | Nathan | Dec 9 | Quantum Computing: Bell's inequality (a popular exposition by Michael Nielsen) | Nathan |
| Dec 11 | Algorithmic randomness (parts of Chapter 6) | Suresh | |||
Paper Summaries
- Main article: CS 6963 Summaries
Project Ideas
Analysis
- A taxonomy of tail bounds (given a situation, which tail bounds make sense)
- Review of Talagrand's inequality (I'd recommend picking a basic inequality from Part I and one or two applications from Part II).
- Probabilistic recurrences (the original Karp paper, Karpinski and Zimmerman, Chaudhuri and Dubhashi
Algorithms
- Markov incremental constructions (an extension of randomized incremental constructions)
- Path coupling in Markov chains
- Geometric random walks
- Property testing, and a more recent survey of graph property testing
- Where does randomization give strict improvements ? (volume estimation, communication complexity) (see me for papers)
Complexity
- A review of the natural proofs idea (in elementary form) (Also read Luca's post)
- Hardness vs randomness (nisan-wigderson etc)
- BQP vs BPP
Pseudorandomness
- Classification of expanders, extractors, concentrators and the like (see the second half of Luca's class)
Course Links
- By David Karger@MIT
- By Luca Trevisan@Berkeley
- Gupta+Chawla@CMU
- Complexity theory by Goldreich
- Derandomization by Luby+Wigderson
- Pseudorandomness by Trevisan
- Peter Bro Milterson book chapter on derandomization
Past Semesters
- Fall 2007: Approximate High Dimensional Geometry
- Spring 2008: The Geometry of Information Spaces
