2016-2017 Papers

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

Theoretical Computer Science

• N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, T. Ma. Finding Approximate Local Minima Faster Than Gradient Descent. STOC 2017: 1195-1199.
• Z. Allen-Zhu. Katyusha: The First Direct Acceleration of Stochastic Gradient Methods. STOC 2017: 1200-1205.
• Z. Allen-Zhu. Natasha: Faster Stochastic Non-Convex Optimization via Strongly Non-Convex Parameter. ICML 2017, 70:89-97.
• Z. Allen-Zhu, Y. Li. Follow the Compressed Leader: Faster Algorithm for Matrix Multiplicative Weight Updates. ICML 2017, 70:116-125.
• Z. Allen-Zhu, Y. Li. Faster Principal Component Regression and Stable Matrix Chebyshev Approximation. ICML 2017, 70:107-115.
• Z. Allen-Zhu, Y. Li. First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate. FOCS 2017.
• Z. Allen-Zhu, Y. Li. Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition. ICML 2017, 70:98-106.
• Z. Allen-Zhu, Y. Li. LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain. In NIPS, 2016.
• Z. Allen-Zhu, Y. Li, R. Oliveira, A. Wigderson. Much Faster Algorithms for Matrix Scaling. FOCS 2017.
• Z. Allen-Zhu, Y. Li, A. Singh, Y. Wang. Near-Optimal Design of Experiments via Regret Minimization. ICML 2017, 70:126-135.
• N. Alon, M. Braverman, K. Efremenko, R. Gelles, B. Haeupler. Reliable Communication over Highly Connected Noisy Networks. Distributed Computing, accepted.
• I. Ashlagi, M. Braverman, Y. Kanoria, P. Shi. Communication Requirements and Informative Signaling in Matching Markets. EC 2017: 263.
• B. Barak, P. Kothari, D. Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. STOC 2017: 975-988.
• S. Basu, O. Raz. An o-minimal Szemerédi-Trotter theorem. ArXiv preprint 1611.07362.
• S. David, P. Hatami, A. Tal. Low-Sensitivity Functions from Unambiguous Certificates. ITCS 2017.
• A. Bhattacharyya, S. Gopi, and A. Tal. Lower bounds for 2-query LCCs over large alphabet. RANDOM 2017.
• M. Braverman, Y. Kun Ko. Information value of the game. Preprint.
• M. Braverman, Y. Kun Ko, A. Rubinstein, O. Weinstein. ETH Hardness for Densest-k-Subgraph with Perfect Completeness. SODA 2017: 1326-1341.
• M. Braverman, J. Mao, J. Schneider, M. Weinberg. Multi-armed Bandit Problems with Strategic Arms. ArXiv preprint 1706.09060.
• M. Braverman, J. Mao, M. Weinberg. On Simultaneous Two-player Combinatorial Auctions. ArXiv preprint 1704.03547.
• E. Chattopadhya, X. Li. Non-malleable codes and extractors for small-depth circuits, and affine functions. STOC 2017: 1171-1184.
• A. Garg, L. Gurvits, R. Oliveira, A. Wigderson. A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. FOCS 2016: 109-117.
• A. Garg, L. Gurvits, R. Oliveira, A. Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. STOC 2017: 397-409.
• S. Garg, R. Raz, A. Tal. Extractor-Based Time-Space Lower Bounds for Learning. ECCC 2017, 24:121.
• D. Gavinsky, O. Meir. O. Weinstein. A. Wigderson. Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. SICOMP 2017: ISSN (online): 1095-7111.
• D. Gavinsky, O. Meir. O. Weinstein. A. Wigderson. Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comp. 2017 46(1):114-131.
• R. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi. Explicit Capacity Approaching Coding for Interactive Communication. Accepted into IEEE Transactions on Information Theory, 2017.
• P. Gopalan, R. Servedio, A. Wigderson. Degree and Sensitivity: tails of two distributions. CCC 2016, 13:1-13:23.
• P. Hatami, A. Tal. Pseudorandom Generators for Low-Sensitivity Functions. ECCC 2017, 24:25.
• G. Kol, R. Raz, A. Tal. Time-Space Hardness of Learning Sparse Parities. STOC 2017: 1067-1080.
• S. Lovett, A. Tal, J. Zhang. Robust Sensitivity. ECCC 2016, 23:161.
• A. Potechin. A Note on Amortized Branching Program Complexity. CCC 2017, 4:1-4:12.
• A. Potechin. A note on amortized space complexity. Accepted into CCC 2017.
• A. Potechin, D. Steurer. Exact tensor completion with sum-of-squares. ArXiv preprint 1702.06237.
• A. Potechin, L. Yang. A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation. ArXiv preprint 1709.03198.
• R. Raz. A Time-Space Lower Bound for a Large Class of Learning Problems. ECCC 2017, 24:20.
• R. Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. ArXiv preprint 1602.05161.
• T. Schramm, D. Steurer. Fast and robust tensor decomposition with applications to dictionary learning. ArXiv preprint 1706.08672.
• A. Tal. On the Sensitivity Conjecture. ICALP 2016, 38:1-38:13.
• A. Tal. Formula lower bounds via the Quantum Method. STOC 2017.
• E. Viola, A. Wigderson. Local Expanders. ECCC 2016, 23:129.