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