2014-2015 Papers

This page contains links to some papers produced during the academic year of 2014-2015.

Theoretical Computer Science

• E. Abbe, N. Alon, A. S. Bandeira. Linear Boolean classification, coding and "the critical problem". ISIT 2014. 1231-1235.
• E. Abbe, A. Shpilka, A. Wigderson. Reed-Muller codes for random erasures and errors. STOC 2015. 297-306.
• N. Alon. Approximating sparse binary matrices in the cut-norm.
• N. Alon. Problems and results in extremal combinatorics - III.
• N. Alon. Size and degree anti-Ramsey numbers.
• N. Alon, T. Bohman, H. Huang. More on the bipartite decomposition of random graphs.
• N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, O. Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. ArXiv preprint 1409.8428. 2014.
• N. Alon, S. Das, R. Glebov, B. Sudakov. Comparable pairs in families of sets. J. Combinatorial Theory Ser. B, to appear.
• N. Alon, O. B. Eliezer. Local and global colorability of graphs. ArXiv preprint 1410.6236. 2014.
• N. Alon, A. Kostochka, B. Reiniger, D. B. West, X. Zhu. Coloring, sparseness, and girth. Israel J. Mathematics, accepted.
• N. Alon, S. Moran, A. Yehudayoff. Sign rank, VC dimension and spectral gaps. ECCC 21:135. 2014.
• N. Alon, N. Nisan, R. Raz, O. Weinstein. Welfare maximization with limited interaction. ECCC 22:54. 2015.
• N. Alon, C. Shikhelman. Many T copies in H-free graphs. ArXiv preprint 1409.4192. 2014.
• A. Ambainis, Y. Filmus, F. Le Gall. Fast matrix multiplication: Limitations of the laser method. STOC 2015. 585-593.
• F. Ba Baee, J. Huh. A tropical approach to the strongly positive hodge conjecture. ArXiv preprint 1502.00299. 2015.
• X. Chen, A. De, R. A. Servedio, L. Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. STOC 2015. 519-528.
• A. De. Beyond the central limit theorem: asymptotic expansions and pseudorandomness for combinatorial sums. ECCC 21:125. 2014.
• A. De, I. Diakonikolas, R. A. Servedio. Inverse problems in approximate uniform generation. SODA 2015.
• Y. Filmus. Friedgut-Kalai-Naor theorem for slices of the Boolean cube. ArXiv preprint 1410.7834. 2015.
• Y. Filmus. Orthogonal basis for functions over a slice of the Boolean hypercube. ArXiv preprint 1406.0142. 2014.
• Y. Filmlus, G. Kindler, E. Mossel, K. Wimmer. Invariance principle of the slice. ArXiv preprint 1504.01689. 2015.
• M. Forbes. Deterministic divisibility testing via shifted partial derivatives. FOCS 2015.
• M. Forbes, V. Guruswami. Dimension expanders via rank condensers. ArXiv 1411.7455. 2014.
• A. Ganor, G. Kol, R. Raz. Exponential separation of information and communication. FOCS 2014. 176-185.
• A. Ganor, G. Kol, R. Raz. Exponential separation of information and communication for Boolean functions. STOC 2015. 557-566.
• A. Ganor, G. Kol, R. Raz. Exponential separation of communication and external information. ECCC 22:88. 2015.
• O. Golreich, E. Viola, A. Wigderson. On randomness extraction in AC0. CCC 2015. 601-668.
• K. Golubev, O. Parzanchevski. Spectrum and combinatorics of Ramanujan triangle complexes. ArXiv preprint 1406.6666. 2014.
• C. Hall, D. Puder, W. Swain. Ramanujan Coverings of Graphs. ArXiv preprint 1506.02335. 2015.
• S. Kopparty, O. Meir, N. Ron-Zewi, S. Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. ArXiv preprint 1504.05653. 2015.
• R. Meka, A. Potechin, A. Wigderson. Sum-of-squares lower bounds for planted clique. STOC 2015. 87-96.
• S. Moran, A. Shpilka, A. Wigderson, A. Yehudayoff. Teaching and compressing for low VC-dimension. ArXiv preprint 1502.06187. 2015.
• O. Parzanchevski. Mixing in high-dimensional expanders. ArXiv 1310.6477. 2013.
• O. Parzanchevski, R. Rosenthal, R. J. Tessler. Isoperimetric inequalities in simplicial complexes. Combinatorica Feb. 2015.
• D. Puder. Expansion of random graphs: new proofs, new results. ArXiv 1212.5216. 2014.
• D. Puder, O. Parzanchevski. Measure preserving words are primitive. Journal of the American Mathematical Society. Vol. 28, No. 1. pp. 63-97. 2015.
• E. Ben-Sasson, I. Ben-Tov, I. Damgard, Y. Ishai, N. Ron-Zewi. On public key encryption from noisy codewords. ECCC 22:94. 2015.