Theory of Computing Reading Seminar
Fall 2010—Spring 2011

TIME AND PLACE:   Every Wednesday, 9:30am, CoRE 433.

Meetings

DATE LEADER PAPER TITLE
Sep 8, 15 Nikos Hartmut Klauck. "A strong direct product theorem for disjointness." STOC 2010.
Sep 22, 29 Fengming Ryan Williams. "Improving exhaustive search implies superpolynomial lower bounds." STOC 2010.
Oct 6,13 Luke Pascal Koiran. "Arithmetic circuits: the chasm at depth four gets wider." arXiv 2010.
Oct 13, 20, 27 Dev David Steurer, Sanjeev Arora, Boaz Barak. "Subexponential Algorithms for Unique Games and Related Problems." FOCS 2010.
Nov 10, 17; Dec 1, 8 Aritanan Nikhil Bansal, Niv Buchbinder, Joseph (Seffi) Naor. "Towards the Randomized k-Server Conjecture: A Primal-Dual Approach." SODA 2010.
Dec 15, 22; Jan 12, 19 Rajat Nitin Saxena, C. Seshadhri "From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits." FOCS 2010.
Jan 26; Feb 9, 16 Kashyap Sergey Yekhanin. "Locally decodable codes."
Feb 23; Mar 2, 9 Fengming Nitin Saxena, C. Seshadhri "Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter." ECCC 2010.
Mar 30 Nikos Eric Blais, Joshua Brody, Kevin Matulef. "Property Testing Lower Bounds Via Communication Complexity." CCC 2011.
Apr 6, 13, 20 Neil Ankur Moitra. "Efficiently Coding for Interactive Communication." ECCC 2011.
Apr 27; May 4, 13 Luke Maurice Jansen and Rahul Santhanam. "Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth." ICALP 2011.
May 18 Luke Maurice Jansen and Rahul Santhanam. "Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent."

Possible future papers

Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi. "A General Framework for Graph Sparsification." STOC 2011.
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin. "High-rate codes with sublinear-time decoding." ECCC 2010.
Dan Feldman, Michael Langberg. "A Unified Framework for Approximating and Clustering Data," STOC 2011.
Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan. "Almost Settling the Hardness of Noncommutative Determinant." STOC 2011.
Shubhangi Saraf, Ilya Volkovich. "Blackbox Identity Testing for Depth-4 Multilinear Circuits." STOC 2011.
Hartmut Klauck. "On Arthur Merlin Games in Communication Complexity." CCC 2011.
Andrew Drucker, Ronald de Wolf. "Quantum Proofs for Classical Theorems." Survey.

HTML 4.01 Strict