2010-2011 Papers

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

Theoretical Computer Science

• Y. Afek, N. Alon, O. Barad, N. Barkai, E. Hornstein and Z. Bar-Joseph. A biological solution to a fundamental distributed computing problem, Science, 331(6014), pp. 183-185, (2011).
• N. Alon. A non-linear lower bound for planar epsilon nets, Proceedings of FOCS 2010, pp. 341-346. Also to appear in Discrete and Computational Geometry.
• N. Alon. Multicolored matchings in hypergraphs. Moscow Journal of Combinatorics and Number Theory 1 (2011), pp. 3-10.
• N. Alon and A. Kostochka. Dense uniform hypergraphs have high list chromatic number. Discrete Math., to appear.
• N. Alon and A. Kostochka. Hypergraph list coloring and Euclidean Ramsey Theory. Random Structures and Algorithms, to appear.
• N. Alon and S. Lovett. Weighted families of k-wise independent permutations, submitted.
• N. Alon and P. Pralat. Modular orientations of random and quasi-random regular graphs, Combinatorics, Probability and Computing 20(2011), pp. 321-329.
• N. Alon and S. Lovett. Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions, submitted 2011.
• N. Alon and A. Mehrabian. On a generalization of Meyniel's Conjecture on the Cops and Robbers Game. Combinatorics 18 (2011), pp. 19-26.
• P. Beame, R. Impagliazzo and S. Srinivasan. Approximating AC^0 circuits by small height decision tree, preprint 2011.
• B. Barak, Z. Dvir, A. Wigderson and A. Yehudayoff. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. Proceedings of STOC 2011, to appear.
• P. Beame and W. Machmouchi. Making branching programs oblivious requires super-polynomial overhead. ECCC TR10-104 (2010); also to appear in Proceedings of CCC 2011.
• E. Ben-Sasson and R. Impagliazzo. Random CNFs are Hard for the Polynomial Calculus. Computational Complexity 19(4): 501-519 (2010).
• E. Bombieri and S. Kopparty. List-decoding multiplicity codes, in preparation, 2011.
• C. Calabro, R. Impagliazzo and R. Paturi. On the Exact Complexity of Evaluating Quantified k-CNF. IPEC 2010, pp. 50-59.
• J. Bourgain and L. Guth. Bounds on oscillatory integral operators based on multilinear estimates, arXiv:1012-3760, to appear in GAFA
• A. Chattopadhyay and S. Lovett. Linear systems over finite abelian groups. Proceedings of CCC 2011, to appear.
• D. Chebikin and R. Ehrenborg. The f-vector of the descent polytope, Discrete and Computational Geometry, 45(2011): 410-424.
• S. Chien, P. Harsha, A. Sinclair and S. Srinivasan. Almost Settling the Hardness of the Noncommutative Determinant, Proceedings of STOC 2011, to appear.
• I. Diakonikolas, R. O'Donnell, R. Servedio and Y. Wu. Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions, SODA 2011.
• Z. Dvir, A. Rao, A. Wigderson and A. Yehudayoff. Restricted access, submitted.
• R. Ehrenborg, S. Kitaev and P. Perry. A spectral approach to pattern-avoiding permutations, arXiv:1009.2119, submitted 2011.
• R. Ehrenborg and J. Jung. Descent pattern avoidance, preprint 2011.
• R. Ehrenborg. The cubical matching complex, preprint 2011.
• R. Ehrenborg and M. Readdy. The cd-index of balanced and Bruhat graphs, preprint 2011.
• M. Gromov and L. Guth. Generalizaitons of the Kolmogorov-Barzdin embedding estimates, arXiv:1103-3423; submitted 2011
• L. Guth and N. Katz. On the Erdos distinct distance problem in the plane, arXiv:1011.4105; submitted 2011
• A. Hasson, M. Kojman and A. Onshuus. On symmetric indivisibility of countable structures, preprint 2011.
• H. Hatami and S. Lovett. Correlation testing of the Affine Invariant properties on F^n_p in the high error regime, Proceedings of STOC 2011.
• H. Hatami and S. Lovett. Higher-order Fourier analysis of F^n_p and the complexity of systems of linear forms. Geometric and Functional Analysis, to appear.
• P. Hrubes, A. Wigderson and A. Yehudayoff. An asymptotic bound on integer sums of squares. Canadian Journal of Math., to appear.
• 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. Relativized Separation of Worst-Case and Average-Case Complexity for NP, Computational Complexity, to appear June 2011.
• M. Kojman. Shelah's revised gch and a question by Alon, preprint 2011.
• S. Kopparty. On the complexity of powering in finite fields, Proceedings of STOC 2011, to appear.
• S. Kopparty, S. Saraf and S. Yekhanin. High-rate codes 2ith sublinear-time decoding, Proceedings of STOC 2011, to appear.
• D. Milovich, M. Kojman and S. Spadaro. Order-theoretic properties of bases in topological spaces, submitted.
• G. Kindler, R. O'Donnell, A. Rao and A. Wigderson. Spherical cubes: optimal foams from computational hardness amplification, submitted.
• G. Kun, R. O'Donnell and Y. Zhou. Linear programming robustly decides width-1 CSPs, manuscript.
• A. Moitra and R. O'Donnell. Pareto optimal solutions for smoothed analysts, Symposium on Theory of Computation, 2011.
• S. Lovett and E. Viola. Bounded-depth circuits cannot sample good codes, Proceedings of CCC 2011, to appear.
• S. Lovett and S. Srinivasan. Correlation bounds for poly-size AC^0 circuits with InI^(1-o(1)) symmetric gates, submitted.
• R. O'Donnell. Analysis of Boolean Functions, manuscript.
• R. O'Donnell and K. Wimmer. Sharpness of KKL on Schreier graphs, submitted.
• R. O'Donnell, J. Wright and Y. Zhou. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions, Proceedings of ICALP 2011, to appear.
• R. O'Donnell, Y. Wu and Y. Zhou. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups, Proceedings of CCC 2011, to appear.
• M. Readdy. Enumerative and asymptotic analysis of a moduli space, arXiv:1009.4938v2, to appear in Advances in Applied Math.
• N. Srivastava and R. Vershynin. Covariance Estimation for Distributions with 2+\varepsilon Moments. arXiv1106.2775v1; submitted.