2011-2012 Papers

This page contains 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 J. Fox. Testing perfection is hard.
  • 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. The chromatic number of random Cayley graphs.
  • 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. Analyse, 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 Lp-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 AC0 by Small Height Decision Trees and a Deterministic Algorithm for #AC0 -SAT, CCC 2012, to appear.
  • R. Impagliazzo, C. Beck and S. Lovett. Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0 -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 AC0 , 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, Submitted 2012.