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 23th 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.

• N. Bansal.  Constructive algorithms for dsicrepancy minimization, FOCS, pp 3-10, 2010.

• 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 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.

• K. Efremenko.  3-query locally decodable codes of subexponential length, in The 41st ACM Symposium on Theory of Computer STOC, pp 39-44, 2009.

• V. Guruswami and A. Rudra.  Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy, Information Theory, IEEE Transactions on, 54(1):135-150, 2008.

•  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⁰ by Small Height Decision Trees and a Deterministic Algorithm for #AC⁰ -SAT, CCC 2012, to appear.

• R. Impagliazzo, C. Beck and S. Lovett.  Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC⁰ -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⁰ , 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.

• T. Kaufman and M. Sudan.  Algebraic property testing: The role of invariance, pp. 403-412, 2008.

• 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.

• L. Lovász and P. Erdös.  Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, number 11 in Coll. Math. Soc. J. Bolyai, pp 609-627. North Holland, 1975.

•  L. Lovász and M. E. Saks.  Lattices, Möbius functions and communication complexity.  In FOCS, pp 81-90, IEEE, 1988.

• 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.

• R. A. Moser and G. Tardos.  A constructive proof of the general Lovász local lemma, J. ACM, 57(2):11:1-11:15, 2010.

• J. Spencer. Six standard deviations suffice, Transactions of the American Mathematical Society, 289(2):679-706, 1985.

• 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.

• P. Winkler and D. Zuckerman.  Multiple cover time, Random Struct. Algorithms 9 (1996), no. 4, 403-411.

• S. Yekhanin. Towards 3-query locally decodable codes of subexponential length, Journal of the ACM, 55:1-16, 2008.