ITCS 2020 Accepted Papers

  • 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
  • Arnab Bhattacharyya; Sunil Chandran; Suprovat Ghoshal. Combinatorial lower bounds for 3-query LDCs
  • 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?