All accepted papers are available in the ITCS'20 proceedings volume published by LIPICS.
Elazar Goldenberg; Karthik C. S.. Hardness Amplification of Optimization Problems
Orr Paradise. Smooth and Strong PCPs
Ariel Schvartzman; S. Matthew Weinberg; Eitan Zlatin; Albert Zuo. Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence
Stacey Jeffery. Span Programs and Quantum Space Complexity
Eli Ben Sasson; Lior Goldberg; Swastik Kopparty; Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness
Nir Bitansky; Idan Gerichter. On the Cryptographic Hardness of Local Search
Klim Efremenko; Elad Haramaty; Yael Kalai. Interactive Coding with Constant Round and Communication Blowup
Xiaohui Bei; Shiteng Chen; Ji Guan; Youming Qiao; Xiaoming Sun. From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: Another bridge between graphs and alternating matrix spaces
Omri Ben-Eliezer; Eldar Fischer; Amit Levi; Ron D. Rothblum. Hard properties with (very) short PCPPs and their applications
Joseph Landsberg; Austin Conner; Fulvio Gesmundo; Emanuele Ventura. Tensors not subject to barriers for Strassen's laser method
Andrea Lincoln; Nikhil Vyas. Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
Siqi Liu; Sidhanth Mohanty; Elizabeth Yang. High-Dimensional Expanders from Expanders
Jeremiah Blocki; Seunghoon Lee; Samson Zhou. Approximating Cumulative Pebbling Cost is Unique Games Hard
Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction
Kira Goldner; Nicole Immorlica; Brendan Lucier. Reducing Inefficiency in Carbon Auctions with Imperfect Competition
Michael P. Kim; Aleksandra Korolova; Guy N. Rothblum; Gal Yona. Preference-Informed Fairness
Jin-Yi Cai; Artsiom Hovarau. On a Theorem of Lov'asz that \(\hom(\cdot, H)\) Determines the Isomorphism Type of \(H\)
Kousha Etessami; Christos Papadimitriou; Aviad Rubinstein; Mihalis Yannakakis. Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
Fedor Part; Iddo Tzameret. Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
Ran Raz; Wei Zhan. The Random-Query Model and the Memory-Bounded Coupon Collector
Greg Bodwin; Ofer Grossman. Strategy-Stealing is Non-Constructive
Noah Fleming; Yuichi Yoshida. Distribution-Free Testing of Linear Functions on \(R^n\)
Yael Hitron; Cameron Musco; Merav Parter; Nancy Lynch. Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks
Georg Loho; László A. Végh. Signed tropical convexity
Andras Pal Gilyen; Tongyang Li. Distributional property testing in a quantum world
Alessandro Chiesa; Peter Manohar; Igor Shinkar. On Local Testability in the Non-Signaling Setting
Amartya Shankha Biswas; Ronitt Rubinfeld; Anak Yodpinyanee. Local Access to Huge Random Objects through Partial Sampling
Ronitt Rubinfeld; Arsen Vasilyan. Monotone probability distributions over the Boolean cube can be learned with sublinear samples
Gal Sadeh; Edith Cohen; Haim Kaplan. Sample Complexity Bounds for Influence Maximization
Nir Bitansky; Nathan Geier. On Oblivious Amplification of Coin-Tossing Protocols
Christopher Jung; Katrina Ligett; Seth Neel; Aaron Roth; Saeed Sharifi-Malvajerdi; Moshe Shenfeld. A New Analysis of Differential Privacy's Generalization Guarantees
Domagoj Bradac; Anupam Gupta; Sahil Singla; Goran Zuzic. Robust Algorithms for the Secretary Problem
Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling
Rahul Ilango. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC0[p]
Sivaramakrishnan Natarajan Ramamoorthy; Cyrus Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity
Mohammad Hassan Ameri; Jeremiah Blocki; Samson Zhou. Computationally Data-Independent Memory Hard Functions
Andrej Bogdanov; Baoxiang Wang. Learning and Testing Variable Partitions
Suman Kalyan Bera; Noujan Pashanasangi; C. Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six
Fedor Fomin; Petr Golovach; Daniel Lokshtanov; Fahad Panolan; Saket Saurabh; Meirav Zehavi. Parameterization Above a Multiplicative Guarantee
Shweta Agrawal; Michael Clear; Sanjam Garg; Adam O'Neill; Justin Thaler; Ophir Frieder. Ad Hoc Multi-Input Functional Encryption
Shuichi Hirahara. Unexpected Power of Random Strings
Andrea Clementi; Luciano Gualá; Emanuele Natale; Francesco Pasquale; Giacomo Scornavacca; Luca Trevisan. Consensus vs Broadcast, with and without Noise
Asaf Shapira; Lior Gishboliner; Henrique Stagni. Testing linear inequalities of subgraph statistics
Guy Blanc; Jane Lange; Li-Yang Tan. Top-down induction of decision trees: rigorous guarantees and inherent limitations
Haotian Jiang; Jian Li; Daogao Liu; Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic k-TSP
Nils Bertschinger; Martin Hoefer; Daniel Schmand. Strategic Payments in Financial Networks
William Lochet; Daniel Lokshtanov; Pranabendu Misra; Saket Saurabh; Roohani Sharma; Meirav Zehavi. Fault Tolerant Subgraphs with Applications in Kernelization
Yael Hitron; Merav Parter; Gur Perri. The Computational Cost of Asynchronous Neural Communication
Konstantin Makarychev; Yury Makarychev. Certified Algorithms: Worst-Case Analysis and Beyond
Ruben Becker; Yuval Emek; Christoph Lenzen. Low Diameter Graph Decompositions by Approximate Distance Computation
Yihan Zhang; Amitalok Jayant Budkuley; Sidharth Jaggi. Generalized List Decoding
Spyros Angelopoulos; Christoph Dürr; Shahin Kamali; Shendan Jin; Marc Renault. Online Computation with Untrusted Advice
Andrea Lincoln; Adam Polak; Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions
Nima Anari; Vijay Vazirani. Matching is as Easy as the Decision Problem, in the NC Model
Avrim Blum; Thodoris Lykouris. Advancing subgroup fairness via sleeping experts
Tomer Grossman; Ilan Komargodski; Moni Naor. Instance Complexity and Unlabeled Certificates in the Decision Tree Model
Alessandro Chiesa; Siqi Liu. On the Impossibility of Probabilistic Proofs in Relativized Worlds
Anna Gál; Robert Robere. Lower Bounds for (Non-monotone) Comparator Circuits
Nathan Lindzey; Ansis Rosmanis. A Tight Lower Bound for Non-Coherent Index Erasure
Aviad Rubinstein; Jack Z. Wang; S. Matthew Weinberg. Optimal Single-Choice Prophet Inequalities from Samples
Clayton Thomas; Linda Cai; S. Matthew Weinberg. Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard
Jayson Lynch; Erik D. Demaine; Dylan Hendrickson. Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard
Adam Bouland; Bill Fefferman; Umesh V. Vazirani. Computational pseudorandomness, Complexity=Volume, and constraints on the AdS/CFT duality
Andrei A. Graur; Tristan Pollner; Vidhya Ramaswamy; S. Matthew Weinberg. New Query Lower Bounds for Submodular Function Minimization
Bernhard Haeupler; D. Ellis Hershkowitz; Anson Kahng; Ariel Procaccia. Computation-Aware Data Aggregation
Francisco Maturana; K. V. Rashmi. Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data
Siddharth Prasad; Federico Echenique. Incentive Compatible Active Learning
Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem
Maryam Aliakbarpour; Sandeep Silwal. Testing Properties of Multiple Distributions with Few Samples
Lijie Chen; Shuichi Hirahara; Igor Oliveira; Jan Pich; Ninad Rajgopal; Rahul Santhanam. Beyond Natural Proofs: Hardness Magnification and Locality
Benny Applebaum; Zvika Brakerski; Sanjam Garg; Yuval Ishai; Akshayaram Srinivasan. Separating Two-Round Secure Computation from Oblivious Transfer
Guillaume Lagarde; Jakob Nordstrom; Dmitry Sokolov; Joseph Swernofsky. Tradeoff Between Size and Degree in Polynomial Calculus
Shant Boodaghians; Rucha Kulkarni; Ruta Mehta. Smoothed Efficient Algorithms and Reductions for Network Coordination Games
David Mass; Tali Kaufman. Local-to-Global Agreement Expansion via The Variance Method
T-H. Hubert Chan; Kai-Min Chung; Wei-Kai Lin; Elaine Shi. MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
Agelos Georgakopoulos; John Haslegrave; Thomas Sauerwald; John Sylvester. Choice and Bias in Random Walks
Manuel Fernandez; David Woodruff; Taisuke Yasuda. Graph Spanners in the Message-Passing Model
Afonso S. Bandeira; Dmitriy Kunisky; Alexander S. Wein. Computational Hardness of Certifying Bounds on Constrained PCA Problems
Shafi Goldwasser; Ofer Grossman; Sidhanth Mohanty; David P. Woodruff. Pseudo-deterministic Streaming
Marshall Ball; Dana Dachman-Soled; Mukul Kulkarni; Tal Malkin. Limits to Non-Malleability
Marshall Ball; Elette Boyle; Akshay Degwekar; Apoorvaa Deshpande; Alon Rosen; Vinod Vaikuntanathan; Prashant Vasudevan. Cryptography from Information Loss
James Bartusek; Yuval Ishai; Aayush Jain; Fermi Ma; Amit Sahai; Mark Zhandry. Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption
Josh Alman; Virginia Vassilevska Williams. OV graphs are (probably) hard instances
Parikshit Gopalan; Roie Levin; Udi Wieder. Finding Skewed Subcubes Under a Distribution
Marshall Ball; Justin Holmgren; Yuval Ishai; Tianren Liu; Tal Malkin. On the Complexity of Decomposable Randomized Encodings, or: How Friendly Can a Garbling-Friendly PRF be?