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.