2017-2018 Papers

This page contains links to some papers produced during the academic year of 2017-2018.

Theoretical Computer Science

• Z. Allen Zhu, A. Garg, Y. Li, R. Oliveira, A. Wigderson. Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing. STOC 2018, 172-181.

• Z. Allen Zhu, Y. Li, R. Oliveira, A. Wigderson. Much Faster Algorithms for Matrix Scaling. FOCS 2017: 890-901.

• N. Alon, M. Babaio , Y. A. Gonczarowski, Y. Mansour, S. Moran, A. Yehudayoff. Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues. NIPS 2017. Spotlight presentation (about 3.5% of submissions).

• N. Alon, R. Livni, M. Malliaris, S. Moran. Private PAC Learning Implies Finite Littlestone Dimension. Work in progress, 2018.

• A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Data-dependent hashing via nonlinear spectral gaps. STOC 2018: 787-800.

• A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Locality sensitive hashing via nonlinear spectral gaps. To appear in STOC 2018.

• A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Holder homeomorphisms and approximate nearest neighbors. Submitted to FOCS 2018.

• S. Arora, N. Cohen, E. Hazan. On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. ICML 2018.

• S. Arora, R. Ge, B. Neyshabur, Y. Zhang. Stronger Generalization Bounds for Deep Nets via a Compression Approach. ICML 2018.

• S. Arora, W. Hu, P. Kothari. An Analysis of the t-SNE Algorithm for Data Visualization. ArXiv preprint 1803.0768v2.

• S. Arora, M. Khodak, N. Saunshi, K. Vodrahalli. A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs. ICML 2018.

• S. Arora, A. Risteski, Y. Zhang. Do GANs learn the distribution? Some Theory and Empirics. ICLR 2018.

• M. Babaio , Y. A. Gonczarowski, Y. Mansour, S. Moran. Are two (samples) really better than one? On the non-asymptotic performance of empirical revenue maximization. ArXiv preprint 1802.08037.

• B. Barak, Z. Brakerski, I. Komargodski, P. Kothari. Limits on low-degree pseudorandom generators (or: Sum-of-squares meets program obfuscation). EUROCRYPT 2018.

• R. Bassily, S. Moran, I. Nachum, J. Shafer, A. Yehudayoff. Learners that use little information. ALT 2018: 25-55.

• P. Beame, N. Fleming, R. Impagliazzo, A. Kolokolova, D. Pankratov, T. Pitassi, R. Robere. Stabbing Planes. ITCS 2018, 10:1-10:20.

• A. Ben-Aroya, E. Chattopadhyay, D. Doron, X. Li, A. Ta-Shma. A new approach for constructing low-error, two-source extractors. CCC 2018, 3:1-3:19.

• S. Ben-David, P. Hrubes, S. Moran, A. Shpilka, A. Yehudayoff. A learning problem that is independent of the set theory ZFC axioms. CoRR abs/1711.05195 (2017).

• M. Braverman, G. Kol, S. Moran, R. R. Saxena. Convex Set Disjointness. Work in progress, 2018.

• P. Burgisser, C. Franks, A. Garg, R. Oliveira, M. Water, A. Wigderson. Efficient algorithms for tensor scaling, quantum marginals and moment polytopes. FOCS 2018, 883-897

• P. Burgisser, A. Garg, R. Oliveira, M. Walter, A. Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. ITCS 2018, 24:1-24:20.

• P. Burgisser, C. Ikenmeyer, G. Panova. No occurrence obstructions in geometric complexity theory. arXiv:1604.06431v3 .

• E. Chattopadhyay, A. De, R. Servedio. Simple and efficient pseudorandom generators from gaussian processes. ECCC 2018, 18:100.

• E. Chattopadhyay, P. Hatami, K. Hosseini, S. Lovett. Pseudorandom generators from polarizing random walks. CCC 2018, 1:1-1:21.

• E. Chattopadhyay, P. Hatami, O. Reingold, A. Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. STOC 2018.

• E. Chattopadhyay, B. Kanukurthi, S. Lakshmi Bhavana Obattu, S. Sekar. Privacy amplification from non-malleable codes. IACR 2018, 293.

• E. Chattopadhyay, X. Li. Non-malleable extractors and codes in the interleaved split-state model and more. ArXiv preprint 1804.05228.

• Y. Dagan, Y. Filmus, D. Kane, S. Moran. The entropy of lies: playing twenty questions with a liar. CoRR abs/1811.02177 (2018).

• Z. Dvir, Y. Filmus, S. Moran. A Sauer-Shelah-Perles Lemma for Sumsets. Electr. J. Comb. 25(4): P4.38 (2018)

• Z. Dvir, Y. Filmus, S. Moran. An Extension of The Sauer-Shelah-Perles Lemma to Lattices. arXiv:1807.04957v1

• Z. Dvir, S. Gopi, A. Wigderson. Spanoids - an abstraction of spanning structures, and a barrier for LCCs . arXiv:1809.10372v2

• Z. Dvir, S. Moran. A Sauer-Shelah-Perles Lemma for Sumsets. arXiv:1806.05737v2

• Z. Dvir, S. Moran. On the VC dimension of symmetric differences. In preparation, 2018.

• J. Edmonds, V. Medabalimi, T. Pitassi. Hardness of Function Composition for Semantic Read once Branching Programs. CCC2018: 15:1-15:22

• K. Efremenko, A. Garg, R. Oliveira, A. Wigderson. Barriers for Rank Methods in Arithmetic Complexity. ITCS 2018, 1:1-1:19.

• A. Eskenazis, M. Mendel, and A. Naor. Nonpositive curvature is not coarsely universal. arXiv:1808.02179v1.

• N. Fleming, D. Pankratov, T. Pitassi, R. Robere. Random CNFs are Hard for Cutting Planes. arXiv:1703.02469v1.

• A. Garg, L. Gurvits, R. Oliveira, A. Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. GAFA 2018, 28/1: 100-145.

• R. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi, A. Wigderson. Explicit Capacity Approaching Coding for Interactive Communication. IEEE Transactions on Information Theory, 2018 (Early Access) DOI 10.1109/TIT.2018.2829764.

• M. Goos, T. Pitassi, T. Watson. Query to Communication Lifting for BPP. FOCS 2017: 132-143.

• D. M. Kane, R. Livni, S. Moran, A. Yehudayoff. On communication complexity of classification problems. ArXiv preprint 1711.05893.

• D. M. Kane, S. Lovett, S. Moran, J. Zhang. Active Classification with Comparison Queries. FOCS 2017: 355-366.

• D. M. Kane, S. Lovett, S. Moran. Generalized Comparison Trees for Point-location Problems. ICALP 2018.

• D. M. Kane, S. Lovett, S. Moran. Near-optimal Linear Decision Trees for k-SUM and Related Problems. STOC 2018.

• S. Khot and A. Naor. The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. Preprint, 2018.

• A. Klivans, P. Kothari, R. Meka. Efficient algorithms for outlier-robust regression. COLT 2018.

• P. Kothari, R. Mehta. Sum-of-squares meets nash: Lower bounds for finding any equilibrium. STOC 2018.

• P. Kothari, J. Steinhardt. Better agnostic clustering via relaxed tensor norms. STOC 2018.

• P. Kothari, D. Steurer. Outlier-robust moment estimation via sum-of-squares. STOC 2018.

• Y. Levine, O. Sharir, N. Cohen, A. Shashua. Bridging Many-Body Quantum Physics and Deep Learning via Tensor Networks. ArXiv preprint 1803.09780v2.

• D. Madras, E. Creager, T. Pitassi, R. Zemel. Learning Adversarially Fair and Transferrable Representations. ICML 2018.

• D. Madras, T. Pitassi, R. Zemel. Predicting Responsibly: Increasing Fairness by Learning to Defer. Submitted NIPS 2018.

• O. Meir, A. Wigderson. Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. ECCC 2017, 17:149.

• S. Melczer, G. Panova, R. Pemantle. Counting partitions inside a rectangle. arXiv:1805.08375v3 .

• A. Morales, I. Pak, G. Panova. Asymptotics of principal evaluations of Schubert polynomials for layered permutations. arXiv:1805.04341v1.

• A.H. Morales, I. Pak, G. Panova. Asymptotics of the number of Standard Young Tableaux of skew shape. Europ. J. Comb. 2018 70: 26-49.

• A.H. Morales, I. Pak, G. Panova. Hook formulas for skew shapes III. Multivariate and product formulas. ArXiv 1707.00931v2.

• S. Moran, A. Yehudayoff. On weak epsilon-nets and the Radon number. ArXiv 1707.05381v3.

• A. Naor. Metric dimension reduction: A snapshot of the Ribe program. To appear in Proceedings of the 2018 International Congress of Mathematicians, 2018.

• A. Naor. On the vector-valued law of large numbers for Markov chains with a spectral gap. Preprint, 2018.

• A. Naor. Separating decompositions in high dimensions, extremal hyperplane projections, and Lipschitz extension. Preprint, 2018.

• A. Naor and P. Youssef. Refined restricted invertibility. Preprint, 2018.

• B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, N. Srebro. Towards Understanding the Role of Over-Parameterization in Generalization of Neural Networks. arXiv:1805.12076v1.

• I. Pak, G. Panova, D. Yeliussizov. Bounds on the largest Kronecker and induced multiplicities of nite groups. ArXiv 1804.04683v1.

• I. Pak, G. Panova, D. Yeliussizov. On the largest Kronecker and Littlewood-Richardson coefcients. ArXiv 1804.04693v2.

• T. Pitassi, R. Robere. Lifting Nullstellensatz to Monotone Span Programs over any Field. STOC 2018: 1207-1219.

• A. Wigderson. On the nature of the Theory of Computation (ToC). ECCC 2018, 18:72.