ITCS 2018 January 11-14, 2018 - Cambridge, MA, USA

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)



Anna R. Karlin (Ed.)
ISBN 978-3-95977-060-6, LIPICS Vol. 94 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 38 MB)
Search Publication Server

Authors
  • Abboud, Amir
  • Ailon, Nir
  • Alev, Vedat Levi
  • Allender, Eric
  • Alman, Josh
  • Anari, Nima
  • Arunachalam, Srinivasan
  • Balcan, Maria-Florina
  • Balcer, Victor
  • Beame, Paul
  • Ben-Or, Michael
  • Berman, Itay
  • Bernstein, Aaron
  • Beyersdorff, Olaf
  • Bhaskara, Aditya
  • Bhattacharya, Anup
  • Blinkhorn, Joshua
  • Blum, Avrim
  • Boczkowski, Lucas
  • Boyle, Elette
  • Braverman, Mark
  • Briët, Jop
  • Bürgisser, Peter
  • Cai, Jin-Yi
  • Censor-Hillel, Keren
  • Chandrasekaran, Karthekeyan
  • Charikar, Moses
  • Chazelle, Bernard
  • Chiesa, Alessandro
  • Dadush, Daniel
  • Däubel, Karl
  • Demaine, Erik D.
  • Diakonikolas, Jelena
  • Dinur, Irit
  • Disser, Yann
  • Dürr, Christoph
  • Efremenko, Klim
  • Eldar, Lior
  • Erlebach, Thomas
  • Fefferman, Bill
  • Feinerman, Ofer
  • Fleming, Noah
  • Frongillo, Rafael
  • Fu, Zhiguo
  • Gandikota, Venkata
  • Ganor, Anat
  • Garg, Ankit
  • Gelles, Ran
  • Gilboa, Niv
  • Girstmair, Kurt
  • Gishboliner, Lior
  • Goldberg, Paul W.
  • Goldreich, Oded
  • Goldwasser, Shafi
  • Grigorescu, Elena
  • Grochow, Joshua A.
  • Grossman, Ofer
  • Groß, Martin
  • Gupta, Anupam
  • Gur, Tom
  • Haeupler, Bernhard
  • Har-Peled, Sariel
  • Hatami, Pooya
  • Hinde, Luke
  • Holden, Dhiraj
  • Huang, Qingqing
  • Impagliazzo, Russell
  • Ishai, Yuval
  • Jaiswal, Ragesh
  • Kakade, Sham M.
  • Karlin, Anna R.
  • Karwa, Vishesh
  • Kleinberg, Jon
  • Klimm, Max
  • Kol, Gillat
  • Kolokolova, Antonina
  • Kong, Weihao
  • Kong, Yuqing
  • Korman, Amos
  • Kothari, Pravesh K.
  • Kowalczyk, Michael
  • Ko, Young Kun
  • Kumar, Amit
  • Lattanzi, Silvio
  • Lau, Lap Chi
  • Legenstein, Robert
  • Liang, Yingyu
  • Lin, Cedric Yen-Yu
  • Lincoln, Andrea
  • Lin, Huijia
  • Liu, Quanquan C.
  • Livni, Roi
  • Lokshtanov, Daniel
  • Lynch, Jayson
  • Maass, Wolfgang
  • Mansour, Yishay
  • Manurangsi, Pasin
  • Matuschke, Jannik
  • Megow, Nicole
  • Meißner, Julie
  • Misra, Pranabendu
  • Moore, Cristopher
  • Morgan, Andrew
  • Moshkovitz, Dana
  • Moshkovitz, Michal
  • Musco, Cameron
  • Mütze, Torsten
  • Natale, Emanuele
  • Natarajan Ramamoorthy, Sivaramakrishnan
  • Netrapalli, Praneeth
  • Oliveira, Rafael
  • Orecchia, Lorenzo
  • Oveis Gharan, Shayan
  • Palazuelos, Carlos
  • Panigrahy, Rina
  • Pankratov, Denis
  • Panolan, Fahad
  • Papadimitriou, Christos H.
  • Piliouras, Georgios
  • Pitassi, Toniann
  • Qiao, Mingda
  • Raghavan, Manish
  • Rahimi, Ali
  • Ramnarayan, Govind
  • Rashtchian, Cyrus
  • Raz, Ran
  • Robere, Robert
  • Rothblum, Guy N.
  • Rothblum, Ron D.
  • Rubinstein, Aviad
  • Sachdeva, Sushant
  • Saurabh, Saket
  • Schmidt, Daniel R.
  • Schmidt, Melanie
  • Schoenebeck, Grant
  • Schramm, Tselil
  • Schulman, Leonard J.
  • Shapira, Asaf
  • Sidford, Aaron
  • Sinha, Makrand
  • Slivkins, Aleksandrs
  • Smolny, Frieder
  • Solomon, Shay
  • Srinivasan, Srikanth
  • Steinhardt, Jacob
  • Sudan, Madhu
  • Tal, Avishay
  • Tessaro, Stefano
  • Ubaru, Shashanka
  • Vadhan, Salil
  • Vaikuntanathan, Vinod
  • Valiant, Gregory
  • van Melkebeek, Dieter
  • Vassilevska Williams, Virginia
  • Vempala, Santosh S.
  • Verschae, José
  • Waggoner, Bo
  • Walter, Michael
  • Weinberg, S. Matthew
  • Wigderson, Avi
  • Woodruff, David P.
  • Wu, Zhiwei Steven
  • Yang, Greg
  • Zehavi, Meirav
  • Zhang, Hongyang
  • Zhang, Qiuyi
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Karlin, Anna R.

    Abstract | Document (380 KB) | BibTeX

    Barriers for Rank Methods in Arithmetic Complexity
    Authors: Efremenko, Klim ; Garg, Ankit ; Oliveira, Rafael ; Wigderson, Avi

    Abstract | Document (651 KB) | BibTeX

    A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
    Authors: Cai, Jin-Yi ; Fu, Zhiguo ; Girstmair, Kurt ; Kowalczyk, Michael

    Abstract | Document (569 KB) | BibTeX

    Quantum Query Algorithms are Completely Bounded Forms
    Authors: Arunachalam, Srinivasan ; Briët, Jop ; Palazuelos, Carlos

    Abstract | Document (709 KB) | BibTeX

    A Complete Characterization of Unitary Quantum Space
    Authors: Fefferman, Bill ; Lin, Cedric Yen-Yu

    Abstract | Document (685 KB) | BibTeX

    Matrix Completion and Related Problems via Strong Duality
    Authors: Balcan, Maria-Florina ; Liang, Yingyu ; Woodruff, David P. ; Zhang, Hongyang

    Abstract | Document (1,614 KB) | BibTeX

    A Quasi-Random Approach to Matrix Spectral Analysis
    Authors: Ben-Or, Michael ; Eldar, Lior

    Abstract | Document (598 KB) | BibTeX

    Non-Negative Sparse Regression and Column Subset Selection with L1 Error
    Authors: Bhaskara, Aditya ; Lattanzi, Silvio

    Abstract | Document (614 KB) | BibTeX

    Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
    Authors: Musco, Cameron ; Netrapalli, Praneeth ; Sidford, Aaron ; Ubaru, Shashanka ; Woodruff, David P.

    Abstract | Document (683 KB) | BibTeX

    Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs
    Authors: Beyersdorff, Olaf ; Blinkhorn, Joshua ; Hinde, Luke

    Abstract | Document (548 KB) | BibTeX

    Stabbing Planes
    Authors: Beame, Paul ; Fleming, Noah ; Impagliazzo, Russell ; Kolokolova, Antonina ; Pankratov, Denis ; Pitassi, Toniann ; Robere, Robert

    Abstract | Document (594 KB) | BibTeX

    A Candidate for a Strong Separation of Information and Communication
    Authors: Braverman, Mark ; Ganor, Anat ; Kol, Gillat ; Raz, Ran

    Abstract | Document (472 KB) | BibTeX

    Information Value of Two-Prover Games
    Authors: Braverman, Mark ; Ko, Young Kun

    Abstract | Document (553 KB) | BibTeX

    Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
    Authors: Kong, Yuqing ; Schoenebeck, Grant

    Abstract | Document (2,917 KB) | BibTeX

    Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
    Authors: Kong, Yuqing ; Schoenebeck, Grant

    Abstract | Document (3,153 KB) | BibTeX

    An Axiomatic Study of Scoring Rule Markets
    Authors: Frongillo, Rafael ; Waggoner, Bo

    Abstract | Document (823 KB) | BibTeX

    On Price versus Quality
    Authors: Blum, Avrim ; Mansour, Yishay

    Abstract | Document (483 KB) | BibTeX

    Pseudo-Deterministic Proofs
    Authors: Goldwasser, Shafi ; Grossman, Ofer ; Holden, Dhiraj

    Abstract | Document (497 KB) | BibTeX

    Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
    Authors: Goldreich, Oded ; Rothblum, Guy N.

    Abstract | Document (653 KB) | BibTeX

    Zero-Knowledge Proofs of Proximity
    Authors: Berman, Itay ; Rothblum, Ron D. ; Vaikuntanathan, Vinod

    Abstract | Document (654 KB) | BibTeX

    Minimum Circuit Size, Graph Isomorphism, and Related Problems
    Authors: Allender, Eric ; Grochow, Joshua A. ; van Melkebeek, Dieter ; Moore, Cristopher ; Morgan, Andrew

    Abstract | Document (590 KB) | BibTeX

    Foundations of Homomorphic Secret Sharing
    Authors: Boyle, Elette ; Gilboa, Niv ; Ishai, Yuval ; Lin, Huijia ; Tessaro, Stefano

    Abstract | Document (645 KB) | BibTeX

    Convergence Results for Neural Networks via Electrodynamics
    Authors: Panigrahy, Rina ; Rahimi, Ali ; Sachdeva, Sushant ; Zhang, Qiuyi

    Abstract | Document (702 KB) | BibTeX

    Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
    Authors: Diakonikolas, Jelena ; Orecchia, Lorenzo

    Abstract | Document (1,147 KB) | BibTeX

    Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory
    Authors: Bürgisser, Peter ; Garg, Ankit ; Oliveira, Rafael ; Walter, Michael ; Wigderson, Avi

    Abstract | Document (628 KB) | BibTeX

    Further Limitations of the Known Approaches for Matrix Multiplication
    Authors: Alman, Josh ; Vassilevska Williams, Virginia

    Abstract | Document (548 KB) | BibTeX

    Local Decoding and Testing of Polynomials over Grids
    Authors: Srinivasan, Srikanth ; Sudan, Madhu

    Abstract | Document (565 KB) | BibTeX

    Relaxed Locally Correctable Codes
    Authors: Gur, Tom ; Ramnarayan, Govind ; Rothblum, Ron D.

    Abstract | Document (538 KB) | BibTeX

    Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
    Authors: Moshkovitz, Dana ; Moshkovitz, Michal

    Abstract | Document (580 KB) | BibTeX

    Pseudorandom Generators for Low Sensitivity Functions
    Authors: Hatami, Pooya ; Tal, Avishay

    Abstract | Document (541 KB) | BibTeX

    Scheduling with Explorable Uncertainty
    Authors: Dürr, Christoph ; Erlebach, Thomas ; Megow, Nicole ; Meißner, Julie

    Abstract | Document (639 KB) | BibTeX

    A Local-Search Algorithm for Steiner Forest
    Authors: Groß, Martin ; Gupta, Anupam ; Kumar, Amit ; Matuschke, Jannik ; Schmidt, Daniel R. ; Schmidt, Melanie ; Verschae, José

    Abstract | Document (615 KB) | BibTeX

    Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
    Authors: Lokshtanov, Daniel ; Misra, Pranabendu ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (542 KB) | BibTeX

    Selection Problems in the Presence of Implicit Bias
    Authors: Kleinberg, Jon ; Raghavan, Manish

    Abstract | Document (642 KB) | BibTeX

    Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
    Authors: Demaine, Erik D. ; Lincoln, Andrea ; Liu, Quanquan C. ; Lynch, Jayson ; Vassilevska Williams, Virginia

    Abstract | Document (653 KB) | BibTeX

    Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
    Authors: Abboud, Amir ; Rubinstein, Aviad

    Abstract | Document (545 KB) | BibTeX

    ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
    Authors: Dinur, Irit ; Manurangsi, Pasin

    Abstract | Document (595 KB) | BibTeX

    Towards a Unified Complexity Theory of Total Functions
    Authors: Goldberg, Paul W. ; Papadimitriou, Christos H.

    Abstract | Document (598 KB) | BibTeX

    Edge Estimation with Independent Set Oracles
    Authors: Beame, Paul ; Har-Peled, Sariel ; Natarajan Ramamoorthy, Sivaramakrishnan ; Rashtchian, Cyrus ; Sinha, Makrand

    Abstract | Document (706 KB) | BibTeX

    Computing Exact Minimum Cuts Without Knowing the Graph
    Authors: Rubinstein, Aviad ; Schramm, Tselil ; Weinberg, S. Matthew

    Abstract | Document (581 KB) | BibTeX

    Approximate Clustering with Same-Cluster Queries
    Authors: Ailon, Nir ; Bhattacharya, Anup ; Jaiswal, Ragesh ; Kumar, Amit

    Abstract | Document (654 KB) | BibTeX

    Graph Clustering using Effective Resistance
    Authors: Alev, Vedat Levi ; Anari, Nima ; Lau, Lap Chi ; Oveis Gharan, Shayan

    Abstract | Document (557 KB) | BibTeX

    Lattice-based Locality Sensitive Hashing is Optimal
    Authors: Chandrasekaran, Karthekeyan ; Dadush, Daniel ; Gandikota, Venkata ; Grigorescu, Elena

    Abstract | Document (556 KB) | BibTeX

    Differential Privacy on Finite Computers
    Authors: Balcer, Victor ; Vadhan, Salil

    Abstract | Document (672 KB) | BibTeX

    Finite Sample Differentially Private Confidence Intervals
    Authors: Karwa, Vishesh ; Vadhan, Salil

    Abstract | Document (467 KB) | BibTeX

    Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
    Authors: Steinhardt, Jacob ; Charikar, Moses ; Valiant, Gregory

    Abstract | Document (617 KB) | BibTeX

    Recovering Structured Probability Matrices
    Authors: Huang, Qingqing ; Kakade, Sham M. ; Kong, Weihao ; Valiant, Gregory

    Abstract | Document (547 KB) | BibTeX

    Learning Discrete Distributions from Untrusted Batches
    Authors: Qiao, Mingda ; Valiant, Gregory

    Abstract | Document (626 KB) | BibTeX

    Competing Bandits: Learning Under Competition
    Authors: Mansour, Yishay ; Slivkins, Aleksandrs ; Wu, Zhiwei Steven

    Abstract | Document (670 KB) | BibTeX

    Limits for Rumor Spreading in Stochastic Populations
    Authors: Boczkowski, Lucas ; Feinerman, Ofer ; Korman, Amos ; Natale, Emanuele

    Abstract | Document (1,199 KB) | BibTeX

    Making Asynchronous Distributed Computations Robust to Channel Noise
    Authors: Censor-Hillel, Keren ; Gelles, Ran ; Haeupler, Bernhard

    Abstract | Document (626 KB) | BibTeX

    Distance-Preserving Graph Contractions
    Authors: Bernstein, Aaron ; Däubel, Karl ; Disser, Yann ; Klimm, Max ; Mütze, Torsten ; Smolny, Frieder

    Abstract | Document (569 KB) | BibTeX

    Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
    Authors: Solomon, Shay

    Abstract | Document (535 KB) | BibTeX

    Proofs of Proximity for Distribution Testing
    Authors: Chiesa, Alessandro ; Gur, Tom

    Abstract | Document (548 KB) | BibTeX

    Efficient Testing without Efficient Regularity
    Authors: Gishboliner, Lior ; Shapira, Asaf

    Abstract | Document (506 KB) | BibTeX

    Improper Learning by Refuting
    Authors: Kothari, Pravesh K. ; Livni, Roi

    Abstract | Document (501 KB) | BibTeX

    A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
    Authors: Yang, Greg

    Abstract | Document (1,020 KB) | BibTeX

    Long Term Memory and the Densest K-Subgraph Problem
    Authors: Legenstein, Robert ; Maass, Wolfgang ; Papadimitriou, Christos H. ; Vempala, Santosh S.

    Abstract | Document (666 KB) | BibTeX

    Toward a Theory of Markov Influence Systems and their Renormalization
    Authors: Chazelle, Bernard

    Abstract | Document (1,113 KB) | BibTeX

    Learning Dynamics and the Co-Evolution of Competing Sexual Species
    Authors: Piliouras, Georgios ; Schulman, Leonard J.

    Abstract | Document (364 KB) | BibTeX

    		  



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