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.