ITCS 2017 Accepted Papers

Damian Straszak and Nisheeth K. Vishnoi. IRLS and Slime Mold: Equivalence and Convergence
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions
Martin Fürer. Multi-Clique-Width
Brendan Juba. Conditional Sparse Linear Regression
Gabor Ivanyos, Youming Qiao and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time
Jon Schneider, Ariel Schvartzman and S. Matthew Weinberg. Condorcet-Consistent and Approximately Strategyproof Tournament Rules
Rocco Servedio and Li-Yang Tan. What circuit classes can be learned with non-trivial savings?
Mark Braverman, Sumegha Garg and Ariel Schvartzman. Network coding in undirected graphs is either very helpful or not helpful at all
Jeremiah Blocki, Manuel Blum, Anupam Datta and Santosh Vempala. Towards Human Computable Passwords
Ryan O'Donnell. SOS is not obviously automatizable, even approximately
Matthew Hastings. Quantum Codes from High-Dimensional Manifolds
Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi and Erisa Terolli. The Distortion of Locality Sensitive Hashing
Leonard J. Schulman and Umesh Vazirani. The Duality Gap for Two-Team Zero-Sum Games
Bernard Chazelle and Chu Wang. Self-Sustaining Iterated Learning
Daniel Stubbs and Virginia Vassilevska Williams. Metatheorems for dynamic weighted matching
David Mass and Tali Kaufman. High Dimensional Random Walks and Colorful Expansion
Ran Gelles and Yael Kalai. Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks
Clément Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar and Karl Wimmer. Testing k-Monotonicity
Harry Buhrman, Matthias Christandl and Jeroen Zuiddam. Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication
Shafi Goldwasser and Dhiraj Holden. The Complexity of Problems in P Given Correlated Instances
Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems
Arpita Ghosh and Robert Kleinberg. Inferential Privacy Guarantees for Differentially Private Mechanisms
Scott Aaronson, Daniel Grier and Luke Schaeffer. The Classification of Reversible Bit Operations
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai and Gil Segev. Hierarchical Functional Encryption
Sam Buss, Valentine Kabanets, Antonina Kolokolova and Michal Koucky. Expander Construction in VNC^1
Xi Chen, Yu Cheng and Bo Tang. Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games
Yakov Babichenko and Siddharth Barman. Algorithmic Aspects of Private Bayesian Persuasion
Lennart Gulikers, Marc Lelarge and Laurent Massoulié. Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Pavel Hubacek, Moni Naor and Eylon Yogev. The Journey from NP to TFNP Hardness
Amey Bhangale, Irit Dinur and Inbal Rachel Livni Navon. Cube vs Cube Low Degree Test
Christopher Kennedy and Rachel Ward. Fast Cross-Polytope Locality-Sensitive Hashing
Tom Gur and Ron Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity
Sivakanth Gopi, Zeev Dvir and Jop Briet. Outlaw distributions and locally decodable codes
Mohammad Bavarian, Thomas Vidick and Henry Yuen. Parallel repetition via fortification: analytic view and the quantum case
Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan. Inherent Trade-Offs in the Fair Determination of Risk Scores
Michael Dinitz and Zeyu Zhang. Approximating Approximate Distance Oracles
Aviad Rubinstein. Detecting communities is hard... and counting them is even harder!
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali and Vijay Vazirani. Mutation, Sexual Reproduction and Survival in Dynamic Environments
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat and Clifford Stein. Simultaneously Load Balancing for Every $p$-norm, With Reassignments
Badih Ghazi, Elad Haramaty, Pritish Kamath and Madhu Sudan. Compression in a Distributed Setting
Abhinav Bommireddi and Eric Blais. Testing submodularity and other properties of valuation functions
James Lee. Separators in region intersection graphs
Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems
Yuval Peres, Mohit Singh and Nisheeth Vishnoi. Random Walks in Polytopes and Negative Dependence
Rui Chao, Ben Reichardt, Chris Sutherland and Thomas Vidick. Overlapping qubits
Irit Dinur, Prahladh Harsha, Rakesh Venkat and Henry Yuen. Multiplayer parallel repetition for expander games
Cameron Musco, Nancy Lynch and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
Silvio Micali. Fast and Furious Byzantine Agreement
Mathieu Laurière and Dave Touchette. The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
Vitaly Feldman and Badih Ghazi. On the Power of Learning from k-Wise Queries
Shalev Ben-David, Pooya Hatami and Avishay Tal. Low-Sensitivity Functions from Unambiguous Certificates
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and Nithin Varma. Parameterized Property Testing of Functions
Nima Anari, Shayan Oveis Gharan, Amin Saberi and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials
Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
Steffen Schuldenzucker, Sven Seuken and Stefano Battiston. Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-hard
Prasad Raghavendra, Nicholas Ryder and Nikhil Srivastava. Real-Stability Testing
Benjamin Rossman. An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity
Itai Arad, Zeph Landau, Umesh Vazirani and Thomas Vidick. Rigorous RG algorithms and area laws for low energy eigenstates in 1D
Amir Abboud and Arturs Backurs. Towards Hardness of Approximation for Polynomial Time Problems
Joël Alwen, Susanna F. de Rezende, Jakob Nordström and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution