# 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.