# 2011-2012 Papers

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

## Theoretical Computer Science

- N. Alon and A. Weinstein. Local Correction of Juntas,
*Information Proc. Letters*112 (2012), 223-226.

- N. Alon and I. Ben-Eliezer. Local Rainbow Colorings,
*J. of Cominatorics*, to appear.

- N. Alon, R. Rubinfeld, S. Vardi and N. Xie. Space-efficient Local Computation Algorithms,
*Proc. of the 23rd Annual ACM-SIAM SODA**2012*, 1132-1139.

- N. Alon and S. Lovett. Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.

- N. Alon, A. Moitra and B. Sudakov. Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications,
*Proc. of the 44th ACM STOC**2012*, to appear.

- N. Alon, A. Shpilka and C. Umans. On Sunflowers and Matrix Multiplication,
*Proc. CCC 12*, to appear.

- J. Bourgain. On the Fourier-Walsh coefficients of the Moebius function,
*Israel J. Math,*to appear.

- J. Bourgain. On the correlation of the Moebius function with rank-one system,
*J. Analys*e, to appear.

- J. Bourgain. Prescribing the binary digits of primes,
*Israel J. Math*, to appear.

- J. Bourgain, S. Konyagin and I. Shparlinski. Character sums and deterministic polynomial root finding in finite fields, in preparation.

- J. Bourgain, M. Garaev, S. Konyagin and I. Shparlinski. On the hidden shifted power problem,
*Siam J. Comp.*, in submission.

- J. Bourgain, A. Kontorovich. On the strong density conjecture for integral Apollonian circle packings, in preparation.

- J. Bourgain. On the Schrödinger maximal function in higher dimension, in preparation.

- J. Bourgain and A. Bulut. Gibbs measure evolution in radial nonlinear wave and Schrödinger equations on the ball,
*CRAS Paris*, to appear.

- J. Bourgain, P. Shao, C. Sogge and X. Yao. On the L
^{p}-resolvent estimates and the density of eigenvalues for compact Riemannian manifolds, Submitted to*Duke J. Math*.

- J. Bourgain. Moment inequalities for trigonometric polynomials with spectrum in curved hyper-surfaces,
*Israel J. Math*, to appear.

- J. Ding, J. R. Lee and Y. Peres. Cover times, blanket times and majorizing measures,
*Annals of Mathematics*175 (2012), 1-63, Preliminary version in*STOC 2011*.

- R. Impagliazzo, M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, A. Magen and T. Pitassi. Toward a Model for Backtracking and Dynamic Programming,
*Computation Complexity*20(4): 679-740 (2011).

- R. Impagliazzo, B. Barak, O. Goldreich, S. Rudich, A. Sahai, S. Vadha and K. Yang. On the (Im)possibility of Obfuscating Programs,
*Journal of the ACM*, Vol. 49, Issue 2, Article 6 (2012).

- R. Impagliazzo, P. Beame and C. Beck. Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space,
*STOC 2012*, pp. 213-232.

- R. Impagliazzo, P. Beame and S. Srinivasan. Approximating AC
^{0}by Small Height Decision Trees and a Deterministic Algorithm for #AC^{0}-SAT,*CCC 2012*, to appear.

- R. Impagliazzo, C. Beck and S. Lovett. Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC
^{0}-circuits,*FOCS 2012*, to appear.

- R. Impagliazzo, J. Buresh-Oppenheim and S. Davis. A Stronger Model of Dynamic Programming Algorithms,
*Algorithmica*, 60(4): 938-968 (2011).

- R. Impagliazzo. Relativized Separation of Worst-Case and Average-Case Complexity for
*N P*,*Computational Complexity '11*, June, 2011, pp. 104-114.

- R. Impagliazzo, W. Matthews, R. Paturi. A satisfiability algorithm for
*AC*,^{0}*SODA 2012*: pp. 961-972.

- R. Impagliazzo, C. Moore and A. Russell. An Entropic Proof of Chang's Inequality,
*arXiv:1205.0263v2*.

- R. Impagliazzo, R. Meka and D. Zuckerman. Pseudorandomness from shrinkage,
*FOCS**2012*, to appear.

- L. Lovász, K. Vesztergombi, C. Borgs, J. Chayes, and V.T. Sós. Convergent sequences of dense graphs ii. multiway cuts and statistical physics,
*Annals of Mathematics*, to appear 2012.

- L. Lovász, H. Hatami and B. Szegedy. Limits of local-global convergent graph sequences,
*manuscript*, 2012.

- L. Lovász and K. Vesztergombi. Nondeterministic graph property testing,
*manuscript*, 2012.

- L. Lovász, T. Hubai, G. Lippner, O. A. Camárena and E. Csoka. Positive graphs,
*manuscript*, 2012.

- S. Lovett, A. Bhowmick and Z. Dvir. New lower bounds for matching vector codes, Submitted 2012.

- S. Lovett, A. Bhattacharyya and E. Fischer. Testing how complexity affine-invariant properties, Submitted 2012.

- S. Lovett, E. Ben-Sasson and N. Zewi. An additive combinatorics approach to the log-rank conjecture in communication complexity, Submitted 2012.

- S. Lovett, Z. Dvir and J. Kollár. Variety evasive sets, Submitted 2012.

- S. Lovett and Z. Dvir. Subspace evasive sets. In
*The 44th ACM Symposium on Theory of Computing**STOC**2012*, to appear.

- S. Lovett, G. Kuperberg and R. Peled. Probabilistic existence of rigid combinatorial objects. In
*The 44th ACM Symposium on Theory of Computing STOC 2012*, to appear.

- S. Lovett and R. Meka. Constructive discrepancy minimization by walking on the edges,
*CoRR***abs/1203.5747**(2012).

- R. Meka, R. Impagliazzo and D. Zuckerman. Pseudorandomness from shrinkage,
*Electronic Colloquium on Computational Complexity*(*ECCC*) 19 (2012), no. 57.

- R. Meka. A ptas for computing the supremum of gaussian processes,
*CoRR***abs/1202.4970**(2012).

- A. Moitra, S. Arora, R. Ge and R. Kannan. Computing a nonnegative matrix factorization - provably. In
*Symposium on Theory of Computing STOC**2012*.

- A. Moitra, S. Arora and R. Ge. Learning topic models -- going beyond svd,
*FOCS**2012*.

- A. Moitra, S. Arora, R. Ge and S. Sachdeva. Provable ica with unknown gaussian noise, and implications for gaussian mixtures and autoencoders,
*manuscript*, 2012.

- A. Moitra, N. Alon and B. Sudakov. Nearly complete graphs decomposable into large induced matchings and their applications. In
*Symposium on Theory of Computing STOC**2012*.

- A. Moitra, A. Kalai and G. Valiant. Disentangling gaussians. In
*Communications of the ACM (CACM), Research Highlights,*February 2012.

- A. Moitra. A singly-exponential time algorithm for computing nonnegative rank,
*manuscript*, 2012.

- A. Wigderson, Z. Dvir, A. Rao and A. Yehudayoff. Restriction access. In
*Proceedings of ITCS (Innovations in Theoretical Computer Science)*, pp 19-33, 2012.

- A. Wigderson and A. Yehudayoff. Population recovery and partial identification,