Past Presentations
Fall 2006 |
Spring 2006 |
Fall 2005 |
Spring 2005 |
Fall 2004 |
Spring 2004
|
| Presenter | Date | Time | Topic | Reading Material |
| [Theory Day @ NYU] | 12/08/2006 | ... | ||
| Sam Daitch | 11/17/2006 | 1:00 PM | Solving Linear Systems with Preconditioners | ... |
| Edo Liberty | 11/03/2006 | 1:00 PM | Random Projections with Applications to SVD and Nearest Neighbors |
Approximate Nearest
Neighbors by Indyk and Motwani Efficient Search for Approximate Nearest Neighbors by Kushilevitz et al. |
| Nikhil Srivastava | 10/27/2006 | 1:00 PM | Evolving Sets |
Evolving
sets and mixing by Morris and Peres Generalized Cheeger inequalities... by Montenegro |
|
Lev Reyzin [in AKW 500] |
10/20/2006 | 1:00 PM | Learning Graphs | ... |
| [postponed due to act of God] | 10/13/2006 | 1:00 PM | ||
| Prof. Sekhar Tatikonda | 10/5/2006 | 4:00 PM | Loopy Sum-Product Algorithm and k-SAT | ... |
| Aaron Johnson | 9/29/2006 | 1:00 PM | Onion Routing and Anonymous Communication | ... |
| Presenter | Date | Time | Topic | Reading Material |
| NYU/Columbia Theory Day | April 28, 2006 | |||
| Hong Jiang | April 21, 2006 | 2:30 PM | Recent work on distributed consensus | ... |
| STOC06 Review | April 13, 2006 | 2:30 PM | ||
| Felipe Saint-Jean | April 6, 2006 | 2:30 PM | Rational Secure Computation and Ideal Mechanism Design |
Rational Secure Computation and Ideal Mechanism Design by Izmalkov, Micali, Lepinski. [paper] How to play ANY mental game by Goldreich, Micali, Wigderson |
| Kevin Chang | March 31, 2006 | 2:30 PM | Sparsest Cut | Expander Flows, Geometric Embeddings, and Graph Partitionings by Arora, et al. [paper] |
| Lev Reyzin | March 24, 2006 | 2:30 PM | The Complexity of Go | Go is PSPACE-HARD by Lichtenstein and Sipser |
| N/A | March 17, 2006 | N/A | [Spring Recess] | |
| N/A | March 10, 2006 | N/A | [Spring Recess] | |
| Aaron Johnson | March 3, 2006 | 2:30 PM | Repeated Games and Bounded Rationality | On Bounded Rationality and Computational Complexity [paper] |
| Sam Daitch | February 24, 2006 | 2:30 PM | Unique Games [Conjecture] | ... |
| Tomas Toft | February 17, 2006 | 2:30 PM | Unconditionally Secure Constant-Rounds Multi-Party Computation for Equality, Comparison, Bits and Exponentiation | How to Split a Shared Secret into Shared Bits in Constant-Round [paper] |
| Pradipta Mitra | February 10, 2006 | 2:30 PM | Every 2-CSP Allows Nontrivial Approximation | Every 2-CSP Allows Nontrivial Approximation [paper] |
| Kevin Chang | February 3, 2006 | 2:30 PM | The Ellipsoid Method | ... |
| Nikhil Srivastava | January 27, 2006 | 3:15 PM | IP = PSPACE | ... |
| Patrick Huggins | January 20, 2006 | 2:30 PM | Signal Processing via Linear Programming | ... |
| Presenter | Date | Time | Topic | Reading Material |
| Rocco Servedio | December 2, 2005 | 11:30 AM | Learning Monotone Functions from Random Examples in Polynomial Time | Learning Monotone Functions from Random Examples in Polynomial Time [paper] |
| N/A | November 18, 2005 | N/A | [Fall Recess] | |
| Aleksandr Yampolskiy | November 11, 2005 | 11:30 AM | Spreading Alerts Quietly and the Subgroup Escape Problem | Spreading Alerts Quietly and the Subgroup Escape Problem [paper] |
| Lev Reyzin | November 4, 2005 | 11:30 AM | Boosting | Boosting Overview [paper] |
| Kevin Chang | October 28, 2005 | 11:30 AM | Clustering in Multiple Passes | |
| Pradipta Mitra | October 21, 2005 | 11:30 AM | Clustering in Random Graphs | Spectral Partitioning of Random Graphs [paper] |
| Hong Jiang | October 14, 2005 | 11:30 AM | Self-stabilizing Population Protocols | |
| Aaron Johnson | October 7, 2005 | 11:30 AM | Cross-monotonic Cost Sharing for Combinatorial Problems | Limitations of cross-monotonic cost sharing schemes [paper] |
| Michael Schapira | September 30, 2005 | 12:00 PM | Approximation Algorithms for Combinatorial Auctions |
| Presenter | Date | Time | Topic | Reading Material |
| Moses Charikar | April 28, 2005 | 4:00 PM | Metric Space Embedding | ... |
| Kevin Chang | April 18, 2005 | 4:00 PM | The Space Complexity of Clustering Algorithms for Census Data | Link to paper |
| Stephan Winkler | April 11, 2005 | 4:00 PM | VC dimensions | ... |
| Thorsten Theobald | March 28, 2005 | 4:00 PM | Semidefinite Programming | Web resource |
| SODA review | Feb 28, 2005 | 4:00 PM | ... | ... |
| Alex Yampolskiy | Feb 21, 2005 | 4:00 PM | Number Theory 1 Number Theory 2 | ... |
| Hong Jiang | Feb 14, 2005 | 4:00 PM | Fault tolerant consensus | ... |
| Aaron Johnson | Feb 7, 2005 | 4:00 PM | Game Theory | Web resource |
| Pradipta Mitra | Jan 31, 2005 | 4:00 PM | Intro to PCP | Approximation Algortihms (V. Vazirani): Chap 29. Good for an Intro. |
| Sam Daitch | Jan 24, 2005 | 4:00 PM | Quantum Computing | Tutorials and other useful stuff |
| Kevin Chang | Jan 14, 2005 | 3:30 PM | Communication Complexity | Communication Complexity -- Kushilevitz and Nisan |
| Presenter | Date | Presentation | Reading Material |
| Yitong Yin | Nov 12, 2004 | Applications of Ramsey Theory in Theoretical Computer Science | Citeseer version |
| Alex Yampolskiy | Nov 5, 2004 | A Verifiable Random Function with Short Proofs and Keys | A Verifiable Random Function with Short Proofs and Keys |
| Aaron Johnson | Oct 29, 2004 | Truthful approximation algorithms for winner determination in combinatorial auctions | Mu'alem, Nisan |
| Hong Jiang | Oct 22, 2004 | Obfuscation presentation | On the (Im)possibility of Obfuscating Programs |
| Pradipta Mitra | Oct 8, 2004 | Bandwidth Presentation | Version on Feige's Webpage |
| Kevin Chang | Oct 1, 2004 | Presentation | Algorithmic Aspects of Low-distortion geometric embeddings |
| Mike Fischer | Sep 24, 2004 | Computation in Networks of Passively Mobile Finite-State Sensors | Computation in Networks of Passively Mobile Finite-State Sensors |
| Kevin Chang | April 23, 2004 | Approximating the frequency moments | The space complexity of approximating the frequency moments |
| Hong Jiang | April 16, 2004 | How to Generate and Enchange Secrets | How to Generate and Exchange Secrets |
| Pradipta Mitra | April 9, 2004 | Prolonging the Longest Path | Finding a Path of Superlogarithmic Length |
| Pradipta Mitra | April 2, 2004 | Approximation in the NP-"Soft" world | A Simple Approximation Algorithm for the Weighted Matching Problem |
| Yitong Yin | Mar 26, 2004 | On a network creation game | On a network creation game |
| Jiang Chen | Feb 27, 2004 | Learning Juntas | Learning Juntas |
| Hong Jiang | Feb 9, 2004 | Electronic check systems with resusable refunds | A new electronic check system with reusable refunds |
| Alex Yampolskiy | Feb 2, 2004 | Secure Information Aggregation | SIA: Secure Information Aggregation in Sensor Networks |
| Kevin Chang | Jan 26, 2004 | A polynomial time approximation scheme for geometric TSP | Approx. Schemes for NP-hard geometric optimization problems: a Survey |