ITCS 2019 January 10-12, 2019 - San Diego, California, USA

10th Innovations in Theoretical Computer Science Conference (ITCS 2019)



Avrim Blum (Ed.)
ISBN 978-3-95977-095-8, LIPICS Vol. 124 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 32 MB)
Search Publication Server

Authors
  • Agrawal, Shipra
  • Aharonov, Dorit
  • Andoni, Alexandr
  • Applebaum, Benny
  • Arnosti, Nick
  • Assadi, Sepehr
  • Austrin, Per
  • Bajpai, Swapnam
  • Barak, Boaz
  • Ben-Eliezer, Omri
  • Bene Watts, Adam
  • Ben-Sasson, Eli
  • Bhrushundi, Abhishek
  • Bilò, Vittorio
  • Bläser, Markus
  • Blum, Avrim
  • Bouland, Adam
  • Boyle, Elette
  • Caragiannis, Ioannis
  • Carboni Oliveira, Igor
  • Chailloux, André
  • Chakrabarty, Deeparnab
  • Chan, Timothy M.
  • Chase, Zachary
  • Chattopadhyay, Eshan
  • Chen, Lijie
  • Chen, Wei
  • Cheraghchi, Mahdi
  • Chiesa, Alessandro
  • Chou, Chi-Ning
  • Chung, Kai-Min
  • C. S., Karthik
  • Daskalakis, Constantinos
  • De, Anindya
  • Dinur, Irit
  • Dughmi, Shaddin
  • Dvir, Zeev
  • Dwork, Cynthia
  • Fefferman, Bill
  • Filmus, Yuval
  • Flammini, Michele
  • Gál, Anna
  • Garg, Sumegha
  • Goldreich, Oded
  • Göös, Mika
  • Gopi, Sivakanth
  • Gur, Tom
  • Guruswami, Venkatesan
  • Gu, Yuzhou
  • Haitner, Iftach
  • Hamilton, Linus
  • Har-Peled, Sariel
  • Harrow, Aram W.
  • Harsha, Prahladh
  • Hatami, Pooya
  • Horel, Thibaut
  • Hosseini, Kaave
  • Igarashi, Ayumi
  • Ilvento, Christina
  • Jansen, Klaus
  • Jin, Ce
  • Jindal, Gorav
  • Jin, Yan
  • Jones, Mitchell
  • Kamath, Pritish
  • Kane, Daniel M.
  • Kanwar, Gurtej
  • Kapralov, Michael
  • Kaski, Petteri
  • Kaufman, Tali
  • Kempe, David
  • Khanna, Sanjeev
  • Kim Thang, Nguyen
  • Klein, Kim-Manuel
  • Kothari, Pravesh K.
  • Krauthgamer, Robert
  • Krishan, Vaibhav
  • Kubjas, Kaie
  • Kumar, Ravi
  • Kush, Deepanshu
  • LaVigne, Rio
  • Lee, Troy
  • Levi, Amit
  • Limaye, Nutan
  • Lin, Fuchun
  • Linial, Nati
  • Liu, Jingcheng
  • Long, Philip M.
  • Lovett, Shachar
  • Lu, Chi-Jen
  • Maack, Marten
  • Manohar, Peter
  • Manurangsi, Pasin
  • Mazor, Noam
  • McKay, Dylan M.
  • Moitra, Ankur
  • Monaco, Gianpiero
  • Mossel, Elchanan
  • Nakkiran, Preetum
  • Natarajan, Anand
  • Nirkhe, Chinmay
  • O'Donnell, Ryan
  • Oshman, Rotem
  • Panageas, Ioannis
  • Papadimitriou, Christos H.
  • Park, Sunoo
  • Parter, Merav
  • Peters, Dominik
  • Pietrzak, Krzysztof
  • Pitassi, Toniann
  • Pogrow, Yosef
  • Potechin, Aaron
  • Prasad, Siddharth
  • Purohit, Manish
  • Qiang, Ruixin
  • Ramnarayan, Govind
  • Rao, Sankeerth
  • Raskhodnikova, Sofya
  • Rau, Malin
  • Ray, Maharshi
  • Reingold, Omer
  • Richelson, Silas
  • Robere, Robert
  • Rohwedder, Lars
  • Ron, Dana
  • Ron-Zewi, Noga
  • Rosén, Adi
  • Rubinfeld, Ronitt
  • Safavi-Naini, Reihaneh
  • Saig, Eden
  • Santha, Miklos
  • Santhanam, Rahul
  • Schild, Aaron
  • Schneider, Jon
  • Schramm, Tselil
  • Servedio, Rocco A.
  • Seshadhri, C.
  • Shadravan, Mohammad
  • Shinkar, Igor
  • Shraibman, Adi
  • Sinclair, Alistair
  • Sokolov, Dmitry
  • Srinivasan, Srikanth
  • Srivastava, Piyush
  • Stein, Cliff
  • Steurer, David
  • Sudan, Madhu
  • Svitkina, Zoya
  • Tal, Avishay
  • Tell, Roei
  • Teng, Shang-Hua
  • Trejo Nuñez, Adrian
  • Urrutia, Florent
  • Vaikuntanathan, Vinod
  • Vakilian, Ali
  • Varma, Nithin
  • Vasudevan, Prashant Nalini
  • Vazirani, Umesh
  • Vee, Erik
  • Vempala, Santosh S.
  • Vinci, Cosimo
  • Waingarten, Erik
  • Wang, Huaxiong
  • Wang, Ruosong
  • Weinberg, S. Matthew
  • Wigderson, Avi
  • Williams, Richard Ryan
  • Wu, Xinyu
  • Yehudayoff, Amir
  • Yodpinyanee, Anak
  • Zhang, Hanrui
  • Zhou, Leo
  • Zwicker, William S.
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Blum, Avrim

    Abstract | Document (364 KB) | BibTeX

    Submodular Secretary Problem with Shortlists
    Authors: Agrawal, Shipra ; Shadravan, Mohammad ; Stein, Cliff

    Abstract | Document (612 KB) | BibTeX

    Hamiltonian Sparsification and Gap-Simulation
    Authors: Aharonov, Dorit ; Zhou, Leo

    Abstract | Document (776 KB) | BibTeX

    On Solving Linear Systems in Sublinear Time
    Authors: Andoni, Alexandr ; Krauthgamer, Robert ; Pogrow, Yosef

    Abstract | Document (591 KB) | BibTeX

    Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
    Authors: Applebaum, Benny ; Vasudevan, Prashant Nalini

    Abstract | Document (466 KB) | BibTeX

    Bitcoin: A Natural Oligopoly
    Authors: Arnosti, Nick ; Weinberg, S. Matthew

    Abstract | Document (264 KB) | BibTeX

    A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
    Authors: Assadi, Sepehr ; Kapralov, Michael ; Khanna, Sanjeev

    Abstract | Document (564 KB) | BibTeX

    Tensor Network Complexity of Multilinear Maps
    Authors: Austrin, Per ; Kaski, Petteri ; Kubjas, Kaie

    Abstract | Document (667 KB) | BibTeX

    A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates
    Authors: Bajpai, Swapnam ; Krishan, Vaibhav ; Kush, Deepanshu ; Limaye, Nutan ; Srinivasan, Srikanth

    Abstract | Document (609 KB) | BibTeX

    Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
    Authors: Barak, Boaz ; Kothari, Pravesh K. ; Steurer, David

    Abstract | Document (498 KB) | BibTeX

    Algorithms, Bounds, and Strategies for Entangled XOR Games
    Authors: Bene Watts, Adam ; Harrow, Aram W. ; Kanwar, Gurtej ; Natarajan, Anand

    Abstract | Document (538 KB) | BibTeX

    Testing Local Properties of Arrays
    Authors: Ben-Eliezer, Omri

    Abstract | Document (464 KB) | BibTeX

    The Complexity of User Retention
    Authors: Ben-Sasson, Eli ; Saig, Eden

    Abstract | Document (524 KB) | BibTeX

    Torus Polynomials: An Algebraic Approach to ACC Lower Bounds
    Authors: Bhrushundi, Abhishek ; Hosseini, Kaave ; Lovett, Shachar ; Rao, Sankeerth

    Abstract | Document (482 KB) | BibTeX

    Almost Envy-Free Allocations with Connected Bundles
    Authors: Bilò, Vittorio ; Caragiannis, Ioannis ; Flammini, Michele ; Igarashi, Ayumi ; Monaco, Gianpiero ; Peters, Dominik ; Vinci, Cosimo ; Zwicker, William S.

    Abstract | Document (512 KB) | BibTeX

    "Quantum Supremacy" and the Complexity of Random Circuit Sampling
    Authors: Bouland, Adam ; Fefferman, Bill ; Nirkhe, Chinmay ; Vazirani, Umesh

    Abstract | Document (215 KB) | BibTeX

    Adversarially Robust Property-Preserving Hash Functions
    Authors: Boyle, Elette ; LaVigne, Rio ; Vaikuntanathan, Vinod

    Abstract | Document (621 KB) | BibTeX

    On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
    Authors: C. S., Karthik ; Manurangsi, Pasin

    Abstract | Document (559 KB) | BibTeX

    Expander-Based Cryptography Meets Natural Proofs
    Authors: Carboni Oliveira, Igor ; Santhanam, Rahul ; Tell, Roei

    Abstract | Document (527 KB) | BibTeX

    A Note on the Quantum Query Complexity of Permutation Symmetric Functions
    Authors: Chailloux, André

    Abstract | Document (395 KB) | BibTeX

    Adaptive Boolean Monotonicity Testing in Total Influence Time
    Authors: Chakrabarty, Deeparnab ; Seshadhri, C.

    Abstract | Document (407 KB) | BibTeX

    On Locality-Sensitive Orderings and Their Applications
    Authors: Chan, Timothy M. ; Har-Peled, Sariel ; Jones, Mitchell

    Abstract | Document (564 KB) | BibTeX

    Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
    Authors: Chattopadhyay, Eshan ; Hatami, Pooya ; Lovett, Shachar ; Tal, Avishay

    Abstract | Document (563 KB) | BibTeX

    Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
    Authors: Chen, Lijie ; Wang, Ruosong

    Abstract | Document (623 KB) | BibTeX

    Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity
    Authors: Chen, Wei ; Teng, Shang-Hua ; Zhang, Hanrui

    Abstract | Document (582 KB) | BibTeX

    Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing
    Authors: Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

    Abstract | Document (535 KB) | BibTeX

    On the Algorithmic Power of Spiking Neural Networks
    Authors: Chou, Chi-Ning ; Chung, Kai-Min ; Lu, Chi-Jen

    Abstract | Document (1,527 KB) | BibTeX

    Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
    Authors: Daskalakis, Constantinos ; Panageas, Ioannis

    Abstract | Document (631 KB) | BibTeX

    Density Estimation for Shift-Invariant Multidimensional Distributions
    Authors: De, Anindya ; Long, Philip M. ; Servedio, Rocco A.

    Abstract | Document (631 KB) | BibTeX

    From Local to Robust Testing via Agreement Testing
    Authors: Dinur, Irit ; Harsha, Prahladh ; Kaufman, Tali ; Ron-Zewi, Noga

    Abstract | Document (494 KB) | BibTeX

    Every Set in P Is Strongly Testable Under a Suitable Encoding
    Authors: Dinur, Irit ; Goldreich, Oded ; Gur, Tom

    Abstract | Document (573 KB) | BibTeX

    Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice
    Authors: Dughmi, Shaddin ; Kempe, David ; Qiang, Ruixin

    Abstract | Document (661 KB) | BibTeX

    Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
    Authors: Dvir, Zeev ; Gopi, Sivakanth ; Gu, Yuzhou ; Wigderson, Avi

    Abstract | Document (578 KB) | BibTeX

    Fairness Under Composition
    Authors: Dwork, Cynthia ; Ilvento, Christina

    Abstract | Document (613 KB) | BibTeX

    A Log-Sobolev Inequality for the Multislice, with Applications
    Authors: Filmus, Yuval ; O'Donnell, Ryan ; Wu, Xinyu

    Abstract | Document (475 KB) | BibTeX

    Cubic Formula Size Lower Bounds Based on Compositions with Majority
    Authors: Gál, Anna ; Tal, Avishay ; Trejo Nuñez, Adrian

    Abstract | Document (470 KB) | BibTeX

    The Space Complexity of Mirror Games
    Authors: Garg, Sumegha ; Schneider, Jon

    Abstract | Document (396 KB) | BibTeX

    The Subgraph Testing Model
    Authors: Goldreich, Oded ; Ron, Dana

    Abstract | Document (448 KB) | BibTeX

    Adventures in Monotone Complexity and TFNP
    Authors: Göös, Mika ; Kamath, Pritish ; Robere, Robert ; Sokolov, Dmitry

    Abstract | Document (791 KB) | BibTeX

    Algorithmic Polarization for Hidden Markov Models
    Authors: Guruswami, Venkatesan ; Nakkiran, Preetum ; Sudan, Madhu

    Abstract | Document (638 KB) | BibTeX

    On the Communication Complexity of Key-Agreement Protocols
    Authors: Haitner, Iftach ; Mazor, Noam ; Oshman, Rotem ; Reingold, Omer ; Yehudayoff, Amir

    Abstract | Document (517 KB) | BibTeX

    The Paulsen Problem Made Simple
    Authors: Hamilton, Linus ; Moitra, Ankur

    Abstract | Document (373 KB) | BibTeX

    How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts
    Authors: Horel, Thibaut ; Park, Sunoo ; Richelson, Silas ; Vaikuntanathan, Vinod

    Abstract | Document (607 KB) | BibTeX

    On Integer Programming and Convolution
    Authors: Jansen, Klaus ; Rohwedder, Lars

    Abstract | Document (473 KB) | BibTeX

    Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times
    Authors: Jansen, Klaus ; Klein, Kim-Manuel ; Maack, Marten ; Rau, Malin

    Abstract | Document (472 KB) | BibTeX

    Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
    Authors: Jin, Yan ; Mossel, Elchanan ; Ramnarayan, Govind

    Abstract | Document (469 KB) | BibTeX

    Simulating Random Walks on Graphs in the Streaming Model
    Authors: Jin, Ce

    Abstract | Document (504 KB) | BibTeX

    On the Complexity of Symmetric Polynomials
    Authors: Bläser, Markus ; Jindal, Gorav

    Abstract | Document (481 KB) | BibTeX

    The Orthogonal Vectors Conjecture for Branching Programs and Formulas
    Authors: Kane, Daniel M. ; Williams, Richard Ryan

    Abstract | Document (521 KB) | BibTeX

    SOS Lower Bounds with Hard Constraints: Think Global, Act Local
    Authors: Kothari, Pravesh K. ; O'Donnell, Ryan ; Schramm, Tselil

    Abstract | Document (570 KB) | BibTeX

    Semi-Online Bipartite Matching
    Authors: Kumar, Ravi ; Purohit, Manish ; Schild, Aaron ; Svitkina, Zoya ; Vee, Erik

    Abstract | Document (562 KB) | BibTeX

    Strategies for Quantum Races
    Authors: Lee, Troy ; Ray, Maharshi ; Santha, Miklos

    Abstract | Document (492 KB) | BibTeX

    Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
    Authors: Levi, Amit ; Waingarten, Erik

    Abstract | Document (644 KB) | BibTeX

    Secret Sharing with Binary Shares
    Authors: Lin, Fuchun ; Cheraghchi, Mahdi ; Guruswami, Venkatesan ; Safavi-Naini, Reihaneh ; Wang, Huaxiong

    Abstract | Document (531 KB) | BibTeX

    On the Communication Complexity of High-Dimensional Permutations
    Authors: Linial, Nati ; Pitassi, Toniann ; Shraibman, Adi

    Abstract | Document (580 KB) | BibTeX

    Fisher Zeros and Correlation Decay in the Ising Model
    Authors: Liu, Jingcheng ; Sinclair, Alistair ; Srivastava, Piyush

    Abstract | Document (411 KB) | BibTeX

    Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
    Authors: McKay, Dylan M. ; Williams, Richard Ryan

    Abstract | Document (556 KB) | BibTeX

    Random Projection in the Brain and Computation with Assemblies of Neurons
    Authors: Papadimitriou, Christos H. ; Vempala, Santosh S.

    Abstract | Document (690 KB) | BibTeX

    Local Computation Algorithms for Spanners
    Authors: Parter, Merav ; Rubinfeld, Ronitt ; Vakilian, Ali ; Yodpinyanee, Anak

    Abstract | Document (1,256 KB) | BibTeX

    Proofs of Catalytic Space
    Authors: Pietrzak, Krzysztof

    Abstract | Document (804 KB) | BibTeX

    Simple Verifiable Delay Functions
    Authors: Pietrzak, Krzysztof

    Abstract | Document (546 KB) | BibTeX

    Sum of Squares Lower Bounds from Symmetry and a Good Story
    Authors: Potechin, Aaron

    Abstract | Document (431 KB) | BibTeX

    Learning Time Dependent Choice
    Authors: Chase, Zachary ; Prasad, Siddharth

    Abstract | Document (480 KB) | BibTeX

    Erasures vs. Errors in Local Decoding and Property Testing
    Authors: Raskhodnikova, Sofya ; Ron-Zewi, Noga ; Varma, Nithin

    Abstract | Document (523 KB) | BibTeX

    A New Approach to Multi-Party Peer-to-Peer Communication Complexity
    Authors: Rosén, Adi ; Urrutia, Florent

    Abstract | Document (498 KB) | BibTeX

    A Schur Complement Cheeger Inequality
    Authors: Schild, Aaron

    Abstract | Document (585 KB) | BibTeX

    Game Efficiency Through Linear Programming Duality
    Authors: Kim Thang, Nguyen

    Abstract | Document (491 KB) | BibTeX

    		  



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