ITCS 2017 January 9-11, 2017 - Berkeley, CA, USA

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)



Christos H. Papadimitriou (Ed.)
ISBN 978-3-95977-029-3, LIPICS Vol. 67 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 32 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Abboud, Amir
  • Allen-Zhu, Zeyuan
  • Alwen, Joël
  • Anari, Nima
  • Applebaum, Benny
  • Arad, Itai
  • Babichenko, Yakov
  • Backurs, Arturs
  • Barman, Siddharth
  • Battiston, Stefano
  • Bavarian, Mohammad
  • Ben-David, Shalev
  • Bernstein, Aaron
  • Bhangale, Amey
  • Blais, Eric
  • Blocki, Jeremiah
  • Blum, Manuel
  • Bommireddi, Abhinav
  • Brakerski, Zvika
  • Braverman, Mark
  • Briët, Jop
  • Buhrman, Harry
  • Buss, Sam
  • Canonne, Clément L.
  • Chandran, Nishanth
  • Chao, Rui
  • Chazelle, Bernard
  • Chen, Xi
  • Cheng, Yu
  • Chierichetti, Flavio
  • Christandl, Matthias
  • Datta, Anupam
  • de Rezende, Susanna F.
  • Dinitz, Michael
  • Dinur, Irit
  • Dvir, Zeev
  • Feldman, Vitaly
  • Fürer, Martin
  • Garg, Sumegha
  • Gelles, Ran
  • Ghazi, Badih
  • Ghosh, Arpita
  • Goldwasser, Shafi
  • Gopi, Sivakanth
  • Goyal, Vipul
  • Grier, Daniel
  • Grigorescu, Elena
  • Gulikers, Lennart
  • Guo, Siyao
  • Gur, Tom
  • Haramaty, Elad
  • Haramaty-Krasne, Naama
  • Harsha, Prahladh
  • Hastings, Matthew B.
  • Hatami, Pooya
  • Henzinger, Monika
  • Holden, Dhiraj
  • Hubácek, Pavel
  • Ishai, Yuval
  • Ivanyos, Gábor
  • Jain, Aayush
  • Juba, Brendan
  • Kabanets, Valentine
  • Kamath, Pritish
  • Kaufman, Tali
  • Kennedy, Christopher
  • Kerenidis, Iordanis
  • Kleinberg, Jon
  • Kleinberg, Robert
  • Kolokolova, Antonina
  • Kopelowitz, Tsvi
  • Koucky, Michal
  • Kumar, Akash
  • Kumar, Ravi
  • Kushilevitz, Eyal
  • Landau, Zeph
  • Laurière, Mathieu
  • Lee, James R.
  • Lelarge, Marc
  • Lincoln, Andrea
  • Livni Navon, Inbal
  • Lynch, Nancy
  • Mass, David
  • Massoulié, Laurent
  • Mehta, Ruta
  • Micali, Silvio
  • Mullainathan, Sendhil
  • Musco, Cameron
  • Naor, Moni
  • Neumann, Stefan
  • Nordström, Jakob
  • O'Donnell, Ryan
  • Orecchia, Lorenzo
  • Oveis Gharan, Shayan
  • Pallavoor, Ramesh Krishnan S.
  • Panageas, Ioannis
  • Panconesi, Alessandro
  • Papadimitriou, Christos H.
  • Parter, Merav
  • Peres, Yuval
  • Pettie, Seth
  • Piliouras, Georgios
  • Porat, Ely
  • Prakash, Anupam
  • Qiao, Youming
  • Raghavan, Manish
  • Raghavendra, Prasad
  • Raskhodnikova, Sofya
  • Reichardt, Ben W.
  • Rossman, Benjamin
  • Rothblum, Ron D.
  • Rubinstein, Aviad
  • Ryder, Nick
  • Saberi, Amin
  • Sahai, Amit
  • Schaeffer, Luke
  • Schneider, Jon
  • Schuldenzucker, Steffen
  • Schulman, Leonard
  • Schvartzman, Ariel
  • Segev, Gil
  • Servedio, Rocco A.
  • Seuken, Sven
  • Singh, Mohit
  • Srivastava, Nikhil
  • Stein, Clifford
  • Stubbs, Daniel
  • Subrahmanyam, K Venkata
  • Sudan, Madhu
  • Sutherland, Chris
  • T. Kalai, Yael
  • Tal, Avishay
  • Tan, Li-Yang
  • Tang, Bo
  • Terolli, Erisa
  • Tetali, Prasad
  • Touchette, Dave
  • Vaikuntanathan, Vinod
  • Varma, Nithin
  • Vassilevska Williams, Virginia
  • Vazirani, Umesh V.
  • Vazirani, Vijay V.
  • Vempala, Santosh
  • Venkat, Rakesh
  • Vidick, Thomas
  • Vinyals, Marc
  • Vishnoi, Nisheeth K.
  • Wang, Chu
  • Ward, Rachel
  • Weinberg, S. Matthew
  • Wimmer, Karl
  • Yogev, Eylon
  • Yuen, Henry
  • Zhang, Zeyu
  • Zuiddam, Jeroen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Papadimitriou, Christos H.

    Abstract | Document (299 KB) | BibTeX

    Separators in Region Intersection Graphs
    Authors: Lee, James R.

    Abstract | Document (501 KB) | BibTeX

    Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
    Authors: Panageas, Ioannis ; Piliouras, Georgios

    Abstract | Document (688 KB) | BibTeX

    Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
    Authors: Allen-Zhu, Zeyuan ; Orecchia, Lorenzo

    Abstract | Document (637 KB) | BibTeX

    High Dimensional Random Walks and Colorful Expansion
    Authors: Kaufman, Tali ; Mass, David

    Abstract | Document (564 KB) | BibTeX

    Real Stability Testing
    Authors: Raghavendra, Prasad ; Ryder, Nick ; Srivastava, Nikhil

    Abstract | Document (515 KB) | BibTeX

    Very Simple and Efficient Byzantine Agreement
    Authors: Micali, Silvio

    Abstract | Document (225 KB) | BibTeX

    Low-Complexity Cryptographic Hash Functions
    Authors: Applebaum, Benny ; Haramaty-Krasne, Naama ; Ishai, Yuval ; Kushilevitz, Eyal ; Vaikuntanathan, Vinod

    Abstract | Document (685 KB) | BibTeX

    Hierarchical Functional Encryption
    Authors: Brakerski, Zvika ; Chandran, Nishanth ; Goyal, Vipul ; Jain, Aayush ; Sahai, Amit ; Segev, Gil

    Abstract | Document (739 KB) | BibTeX

    Inferential Privacy Guarantees for Differentially Private Mechanisms
    Authors: Ghosh, Arpita ; Kleinberg, Robert

    Abstract | Document (294 KB) | BibTeX

    Towards Human Computable Passwords
    Authors: Blocki, Jeremiah ; Blum, Manuel ; Datta, Anupam ; Vempala, Santosh

    Abstract | Document (1,645 KB) | BibTeX

    Towards Hardness of Approximation for Polynomial Time Problems
    Authors: Abboud, Amir ; Backurs, Arturs

    Abstract | Document (653 KB) | BibTeX

    Parameterized Property Testing of Functions
    Authors: Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Varma, Nithin

    Abstract | Document (581 KB) | BibTeX

    The Complexity of Problems in P Given Correlated Instances
    Authors: Goldwasser, Shafi ; Holden, Dhiraj

    Abstract | Document (570 KB) | BibTeX

    Multi-Clique-Width
    Authors: Fürer, Martin

    Abstract | Document (433 KB) | BibTeX

    Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
    Authors: Lynch, Nancy ; Musco, Cameron ; Parter, Merav

    Abstract | Document (1,309 KB) | BibTeX

    Mutation, Sexual Reproduction and Survival in Dynamic Environments
    Authors: Mehta, Ruta ; Panageas, Ioannis ; Piliouras, Georgios ; Tetali, Prasad ; Vazirani, Vijay V.

    Abstract | Document (716 KB) | BibTeX

    Self-Sustaining Iterated Learning
    Authors: Chazelle, Bernard ; Wang, Chu

    Abstract | Document (742 KB) | BibTeX

    Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
    Authors: Braverman, Mark ; Garg, Sumegha ; Schvartzman, Ariel

    Abstract | Document (824 KB) | BibTeX

    Compression in a Distributed Setting
    Authors: Ghazi, Badih ; Haramaty, Elad ; Kamath, Pritish ; Sudan, Madhu

    Abstract | Document (571 KB) | BibTeX

    Outlaw Distributions and Locally Decodable Codes
    Authors: Briët, Jop ; Dvir, Zeev ; Gopi, Sivakanth

    Abstract | Document (600 KB) | BibTeX

    Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks
    Authors: Gelles, Ran ; T. Kalai, Yael

    Abstract | Document (483 KB) | BibTeX

    Parallel Repetition via Fortification: Analytic View and the Quantum Case
    Authors: Bavarian, Mohammad ; Vidick, Thomas ; Yuen, Henry

    Abstract | Document (714 KB) | BibTeX

    The Classification of Reversible Bit Operations
    Authors: Aaronson, Scott ; Grier, Daniel ; Schaeffer, Luke

    Abstract | Document (667 KB) | BibTeX

    Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication
    Authors: Buhrman, Harry ; Christandl, Matthias ; Zuiddam, Jeroen

    Abstract | Document (545 KB) | BibTeX

    Quantum Codes from High-Dimensional Manifolds
    Authors: Hastings, Matthew B.

    Abstract | Document (526 KB) | BibTeX

    Conditional Hardness for Sensitivity Problems
    Authors: Henzinger, Monika ; Lincoln, Andrea ; Neumann, Stefan ; Vassilevska Williams, Virginia

    Abstract | Document (721 KB) | BibTeX

    An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
    Authors: Rossman, Benjamin

    Abstract | Document (672 KB) | BibTeX

    Low-Sensitivity Functions from Unambiguous Certificates
    Authors: Ben-David, Shalev ; Hatami, Pooya ; Tal, Avishay

    Abstract | Document (666 KB) | BibTeX

    Testing k-Monotonicity
    Authors: Canonne, Clément L. ; Grigorescu, Elena ; Guo, Siyao ; Kumar, Akash ; Wimmer, Karl

    Abstract | Document (661 KB) | BibTeX

    What Circuit Classes Can Be Learned with Non-Trivial Savings?
    Authors: Servedio, Rocco A. ; Tan, Li-Yang

    Abstract | Document (655 KB) | BibTeX

    Expander Construction in VNC1
    Authors: Buss, Sam ; Kabanets, Valentine ; Kolokolova, Antonina ; Koucky, Michal

    Abstract | Document (661 KB) | BibTeX

    Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete
    Authors: Schuldenzucker, Steffen ; Seuken, Sven ; Battiston, Stefano

    Abstract | Document (587 KB) | BibTeX

    Testing Submodularity and Other Properties of Valuation Functions
    Authors: Blais, Eric ; Bommireddi, Abhinav

    Abstract | Document (566 KB) | BibTeX

    Algorithmic Aspects of Private Bayesian Persuasion
    Authors: Babichenko, Yakov ; Barman, Siddharth

    Abstract | Document (514 KB) | BibTeX

    Condorcet-Consistent and Approximately Strategyproof Tournament Rules
    Authors: Schneider, Jon ; Schvartzman, Ariel ; Weinberg, S. Matthew

    Abstract | Document (844 KB) | BibTeX

    Nash Social Welfare, Matrix Permanent, and Stable Polynomials
    Authors: Anari, Nima ; Oveis Gharan, Shayan ; Saberi, Amin ; Singh, Mohit

    Abstract | Document (464 KB) | BibTeX

    Multiplayer Parallel Repetition for Expanding Games
    Authors: Dinur, Irit ; Harsha, Prahladh ; Venkat, Rakesh ; Yuen, Henry

    Abstract | Document (556 KB) | BibTeX

    Cumulative Space in Black-White Pebbling and Resolution
    Authors: Alwen, Joël ; de Rezende, Susanna F. ; Nordström, Jakob ; Vinyals, Marc

    Abstract | Document (545 KB) | BibTeX

    A Hierarchy Theorem for Interactive Proofs of Proximity
    Authors: Gur, Tom ; Rothblum, Ron D.

    Abstract | Document (1,007 KB) | BibTeX

    Cube vs. Cube Low Degree Test
    Authors: Bhangale, Amey ; Dinur, Irit ; Livni Navon, Inbal

    Abstract | Document (590 KB) | BibTeX

    On the Power of Learning from k-Wise Queries
    Authors: Feldman, Vitaly ; Ghazi, Badih

    Abstract | Document (674 KB) | BibTeX

    Detecting communities is Hard (And Counting Them is Even Harder)
    Authors: Rubinstein, Aviad

    Abstract | Document (566 KB) | BibTeX

    Inherent Trade-Offs in the Fair Determination of Risk Scores
    Authors: Kleinberg, Jon ; Mullainathan, Sendhil ; Raghavan, Manish

    Abstract | Document (492 KB) | BibTeX

    Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
    Authors: Gulikers, Lennart ; Lelarge, Marc ; Massoulié, Laurent

    Abstract | Document (559 KB) | BibTeX

    Conditional Sparse Linear Regression
    Authors: Juba, Brendan

    Abstract | Document (456 KB) | BibTeX

    Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D
    Authors: Arad, Itai ; Landau, Zeph ; Vazirani, Umesh V. ; Vidick, Thomas

    Abstract | Document (593 KB) | BibTeX

    The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
    Authors: Laurière, Mathieu ; Touchette, Dave

    Abstract | Document (329 KB) | BibTeX

    Overlapping Qubits
    Authors: Chao, Rui ; Reichardt, Ben W. ; Sutherland, Chris ; Vidick, Thomas

    Abstract | Document (876 KB) | BibTeX

    Quantum Recommendation Systems
    Authors: Kerenidis, Iordanis ; Prakash, Anupam

    Abstract | Document (505 KB) | BibTeX

    Random Walks in Polytopes and Negative Dependence
    Authors: Peres, Yuval ; Singh, Mohit ; Vishnoi, Nisheeth K.

    Abstract | Document (434 KB) | BibTeX

    Simultaneously Load Balancing for Every p-norm, With Reassignments
    Authors: Bernstein, Aaron ; Kopelowitz, Tsvi ; Pettie, Seth ; Porat, Ely ; Stein, Clifford

    Abstract | Document (469 KB) | BibTeX

    Approximating Approximate Distance Oracles
    Authors: Dinitz, Michael ; Zhang, Zeyu

    Abstract | Document (489 KB) | BibTeX

    Fast Cross-Polytope Locality-Sensitive Hashing
    Authors: Kennedy, Christopher ; Ward, Rachel

    Abstract | Document (615 KB) | BibTeX

    The Distortion of Locality Sensitive Hashing
    Authors: Chierichetti, Flavio ; Kumar, Ravi ; Panconesi, Alessandro ; Terolli, Erisa

    Abstract | Document (765 KB) | BibTeX

    Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time
    Authors: Ivanyos, Gábor ; Qiao, Youming ; Subrahmanyam, K Venkata

    Abstract | Document (580 KB) | BibTeX

    The Duality Gap for Two-Team Zero-Sum Games
    Authors: Schulman, Leonard ; Vazirani, Umesh V.

    Abstract | Document (434 KB) | BibTeX

    Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games
    Authors: Chen, Xi ; Cheng, Yu ; Tang, Bo

    Abstract | Document (473 KB) | BibTeX

    Metatheorems for Dynamic Weighted Matching
    Authors: Stubbs, Daniel ; Vassilevska Williams, Virginia

    Abstract | Document (492 KB) | BibTeX

    SOS Is Not Obviously Automatizable, Even Approximately
    Authors: O'Donnell, Ryan

    Abstract | Document (471 KB) | BibTeX

    The Journey from NP to TFNP Hardness
    Authors: Hubácek, Pavel ; Naor, Moni ; Yogev, Eylon

    Abstract | Document (624 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI