2006-2007 papers

This page contains links to some papers produced during the academic year of 2006-2007.

Theoretical Computer Science

• N. Ailon, E. Liberty, Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
• M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, Proceedings of the 20th Computational Complexity Conference, 2005, pages 308-322.
• A. Bogdanov, E. Viola, Pseudorandom Bits for Polynomials, Proceedings of the 48th Symposium on Foundations of Computer Science, 2007, pages 41-51.
• A. Borodin, J. Boyar, K. S. Larsen, N. Mirmohammadi, Priority Algorithms for Graph Optimization Problems, Proceedings of the 2nd Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science, vol. 3351, 2005, pages 126-139.
• A. Borodin, D. Cashman, A. Magen, How Well Can Primal-Dual and Local-Ratio Algorithms Perform?, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), 2005, pages 943-955.
• A. Borodin, H. C. Lee, Cluster Based Personalized Search
• A. Borodin, Y. Ye, Priority Algorithms for the Subset-Sum Problem, Proceedings of the 13th Annual Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 4598, 2007, pages 504-514.
• J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar, Hardness of Routing with Congestion in Directed Graphs, Proceedings of the 39th ACM Symposium on Theory of Computing, 2007, pages 165-178.
• J. Chuzhoy, S. Khanna, Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems, Proceedings of the 39th ACM Symposium on Theory of Computing, 2007, pages 179-188.
• Z. Dvir, A. Gabizon, A. Wigderson, Extractors and Rank Extractors for Polynomial Sources, Proceedings of the 48th Symposium on Foundations of Computer Science, 2007, pages 52-62.
• A. Gal, V. Trifonov, On the Correlation Between Parity and Modular Polynomials, Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4162, pages 387-398.
• V. Guruswami, J. Lee, A. Razborov, Almost Euclidean Subspaces of $\ell_1^N$ via Expander Codes, Electronic Colloquium on Computational Complexity, 2007.
• T. Kaufman, S. Litsyn, N. Xie, Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2), Electronic Colloquium on Computational Complexity, 2007.
• T. Kaufman, M. Sudan, Sparse Random Linear Codes are Locally Decodable and Testable, Proceedings of the 48th Symposium on Foundations of Computer Science, 2007, pages 590-600.
• T. Kaufman, M. Sudan, Algebraic Property Testing: The Role of Invariance, Electronic Colloquium on Computational Complexity, 2007.
• N. Kayal, The Complexity of the Annihilating Polynomial
• J. Kelner, E. Nikolova,On the Hardness and Smoothed Complexity of Quasi-concave Minimization, Proceedings of the 48th Symposium on Foundations of Computer Science, 2007, pages 472-482.
• V. Trifonov, An O(log n log log n) Space Algorithm for Undirected ST-connectivity, Proceedings of the 37th ACM Symposium on Theory of Computing, 2005, pages 626-633.
• E. Viola, A. Wigderson, One-way Multi-party Communication Lower Bound for Pointer Jumping with Applications, Proceedings of the 48th Symposium on Foundations of Computer Science, 2007, pages 427-437.
• E. Viola, A. Wigderson, Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols, Proceedings of the 22nd Computational Complexity Conference, 2007, pages 141-154.

Combinatorial Game Theory and Arithmetic Cominatorics

• T. E. Plambeck, A. N. Siegel, Misere quotients for impartial games
• A. Razborov, A product theorem in free groups
• A. N. Siegel, Misere canonical forms of partizan games
• A. N. Siegel, Misere Games and Misere Quotients
• A. N. Siegel, The structure and classification of misere quotients
• E. Viola, Selected results in additive combinatorics: an exposition, Electronic Colloquium on Computational Complexity, 2007