2009-2010 Papers

This page contains links to some papers produced during the academic year of 2009-2010.

Theoretical Computer Science

• Z. Dvir. On matrix rigidity and locally self-correctable codes, IEEE Conference on Computational Complexity 2010, pp. 291-298.
• Z. Dvir, P. Gopalan and S. Yekhanin. Matching vector codes, Proceedings of FOCS 2010.
• Z. Dvir and A. Wigderson. Monotone expanders - constructions and applications, ECCC TR09-135, 2009.
• P. Hrubes and A. Yehudayoff. Arithmetic complexity in algebraic extensions. Submitted, 2010.
• P. Hrubes and A. Yehudayoff. Homogeneous formulas and symmetric polynomials, arXiv:0707.2621v1, 2009.
• P. Hrubes and A. Yehudayoff. Monotone separations for constant degree polynomials. Submitted, 2010.
• P. Hrubes, A. Wigderson and A. Yehudayoff. An asymptotic bound on integer sums of squares. Submitted, 2010.
• P. Hrubes, A. Wigderson and A. Yehudayoff. Non-commutative circuits and the sum-of-squares problem, Proceedings of STOC 2010, pp. 667-676.
• P. Hrubes, A. Wigderson and A. Yehudayoff. Relationless completeness and separations, IEEE Conference on Computational Complexity 2010, pp. 280-290.
• R. Impagliazzo and V. Kabanets. Constructive Proofs of Concentration Bounds. Proceedings of APPROX-RANDOM 2010, pp. 617-631.
• R. Impagliazzo, V. Kabanets and A. Wigderson. New Direct-Product testers and 2-query PCPs. Proceedings of STOC 2009, pp. 131-140.
• R. Impagliazzo, R. Jaiswal, V. Kabanets and A. Wigderson. Uniform direct-product theorems: Simplified, optimized, and derandomized, SIAM Journal on Computing 39(4):1637-1665, 2010.
• R. Impagliazzo and R. Williams. Communication Complexity and Synchronized Clocks, IEEE Conference on Computational Complexity 2010, pp. 259-269.
• P. Beame, R. Impagliazzo, Toniann Pitassi and N. Segerlind. Formula caching in DPLL, TOCT 1(3), 2010.
• A. Kolla. Spectral Algorithms for Unique Games. IEEE Conference on Computational Complexity 2010, pp. 122-130.
• A. Kolla, Y. Makarychev, A. Saberi and S-H. Teng. Subgraph Sparsification and Nealry Optimal Ultrasparsifiers, Proceedings of STOC 2010, pp. 57-66.
• N. Devanur and A. Kolla. Fast online Graph Sparsification for Approximating Vertex Expansion. Submitted, 2010.
• S. Khot and D. Moshkovitz. NP-Hardness of Approximately Solvling Linear Equations over Reals, ECCC TR10-112, 2010.
• D. Moshkovitz. An Alternative Proof of The Schwartz-Zippel Lemma. ECCC TR10-096, 2010.
• A. De, O. Etesami, L. Trevisan and M. Tulsiani. Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM 2010, pp. 504-517.
• A. De, L. Trevisan and M. Tulsiani. Time-space Tradeoffs for Attacks against One-way Functions and PRGs, CRYPTO 2010, pp. 649-665.
• A. Deshpande, K. Varadarajan, M. Tulsiani and N. Vishnoi. Algorithms and Hardness for Subspace Approximation, arXiv:0912.1403.
• V. Guruswami, S. Khot, P. Popat, R. O'Donnell, M. Tulsiani and Y. Wu. SDP Gaps for 2-to-1 and Other Label Cover Variants, ICALP (1) 2010, pp. 617-628.
• A. Kumar, R. Manokaran, M. Tulsiani and N. Vishnoi. On the Optimality of a Class of LP-based Algorithms. arXiv:0912.1776v1.
• P. Raghavendra, D. Steurer and M. Tulsiani. Reductions between expansion problems. Manuscript, 2010.
• M. Braverman, A. Rao, R. Raz and A. Yehudayoff. Pseudorandom generators for regular branching programs. Submitted, 2010.