Algorithms Seminar
From ResearchWiki
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
- Hal Daumé III, Assistant Professor, School of Computing
- Nathan Gilbert, PhD Student, School of Computing
- Arvind Agarwal, PhD Student, School of Computing
- Rob Ricci, PhD Student and Research Staff, School of Computing
- Parasaran Raman, MS Student, School of Computing
- Scott Alfeld, MS Student, School of Computing
- Amit Goyal, PhD Student, School of Computing
- Ruihong Huang, PhD Student, School of Computing
- Jagadeesh Jagarlamudi, 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). Some extra notes and some material on basic Chernoff bounds (also see MoRa 4.1-4.2). This paper (Section 2) proves the lower bound for deterministic oblivious routing in general regular graphs | Suresh | Aug 28 | The Probabilistic Method I: examples, and the modification method (MiUp 6.1-6.4 (excluding 6.3) Luca's Notes | Piyush |
| Sep 2 | The Probabilistic Method II: the Lovasz Local Lemma (MiUp Scan) | Piyush | Sep 4 | Hashing I (MoRa 8.4.0-4) Gupta+Chawla@CMU | Amit |
| Sep 9 | Hashing II (MoRa 8.5) (MiUp 13.3). Extra material for fun: a survey of the use of hashing in high-speed packet processing in networks | Avishek | Sep 11 | Geometry I: Randomized incremental constructions | Suresh |
| Sep 16 | Geometry II: Random sampling (MoRa 9.9) | Parasaran | Sep 18 | Randomized Rounding | Arvind |
| Sep 23 | Algebraic fingerprinting (MoRa 7.1,7.2) | Scott | Sep 25 | Pattern Matching (MoRa 7.4-7.6) Sinclair's Notes | 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 | Avishek | Oct 9 | Where does BPP lie ? BPP in P/poly (Arora Section 7.6), The alternating hierarchy (Arora Chap 5), Boolean Complexity (Arora Chap 6), BPP  : (lecture 7 only) OR (Arora Section 7.7), Fun stuff: Polynomial Hierarchy (PH) collapses | Avishek |
| Oct 21 | Interactive Proofs: IP and PSPACE (8.1-8.3, 8.5 of Arora-Barak) | Parasaran | Oct 23 | Interactive Proofs: PCP (Lecture 1 and the first part of Lecture 2)(An entertaining and even gripping history of the PCP theorem) | Scott |
| Pseudorandomness | |||||
| Oct 28 | Expanders. | Scott | Oct 30 | Pseudorandomness via k-wise independence and expanders (Section 3) and (two-point sampling example from MoRa 3.4) | Jagadeesh |
| Nov 4 | Pseudorandomness via cryptographic hardness I (readings: lecture 5,6,8) | Rob | Nov 6 | Pseudorandomness via cryptographic hardness II (readings: lecture 5,6,8). This handout does a better job of explaining Goldreich-Levin | Suresh |
| Analyzing Randomized Algorithms | |||||
| Nov 11 | Beyond Chernoff: Limited, local, and negative dependence. Dubhashi/Panconesi Chapter 4. Here's Jansson's paper for CH-bounds with limited dependence | Arvind | Nov 13 | The method of bounded differences (McDiarmid survey Sec 3) | |
| Nov 18 | Derandomization: method of conditional expectation, and pessimistic estimators (MoRa 5.6, Raghavan paper on pessimistic estimators) | Ruihong | Nov 20 | Lower bounds: the Yao minimax principle (MoRa 2) (some notes) | Rob |
| Miscellaneous Topics | |||||
| Nov 25 | Random Graphs I (sections 10.1, 10.4-6) | Piyush | Dec 2 | Random Graphs II: The Web Graph | Arvind |
| Dec 4 | Balls and bins: The power of two choices (survey article and a presentation) | Rob | 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
- Derandomizing the Lovasz Local Lemma
- 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
