Theory Reading Group
Fall 2009 Schedule
| Recent | Topic / Paper / Presenter |
|
Thursday December 17, 2009 |
Applications of AP3-Free Sets Papers: Noga Alon Testing subgraphs in large graphs. Proc. 42 IEEE FOCS, IEEE (2001), 434-441. Also: Random Structures and Algorithms 21 (2002), 359-370. Noga Alon and Asaf Shapira Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. Theory of Computing Journal, Volume 1, Article 9 (pages 177-216) ACM Symposium on Theory of Computing, pages 1-6, 1987. Presenters: Seeun William Umboh Time and location: TBA Note: This is part 2. William will cover the construction of dense arithmetic progression-free subsets. |
|
Wednesday December 16, 2009 |
Asymmetric Traveling Salesman Problem Paper: N. S. H. Kaplan, M. Lewenstein and M. Sviridenko. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM, pages 602-626, 2005. Presenter: Pratima Kolan 3pm, 4310 CS |
|
Tuesday December 15, 2009 |
Applications of AP3-Free Sets Papers: Noga Alon Testing subgraphs in large graphs. Proc. 42 IEEE FOCS, IEEE (2001), 434-441. Also: Random Structures and Algorithms 21 (2002), 359-370. Noga Alon and Asaf Shapira Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. Theory of Computing Journal, Volume 1, Article 9 (pages 177-216) ACM Symposium on Theory of Computing, pages 1-6, 1987. Presenters: Dalibor Zeleny 5pm, 3310 CS Note: This is part 1. Dalibor will cover the extremal graph and hypergraph constructions, and graph property tester upper bounds. |
|
Thursday December 10, 2009 |
Applications of AP3-Free Sets Paper: Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. ACM Symposium on Theory of Computing, pages 1-6, 1987. Presenters: Matthew Anderson 5pm, 4310 CS Note: This is part 2. |
|
Tuesday December 8, 2009 |
Applications of AP3-Free Sets Paper: Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. ACM Symposium on Theory of Computing, pages 1-6, 1987. Presenters: Sidhharth Barman 5pm, 3310 CS Note: This is part 1. |
|
Wednesday December 2, 2009 |
Applications of AP3-Free Sets Paper: Johan Hastad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms, 22(2): 139-160, 2003. Presenter: Baris Aydinlioglu 5pm, 3310 CS |
|
Monday November 30, 2009 |
Asymmetric Traveling Salesman Problem Paper: M. Blaser. A new approximation algorithm for the asymmetric TSP with triangle inequality. In ACM-SIAM Symposium on Discrete Algorithms, pages 638-645, 2002. Presenter: Balu Sivan 3pm, 4310 CS |
|
Monday November 23, 2009 |
Asymmetric Traveling Salesman Problem Paper: M. Charikar, M. Goemans, and H. Karloff. On the integrality ratio for the asymmetric traveling salesman problem. Mathematics of Operations Research, 31:245-252, 2006. Presenter: David Malec 3pm, 4310 CS |
|
Tuesday November 24, 2009 |
Applications of AP3-Free Sets Paper: Ashok Chandra, Merrick Furst, and Richard Lipton. Multi-party protocols. STOC'83, pages 94-99. Presenter: Balu Sivan 5pm, 3310 CS |
|
Monday November 16, 2009 |
Asymmetric Traveling Salesman Problem Paper: A. M. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12:23-39, 1982. Presenter: Shuchi Chawla 3pm, 4310 CS |