Portal - ITCS 2020

ITCS 2020	January 12-14, 2020, Seattle, Washington, USA
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) Thomas Vidick (Ed.)
ISBN 978-3-95977-134-4, LIPICS Vol. 151	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 62 MB)
Search Publication Server

Authors

Agrawal, Shweta

Aliakbarpour, Maryam

Alman, Josh

Ameri, Mohammad Hassan

Biswas, Amartya Shankha

Budkuley, Amitalok J.

Georgakopoulos, Agelos

Hendrickson, Dylan H.

Hershkowitz, D. Ellis

Makarychev, Konstantin

Mitzenmacher, Michael

Natarajan Ramamoorthy, Sivaramakrishnan

Papadimitriou, Christos

Sharifi-Malvajerdi, Saeed

Srinivasan, Akshayaram

Vaikuntanathan, Vinod

Vasilyan, Arsen

Vassilevska Williams, Virginia

Vasudevan, Prashant Nalini

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Vidick, Thomas

Abstract | Document (369 KB) | BibTeX

Hardness Amplification of Optimization Problems

Authors: Goldenberg, Elazar ; Karthik C. S.,

Abstract | Document (473 KB) | BibTeX

Smooth and Strong PCPs

Authors: Paradise, Orr

Abstract | Document (791 KB) | BibTeX

Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence

Authors: Schvartzman, Ariel ; Weinberg, S. Matthew ; Zlatin, Eitan ; Zuo, Albert

Abstract | Document (822 KB) | BibTeX

Span Programs and Quantum Space Complexity

Authors: Jeffery, Stacey

Abstract | Document (639 KB) | BibTeX

DEEP-FRI: Sampling Outside the Box Improves Soundness

Authors: Ben-Sasson, Eli ; Goldberg, Lior ; Kopparty, Swastik ; Saraf, Shubhangi

Abstract | Document (711 KB) | BibTeX

On the Cryptographic Hardness of Local Search

Authors: Bitansky, Nir ; Gerichter, Idan

Abstract | Document (680 KB) | BibTeX

Interactive Coding with Constant Round and Communication Blowup

Authors: Efremenko, Klim ; Haramaty, Elad ; Kalai, Yael Tauman

Abstract | Document (647 KB) | BibTeX

From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces

Authors: Bei, Xiaohui ; Chen, Shiteng ; Guan, Ji ; Qiao, Youming ; Sun, Xiaoming

Abstract | Document (770 KB) | BibTeX

Hard Properties with (Very) Short PCPPs and Their Applications

Authors: Ben-Eliezer, Omri ; Fischer, Eldar ; Levi, Amit ; Rothblum, Ron D.

Abstract | Document (715 KB) | BibTeX

Kronecker Powers of Tensors and Strassen’s Laser Method

Authors: Conner, Austin ; Landsberg, Joseph M. ; Gesmundo, Fulvio ; Ventura, Emanuele

Abstract | Document (690 KB) | BibTeX

Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs

Authors: Lincoln, Andrea ; Vyas, Nikhil

Abstract | Document (584 KB) | BibTeX

High-Dimensional Expanders from Expanders

Authors: Liu, Siqi ; Mohanty, Sidhanth ; Yang, Elizabeth

Abstract | Document (1,004 KB) | BibTeX

Approximating Cumulative Pebbling Cost Is Unique Games Hard

Authors: Blocki, Jeremiah ; Lee, Seunghoon ; Zhou, Samson

Abstract | Document (744 KB) | BibTeX

Scheduling with Predictions and the Price of Misprediction

Authors: Mitzenmacher, Michael

Abstract | Document (448 KB) | BibTeX

Reducing Inefficiency in Carbon Auctions with Imperfect Competition

Authors: Goldner, Kira ; Immorlica, Nicole ; Lucier, Brendan

Abstract | Document (744 KB) | BibTeX

Preference-Informed Fairness

Authors: Kim, Michael P. ; Korolova, Aleksandra ; Rothblum, Guy N. ; Yona, Gal

Abstract | Document (577 KB) | BibTeX

On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H

Authors: Cai, Jin-Yi ; Govorov, Artem

Abstract | Document (546 KB) | BibTeX

Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria

Authors: Etessami, Kousha ; Papadimitriou, Christos ; Rubinstein, Aviad ; Yannakakis, Mihalis

Abstract | Document (636 KB) | BibTeX

Resolution with Counting: Dag-Like Lower Bounds and Different Moduli

Authors: Part, Fedor ; Tzameret, Iddo

Abstract | Document (809 KB) | BibTeX

The Random-Query Model and the Memory-Bounded Coupon Collector

Authors: Raz, Ran ; Zhan, Wei

Abstract | Document (430 KB) | BibTeX

Strategy-Stealing Is Non-Constructive

Authors: Bodwin, Greg ; Grossman, Ofer

Abstract | Document (537 KB) | BibTeX

Distribution-Free Testing of Linear Functions on ℝⁿ

Authors: Fleming, Noah ; Yoshida, Yuichi

Abstract | Document (586 KB) | BibTeX

Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks

Authors: Hitron, Yael ; Lynch, Nancy ; Musco, Cameron ; Parter, Merav

Abstract | Document (1,761 KB) | BibTeX

Signed Tropical Convexity

Authors: Loho, Georg ; Végh, László A.

Abstract | Document (681 KB) | BibTeX

Distributional Property Testing in a Quantum World

Authors: Gilyén, András ; Li, Tongyang

Abstract | Document (691 KB) | BibTeX

On Local Testability in the Non-Signaling Setting

Authors: Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

Abstract | Document (722 KB) | BibTeX

Local Access to Huge Random Objects Through Partial Sampling

Authors: Biswas, Amartya Shankha ; Rubinfeld, Ronitt ; Yodpinyanee, Anak

Abstract | Document (1,427 KB) | BibTeX

Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples

Authors: Rubinfeld, Ronitt ; Vasilyan, Arsen

Abstract | Document (668 KB) | BibTeX

Sample Complexity Bounds for Influence Maximization

Authors: Sadeh, Gal ; Cohen, Edith ; Kaplan, Haim

Abstract | Document (784 KB) | BibTeX

On Oblivious Amplification of Coin-Tossing Protocols

Authors: Bitansky, Nir ; Geier, Nathan

Abstract | Document (484 KB) | BibTeX

A New Analysis of Differential Privacy’s Generalization Guarantees

Authors: Jung, Christopher ; Ligett, Katrina ; Neel, Seth ; Roth, Aaron ; Sharifi-Malvajerdi, Saeed ; Shenfeld, Moshe

Abstract | Document (526 KB) | BibTeX

Robust Algorithms for the Secretary Problem

Authors: Bradac, Domagoj ; Gupta, Anupam ; Singla, Sahil ; Zuzic, Goran

Abstract | Document (646 KB) | BibTeX

Universal Communication, Universal Graphs, and Graph Labeling

Authors: Harms, Nathaniel

Abstract | Document (621 KB) | BibTeX

Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]

Authors: Ilango, Rahul

Abstract | Document (684 KB) | BibTeX

Equivalence of Systematic Linear Data Structures and Matrix Rigidity

Authors: Natarajan Ramamoorthy, Sivaramakrishnan ; Rashtchian, Cyrus

Abstract | Document (592 KB) | BibTeX

Computationally Data-Independent Memory Hard Functions

Authors: Ameri, Mohammad Hassan ; Blocki, Jeremiah ; Zhou, Samson

Abstract | Document (669 KB) | BibTeX

Learning and Testing Variable Partitions

Authors: Bogdanov, Andrej ; Wang, Baoxiang

Abstract | Document (9,662 KB) | BibTeX

Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six

Authors: Bera, Suman K. ; Pashanasangi, Noujan ; Seshadhri, C.

Abstract | Document (615 KB) | BibTeX

Parameterization Above a Multiplicative Guarantee

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (738 KB) | BibTeX

Ad Hoc Multi-Input Functional Encryption

Authors: Agrawal, Shweta ; Clear, Michael ; Frieder, Ophir ; Garg, Sanjam ; O'Neill, Adam ; Thaler, Justin

Abstract | Document (845 KB) | BibTeX

Unexpected Power of Random Strings

Authors: Hirahara, Shuichi

Abstract | Document (509 KB) | BibTeX

Consensus vs Broadcast, with and Without Noise (Extended Abstract)

Authors: Clementi, Andrea ; Gualà, Luciano ; Natale, Emanuele ; Pasquale, Francesco ; Scornavacca, Giacomo ; Trevisan, Luca

Abstract | Document (532 KB) | BibTeX

Testing Linear Inequalities of Subgraph Statistics

Authors: Gishboliner, Lior ; Shapira, Asaf ; Stagni, Henrique

Abstract | Document (431 KB) | BibTeX

Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations

Authors: Blanc, Guy ; Lange, Jane ; Tan, Li-Yang

Abstract | Document (851 KB) | BibTeX

Algorithms and Adaptivity Gaps for Stochastic k-TSP

Authors: Jiang, Haotian ; Li, Jian ; Liu, Daogao ; Singla, Sahil

Abstract | Document (666 KB) | BibTeX

Strategic Payments in Financial Networks

Authors: Bertschinger, Nils ; Hoefer, Martin ; Schmand, Daniel

Abstract | Document (536 KB) | BibTeX

Fault Tolerant Subgraphs with Applications in Kernelization

Authors: Lochet, William ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

Abstract | Document (969 KB) | BibTeX

The Computational Cost of Asynchronous Neural Communication

Authors: Hitron, Yael ; Parter, Merav ; Perri, Gur

Abstract | Document (2,208 KB) | BibTeX

Certified Algorithms: Worst-Case Analysis and Beyond

Authors: Makarychev, Konstantin ; Makarychev, Yury

Abstract | Document (488 KB) | BibTeX

Low Diameter Graph Decompositions by Approximate Distance Computation

Authors: Becker, Ruben ; Emek, Yuval ; Lenzen, Christoph

Abstract | Document (710 KB) | BibTeX

Generalized List Decoding

Authors: Zhang, Yihan ; Budkuley, Amitalok J. ; Jaggi, Sidharth

Abstract | Document (1,239 KB) | BibTeX

Online Computation with Untrusted Advice

Authors: Angelopoulos, Spyros ; Dürr, Christoph ; Jin, Shendan ; Kamali, Shahin ; Renault, Marc

Abstract | Document (462 KB) | BibTeX

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions

Authors: Lincoln, Andrea ; Polak, Adam ; Vassilevska Williams, Virginia

Abstract | Document (542 KB) | BibTeX

Matching Is as Easy as the Decision Problem, in the NC Model

Authors: Anari, Nima ; Vazirani, Vijay V.

Abstract | Document (584 KB) | BibTeX

Advancing Subgroup Fairness via Sleeping Experts

Authors: Blum, Avrim ; Lykouris, Thodoris

Abstract | Document (567 KB) | BibTeX

Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Authors: Grossman, Tomer ; Komargodski, Ilan ; Naor, Moni

Abstract | Document (810 KB) | BibTeX

On the Impossibility of Probabilistic Proofs in Relativized Worlds

Authors: Chiesa, Alessandro ; Liu, Siqi

Abstract | Document (722 KB) | BibTeX

Lower Bounds for (Non-Monotone) Comparator Circuits

Authors: Gál, Anna ; Robere, Robert

Abstract | Document (468 KB) | BibTeX

A Tight Lower Bound For Non-Coherent Index Erasure

Authors: Lindzey, Nathan ; Rosmanis, Ansis

Abstract | Document (726 KB) | BibTeX

Optimal Single-Choice Prophet Inequalities from Samples

Authors: Rubinstein, Aviad ; Wang, Jack Z. ; Weinberg, S. Matthew

Abstract | Document (459 KB) | BibTeX

Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard

Authors: Cai, Linda ; Thomas, Clay ; Weinberg, S. Matthew

Abstract | Document (687 KB) | BibTeX

Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard

Authors: Demaine, Erik D. ; Hendrickson, Dylan H. ; Lynch, Jayson

Abstract | Document (1,423 KB) | BibTeX

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)

Authors: Bouland, Adam ; Fefferman, Bill ; Vazirani, Umesh

Abstract | Document (204 KB) | BibTeX

New Query Lower Bounds for Submodular Function Minimization

Authors: Graur, Andrei ; Pollner, Tristan ; Ramaswamy, Vidhya ; Weinberg, S. Matthew

Abstract | Document (536 KB) | BibTeX

Computation-Aware Data Aggregation

Authors: Haeupler, Bernhard ; Hershkowitz, D. Ellis ; Kahng, Anson ; Procaccia, Ariel D.

Abstract | Document (995 KB) | BibTeX

Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage

Authors: Maturana, Francisco ; Rashmi, K. V.

Abstract | Document (688 KB) | BibTeX

Incentive Compatible Active Learning

Authors: Echenique, Federico ; Prasad, Siddharth

Abstract | Document (523 KB) | BibTeX

Pseudorandomness and the Minimum Circuit Size Problem

Authors: Santhanam, Rahul

Abstract | Document (572 KB) | BibTeX

Testing Properties of Multiple Distributions with Few Samples

Authors: Aliakbarpour, Maryam ; Silwal, Sandeep

Abstract | Document (705 KB) | BibTeX

Beyond Natural Proofs: Hardness Magnification and Locality

Authors: Chen, Lijie ; Hirahara, Shuichi ; Oliveira, Igor C. ; Pich, Ján ; Rajgopal, Ninad ; Santhanam, Rahul

Abstract | Document (883 KB) | BibTeX

Separating Two-Round Secure Computation From Oblivious Transfer

Authors: Applebaum, Benny ; Brakerski, Zvika ; Garg, Sanjam ; Ishai, Yuval ; Srinivasan, Akshayaram

Abstract | Document (517 KB) | BibTeX

Trade-Offs Between Size and Degree in Polynomial Calculus

Authors: Lagarde, Guillaume ; Nordström, Jakob ; Sokolov, Dmitry ; Swernofsky, Joseph

Abstract | Document (543 KB) | BibTeX

Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Authors: Boodaghians, Shant ; Kulkarni, Rucha ; Mehta, Ruta

Abstract | Document (509 KB) | BibTeX

Local-To-Global Agreement Expansion via the Variance Method

Authors: Kaufman, Tali ; Mass, David

Abstract | Document (470 KB) | BibTeX

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture

Authors: Chan, T-H. Hubert ; Chung, Kai-Min ; Lin, Wei-Kai ; Shi, Elaine

Abstract | Document (854 KB) | BibTeX

Choice and Bias in Random Walks

Authors: Georgakopoulos, Agelos ; Haslegrave, John ; Sauerwald, Thomas ; Sylvester, John

Abstract | Document (642 KB) | BibTeX

Graph Spanners in the Message-Passing Model

Authors: Fernández V, Manuel ; Woodruff, David P. ; Yasuda, Taisuke

Abstract | Document (515 KB) | BibTeX

Computational Hardness of Certifying Bounds on Constrained PCA Problems

Authors: Bandeira, Afonso S. ; Kunisky, Dmitriy ; Wein, Alexander S.

Abstract | Document (640 KB) | BibTeX

Pseudo-Deterministic Streaming

Authors: Goldwasser, Shafi ; Grossman, Ofer ; Mohanty, Sidhanth ; Woodruff, David P.

Abstract | Document (636 KB) | BibTeX

Limits to Non-Malleability

Authors: Ball, Marshall ; Dachman-Soled, Dana ; Kulkarni, Mukul ; Malkin, Tal

Abstract | Document (680 KB) | BibTeX

Cryptography from Information Loss

Authors: Ball, Marshall ; Boyle, Elette ; Degwekar, Akshay ; Deshpande, Apoorvaa ; Rosen, Alon ; Vaikuntanathan, Vinod ; Vasudevan, Prashant Nalini

Abstract | Document (621 KB) | BibTeX

Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

Authors: Bartusek, James ; Ishai, Yuval ; Jain, Aayush ; Ma, Fermi ; Sahai, Amit ; Zhandry, Mark

Abstract | Document (767 KB) | BibTeX

OV Graphs Are (Probably) Hard Instances

Authors: Alman, Josh ; Vassilevska Williams, Virginia

Abstract | Document (537 KB) | BibTeX

Finding Skewed Subcubes Under a Distribution

Authors: Gopalan, Parikshit ; Levin, Roie ; Wieder, Udi

Abstract | Document (661 KB) | BibTeX

Combinatorial Lower Bounds for 3-Query LDCs

Authors: Bhattacharyya, Arnab ; Chandran, L. Sunil ; Ghoshal, Suprovat

Abstract | Document (479 KB) | BibTeX

On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?

Authors: Ball, Marshall ; Holmgren, Justin ; Ishai, Yuval ; Liu, Tianren ; Malkin, Tal

Abstract | Document (650 KB) | BibTeX

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

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)