# 2015-2016 Papers

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

## Theoretical Computer Science

- N. Alon. High girth augmented trees are huge. J. Combinatorial Theory, Ser. A, in press.
- N. Alon. Uniformly discrete forests with poor visibility.
- N. Alon, O. Ben-Eliezer. Local And Global Colorability of Graphs. Discrete Mathematics 339 (2016), 428-442.
- N. Alon, T. Bohman, H. Huang. More on the bipartite decomposition of random graphs. J. Graph Theory, to appear.
- N. Alon, S. Das, R. Glebov, B. Sudakov. Comparable pairs in families of sets. J. Combinatorial Theory, Ser. B 115 (2015), 164-185.
- N. Alon, E. Mossel, R. Pemantle. Corruption Detection on Networks.
- N. Alon, S. Moran, A. Yehudayoff. Sign rank versus VC dimension. COLT 2016: 47-80.
- N. Alon, H. Naves, B. Sudakov. On the maximum quartet distance between phylogenetic trees. Proc. SODA 2016, 2095-2106.
- N. Alon, N. Nisan, R. Raz, O. Weinstein. Welfare Maximization with Limited Interaction. Proc. FOCS 2015, 1499-1512.
- M. Dinitz, G. Kortsarz, R. Raz. Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner. ACM Trans. Algorithms 12(2): 25. 2016.
- M. Forbes, A. Shpilka, I. Tzameret, A. Wigderson. Proof Complexity Lower Bounds from Algebraic Circuit Complexity. ECCC 23: 98. 2016.
- A. Ganor, G. Kol, R. Raz. Exponential Separation of Communication and External Information. STOC 2016: 977-986.
- A. Garg, L. Gurvits, R. Oliveira, A. Wigderson. A deterministic polynomial time algorithm for non-commutative

rational identity testing. Accepted to FOCS 2016. - A. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi, A. Wigderson. Towards Optimal Deterministic Coding for Interactive Communication. Proc. SODA 2016, 1922-1936.
- P. Gopalan, N. Nisan, R. Servedio, K. Talwar, A. Wigderson. Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Proc. ITCS 2016, 59-70.
- P. Gopalan, R. Servedio, A. Tal, A. Wigderson. Degree and Sensitivity: tails of two distributions. Proc. CCC 2016, to appear.
- C. Hall, D. Puder, W. Sawin. Ramanujan Coverings of Graphs. STOC 2016: 533-541.
- P. Hatami. On the Structure of Quintic Polynomials. ArXiv preprint 1510.05334.
- H. Hatami, P. Hatami, Y. Li. A characterization of functions with vanishing averages over products of disjoint sets. Eur. J. Comb. 56: 81-93. 2016.
- H. Hatami, P. Hatami, S. Lovett. General systems of linear forms: Equidistribution and true complexity. Advances in Mathematics, to appear.
- P. Hatami, S. Sachdeva. M. Tulsiani. An arithmetic analogue of Fox’s triangle removal argument. Online J. Analytic Comb. 11. 2016.
- P. Hatami, J. Vondrak. Testing Real-Valued Modularity and Submodularity. submitted.
- Y. Kalai, R. Raz, O. Regev. On the Space Complexity of Linear Programming with Preprocessing. ITCS 2016: 293-300.
- S. Kopparty, O. Meir, N. Ron-Zewi, S. Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. STOC 2016: 202-215.
- M. Magee, D. Puder. Word Measures on Unitary Groups. ArXiv preprint 1509.07374.
- T. Ma, A. Wigderson. Sum-of-Squares Lower Bounds for Sparse PCA. NIPS 2015: 1612-1620.
- S. Moran, A. Shpilka, A. Wigderson, A. Yehudayoff. Teaching and compressing for low VC-dimension. Accepted into Journey Through Discrete Mathematics. A Tribute to Jiri Matousek.
- H. Nguyen. Concentration of distances in Wigner matrices. submitted.
- H. Nguyen, V. Vu. Normal vector of a random hyperplane. ArXiv preprint 1604.04897.
- R. Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. ArXiv preprint 1602.05161.