default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID8th ITCS 2017: Berkeley, CA, USA
- Christos H. Papadimitriou:
8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, USA, January 9-11, 2017. LIPIcs 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-029-3 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:x
- James R. Lee:
Separators in Region Intersection Graphs. 1:1-1:8 - Ioannis Panageas, Georgios Piliouras:
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. 2:1-2:12 - Zeyuan Allen Zhu, Lorenzo Orecchia
:
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. 3:1-3:22 - Tali Kaufman, David Mass:
High Dimensional Random Walks and Colorful Expansion. 4:1-4:27 - Prasad Raghavendra, Nick Ryder, Nikhil Srivastava:
Real Stability Testing. 5:1-5:15 - Silvio Micali:
Very Simple and Efficient Byzantine Agreement. 6:1-6:1 - Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan:
Low-Complexity Cryptographic Hash Functions . 7:1-7:31 - Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai, Gil Segev:
Hierarchical Functional Encryption. 8:1-8:27 - Arpita Ghosh, Robert Kleinberg:
Inferential Privacy Guarantees for Differentially Private Mechanisms. 9:1-9:3 - Jeremiah Blocki, Manuel Blum, Anupam Datta, Santosh S. Vempala:
Towards Human Computable Passwords. 10:1-10:47 - Amir Abboud, Arturs Backurs:
Towards Hardness of Approximation for Polynomial Time Problems. 11:1-11:26 - Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. 12:1-12:17 - Shafi Goldwasser, Dhiraj Holden:
The Complexity of Problems in P Given Correlated Instances. 13:1-13:19 - Martin Fürer:
Multi-Clique-Width. 14:1-14:13 - Nancy A. Lynch, Cameron Musco, Merav Parter:
Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. 15:1-15:44 - Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani:
Mutation, Sexual Reproduction and Survival in Dynamic Environments. 16:1-16:29 - Bernard Chazelle, Chu Wang:
Self-Sustaining Iterated Learning. 17:1-17:17 - Mark Braverman, Sumegha Garg, Ariel Schvartzman:
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. 18:1-18:18 - Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan:
Compression in a Distributed Setting. 19:1-19:22 - Jop Briët, Zeev Dvir, Sivakanth Gopi:
Outlaw Distributions and Locally Decodable Codes. 20:1-20:19 - Ran Gelles, Yael Tauman Kalai:
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. 21:1-21:13 - Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel Repetition via Fortification: Analytic View and the Quantum Case. 22:1-22:33 - Scott Aaronson, Daniel Grier, Luke Schaeffer:
The Classification of Reversible Bit Operations. 23:1-23:34 - Harry Buhrman, Matthias Christandl, Jeroen Zuiddam:
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. 24:1-24:18 - Matthew B. Hastings:
Quantum Codes from High-Dimensional Manifolds. 25:1-25:26 - Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams:
Conditional Hardness for Sensitivity Problems. 26:1-26:31 - Benjamin Rossman:
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. 27:1-27:17 - Shalev Ben-David, Pooya Hatami, Avishay Tal:
Low-Sensitivity Functions from Unambiguous Certificates. 28:1-28:23 - Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer:
Testing k-Monotonicity. 29:1-29:21 - Rocco A. Servedio, Li-Yang Tan:
What Circuit Classes Can Be Learned with Non-Trivial Savings?. 30:1-30:21 - Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. 31:1-31:26 - Steffen Schuldenzucker, Sven Seuken, Stefano Battiston:
Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete. 32:1-32:20 - Eric Blais, Abhinav Bommireddi:
Testing Submodularity and Other Properties of Valuation Functions. 33:1-33:17 - Yakov Babichenko, Siddharth Barman:
Algorithmic Aspects of Private Bayesian Persuasion. 34:1-34:16 - Jon Schneider, Ariel Schvartzman, S. Matthew Weinberg:
Condorcet-Consistent and Approximately Strategyproof Tournament Rules. 35:1-35:20 - Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh:
Nash Social Welfare, Matrix Permanent, and Stable Polynomials. 36:1-36:12 - Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen:
Multiplayer Parallel Repetition for Expanding Games. 37:1-37:16 - Joël Alwen, Susanna F. de Rezende, Jakob Nordström, Marc Vinyals:
Cumulative Space in Black-White Pebbling and Resolution. 38:1-38:21 - Tom Gur, Ron D. Rothblum:
A Hierarchy Theorem for Interactive Proofs of Proximity. 39:1-39:43 - Amey Bhangale, Irit Dinur, Inbal Livni Navon:
Cube vs. Cube Low Degree Test. 40:1-40:31 - Vitaly Feldman, Badih Ghazi:
On the Power of Learning from k-Wise Queries. 41:1-41:32 - Aviad Rubinstein:
Detecting communities is Hard (And Counting Them is Even Harder). 42:1-42:13 - Jon M. Kleinberg, Sendhil Mullainathan, Manish Raghavan:
Inherent Trade-Offs in the Fair Determination of Risk Scores. 43:1-43:23 - Lennart Gulikers, Marc Lelarge, Laurent Massoulié:
Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models. 44:1-44:27 - Brendan Juba:
Conditional Sparse Linear Regression. 45:1-45:14 - Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick:
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. 46:1-46:14 - Mathieu Laurière, Dave Touchette:
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting. 47:1-47:1 - Rui Chao, Ben W. Reichardt, Chris Sutherland, Thomas Vidick:
Overlapping Qubits. 48:1-48:21 - Iordanis Kerenidis, Anupam Prakash:
Quantum Recommendation Systems. 49:1-49:21 - Yuval Peres, Mohit Singh, Nisheeth K. Vishnoi:
Random Walks in Polytopes and Negative Dependence. 50:1-50:10 - Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein:
Simultaneously Load Balancing for Every p-norm, With Reassignments. 51:1-51:14 - Michael Dinitz, Zeyu Zhang:
Approximating Approximate Distance Oracles. 52:1-52:14 - Christopher Kennedy, Rachel A. Ward:
Fast Cross-Polytope Locality-Sensitive Hashing. 53:1-53:16 - Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Erisa Terolli:
The Distortion of Locality Sensitive Hashing. 54:1-54:18 - Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam:
Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. 55:1-55:19 - Leonard J. Schulman, Umesh V. Vazirani:
The Duality Gap for Two-Team Zero-Sum Games. 56:1-56:8 - Xi Chen, Yu Cheng, Bo Tang:
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. 57:1-57:9 - Daniel Stubbs, Virginia Vassilevska Williams:
Metatheorems for Dynamic Weighted Matching. 58:1-58:14 - Ryan O'Donnell:
SOS Is Not Obviously Automatizable, Even Approximately. 59:1-59:10 - Pavel Hubácek, Moni Naor, Eylon Yogev:
The Journey from NP to TFNP Hardness. 60:1-60:21
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-28 23:53 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
