ITCS 2019 Accepted Papers

Irit Dinur, Oded Goldreich and Tom Gur. Every set in P is strongly testable under a suitable encoding
Wei Chen, Shang-Hua Teng and Hanrui Zhang. Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity
Thibaut Horel, Sunoo Park, Silas Richelson and Vinod Vaikuntanathan. How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts
Pravesh Kothari, Ryan O'Donnell and Tselil Schramm. SOS lower bounds with hard constraints: think global, act local
Alexandr Andoni, Robert Krauthgamer and Yosef Pogrow. On Solving Linear Systems in Sublinear Time
Cynthia Dwork and Christina Ilvento. Fairness Under Composition
Klaus Jansen, Kim-Manuel Klein, Marten Maack and Malin Rau. Empowering the Configuration-IP – New PTAS Results for Scheduling with Setups Times
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett and Sankeerth Rao. Torus polynomials: an algebraic approach to ACC lower bounds
Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci and William S Zwicker. Almost Envy-Free Allocations with Connected Bundles
Adi Rosén and Florent Urrutia. A New Approach to Multi-Party Peer-to-Peer Communication Complexity
Deeparnab Chakrabarty and C. Seshadhri. Adaptive Boolean Monotonicity Testing in Total Influence Time
Constantinos Daskalakis and Ioannis Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
Anindya De, Phil Long and Rocco Servedio. Density estimation for shift-invariant multidimensional distributions
Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution
Gorav Jindal and Markus Blaeser. On the Complexity of Symmetric Polynomials
Per Austrin, Petteri Kaski and Kaie Kubjas. Tensor network complexity of multilinear maps
Omri Ben-Eliezer. Testing local properties of arrays
Ce Jin. Simulating Random Walks on Graphs in the Streaming Model
Linus Hamilton and Ankur Moitra. The Paulsen Problem Made Simple
Amit Levi and Erik Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
Jingcheng Liu, Alistair Sinclair and Piyush Srivastava. Fisher zeros and correlation decay in the Ising model
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett and Avishay Tal. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates
Irit Dinur, Prahladh Harsha, Tali Kaufman and Noga Ron-Zewi. From Local Testing to Robust Testing via Agreement Testing
Merav Parter, Ronitt Rubinfeld, Ali Vakilian and Anak Yodpinyanee. Local Computation Algorithms for Spanners
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu and Avi Wigderson. Spanoids - an abstraction of spanning structures
Alessandro Chiesa, Peter Manohar and Igor Shinkar. Probabilistic Checking against Non-Signaling Strategies from Linearity Testing
Anna Gal, Avishay Tal and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority
Kim Thang Nguyen. Game Efficiency through Linear Programming Duality
Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani. "Quantum Supremacy" and the Complexity of Random Circuit Sampling
Troy Lee, Maharshi Ray and Miklos Santha. Strategies for quantum races
Oded Goldreich and Dana Ron. The Subgraph Testing Model
André Chailloux. A note on the quantum query complexity of permutation symmetric functions
Krzysztof Pietrzak. Simple Verifiable Delay Functions
Yuval Filmus, Ryan O'Donnell and Xinyu Wu. A log-Sobolev inequality for the multislice, with applications
Elette Boyle, Rio LaVigne and Vinod Vaikuntanathan. Adversarially Robust Property Preserving Hash Functions
Mika Göös, Pritish Kamath, Robert Robere and Dmitry Sokolov. Adventures in Monotone Complexity and TFNP
Christos Papadimitriou and Santosh Vempala. Random Projection in the Brain and Computation with Assemblies of Neurons
Nick Arnosti and S. Matthew Weinberg. Bitcoin: A Natural Oligopoly
Shipra Agrawal, Mohammad Shadravan and Clifford Stein. Submodular Secretary Problem with Shortlists
Sepehr Assadi, Michael Kapralov and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Timothy Chan, Sariel Har-Peled and Mitchell Jones. On Locality-Sensitive Orderings and Their Applications
Benny Applebaum and Prashant Nalini Vasudevan. Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
Eli Ben-Sasson and Eden Saig. The Complexity of User Retention
Aaron Potechin. Sum of squares lower bounds from symmetry and a good story
Krzysztof Pietrzak. Proofs of Catalytic Space
Venkatesan Guruswami, Preetum Nakkiran and Madhu Sudan. Algorithmic Polarization for Hidden Markov Models
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold and Amir Yehudayoff. On the Communication Complexity of Key-Agreement Protocols
Siddharth Prasad and Zachary Chase. Learning Time Dependent Choice
Sumegha Garg and Jon Schneider. The Space Complexity of Mirror Games
Boaz Barak, Pravesh Kothari and David Steurer. Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Nati Linial, Toniann Pitassi and Adi Shraibman. On the Communication Complexity of High Dimensional Permutations
Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reyhaneh Safavi-Naini and Huaxiong Wang. Secret Sharing with Binary Shares
Shaddin Dughmi, David Kempe and Ruixin Qiang. Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice
Adam Bene Watts, Aram Harrow, Gurtej Kanwar and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games
Daniel Kane and Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Dylan McKay and Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions With a Random Oracle
Igor Carboni Oliveira, Rahul Santhanam and Roei Tell. Expander-Based Cryptography Meets Natural Proofs
Lijie Chen and Ruosong Wang. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
Karthik C. S. and Pasin Manurangsi. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Yan Jin, Elchanan Mossel and Govind Ramnarayan. Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
Aaron Schild. A Schur Complement Cheeger Inequality
Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina and Erik Vee. Semi-Online Bipartite Matching
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye and Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
Chi-Ning Chou, Kai-Min Chung and Chi-Jen Lu. On the Algorithmic Power of Spiking Neural Networks
Sofya Raskhodnikova, Noga Ron-Zewi and Nithin Varma. Erasures vs. Errors in Local Decoding and Property Testing
Dorit Aharonov and Leo Zhou. Hamiltonian Sparsification and Gap-Simulations