Portal - ITCS 2021

ITCS 2021	January 6-8, 2021, Virtual Conference
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) James R. Lee (Ed.)
ISBN 978-3-95977-177-1, LIPICS Vol. 185	ISSN 1868-8969

Additional Information

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

Authors

Arunachalam, Srinivasan

Arunachaleswaran, Eshwar Ram

Guruswami, Venkatesan

Kulikov, Alexander S.

Mudigonda, Abhijit S.

Pallavoor, Ramesh Krishnan S.

Papadimitriou, Christos

Saxena, Raghuvansh R.

Zadimoghaddam, Morteza

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Lee, James R.

Abstract | Document (341 KB) | BibTeX

The Entropy of Lies: Playing Twenty Questions with a Liar

Authors: Dagan, Yuval ; Filmus, Yuval ; Kane, Daniel ; Moran, Shay

Abstract | Document (498 KB) | BibTeX

Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)

Authors: Impagliazzo, Russell ; McGuire, Sam

Abstract | Document (568 KB) | BibTeX

Algorithmic Persuasion with Evidence

Authors: Hoefer, Martin ; Manurangsi, Pasin ; Psomas, Alexandros

Abstract | Document (606 KB) | BibTeX

The Complexity of Finding Fair Independent Sets in Cycles

Authors: Haviv, Ishay

Abstract | Document (514 KB) | BibTeX

Sharp Threshold Rates for Random Codes

Authors: Guruswami, Venkatesan ; Mosheiff, Jonathan ; Resch, Nicolas ; Silas, Shashwat ; Wootters, Mary

Abstract | Document (548 KB) | BibTeX

Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation

Authors: Musco, Cameron ; Musco, Christopher ; Woodruff, David P.

Abstract | Document (565 KB) | BibTeX

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Authors: Hoza, William M. ; Pyne, Edward ; Vadhan, Salil

Abstract | Document (622 KB) | BibTeX

Pipeline Interventions

Authors: Arunachaleswaran, Eshwar Ram ; Kannan, Sampath ; Roth, Aaron ; Ziani, Juba

Abstract | Document (550 KB) | BibTeX

A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits

Authors: Kumar, Mrinal ; Volk, Ben Lee

Abstract | Document (497 KB) | BibTeX

The Strongish Planted Clique Hypothesis and Its Consequences

Authors: Manurangsi, Pasin ; Rubinstein, Aviad ; Schramm, Tselil

Abstract | Document (582 KB) | BibTeX

Sample Efficient Identity Testing and Independence Testing of Quantum States

Authors: Yu, Nengkun

Abstract | Document (627 KB) | BibTeX

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

Authors: Beyersdorff, Olaf ; Böhm, Benjamin

Abstract | Document (680 KB) | BibTeX

The Quantum Supremacy Tsirelson Inequality

Authors: Kretschmer, William

Abstract | Document (528 KB) | BibTeX

Approximately Strategyproof Tournament Rules in the Probabilistic Setting

Authors: Ding, Kimberly ; Weinberg, S. Matthew

Abstract | Document (588 KB) | BibTeX

Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!

Authors: Bhattacharya, Anup ; Bishnu, Arijit ; Mishra, Gopinath ; Upasana, Anannya

Abstract | Document (566 KB) | BibTeX

The Variable-Processor Cup Game

Authors: Kuszmaul, William ; Westover, Alek

Abstract | Document (534 KB) | BibTeX

Comparison Graphs: A Unified Method for Uniformity Testing

Authors: Meir, Uri

Abstract | Document (487 KB) | BibTeX

Circular Trace Reconstruction

Authors: Narayanan, Shyam ; Ren, Michael

Abstract | Document (558 KB) | BibTeX

Self-Testing of a Single Quantum Device Under Computational Assumptions

Authors: Metger, Tony ; Vidick, Thomas

Abstract | Document (466 KB) | BibTeX

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime

Authors: Chen, Xi ; De, Anindya ; Lee, Chin Ho ; Servedio, Rocco A. ; Sinha, Sandip

Abstract | Document (655 KB) | BibTeX

Metrical Service Systems with Transformations

Authors: Bubeck, Sébastien ; Buchbinder, Niv ; Coester, Christian ; Sellke, Mark

Abstract | Document (527 KB) | BibTeX

Tight Hardness Results for Training Depth-2 ReLU Networks

Authors: Goel, Surbhi ; Klivans, Adam ; Manurangsi, Pasin ; Reichman, Daniel

Abstract | Document (554 KB) | BibTeX

A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization

Authors: Dutta, Pranjal ; Saxena, Nitin ; Thierauf, Thomas

Abstract | Document (648 KB) | BibTeX

Circuit Depth Reductions

Authors: Golovnev, Alexander ; Kulikov, Alexander S. ; Williams, R. Ryan

Abstract | Document (565 KB) | BibTeX

Dynamic Inference in Probabilistic Graphical Models

Authors: Feng, Weiming ; He, Kun ; Sun, Xiaoming ; Yin, Yitong

Abstract | Document (679 KB) | BibTeX

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

Authors: Kelman, Esty ; Khot, Subhash ; Kindler, Guy ; Minzer, Dor ; Safra, Muli

Abstract | Document (496 KB) | BibTeX

On Rich 2-to-1 Games

Authors: Braverman, Mark ; Khot, Subhash ; Minzer, Dor

Abstract | Document (597 KB) | BibTeX

Distributed Quantum Proofs for Replicated Data

Authors: Fraigniaud, Pierre ; Le Gall, François ; Nishimura, Harumichi ; Paz, Ami

Abstract | Document (599 KB) | BibTeX

On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions

Authors: Nanashima, Mikito

Abstract | Document (474 KB) | BibTeX

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

Authors: Barak, Boaz ; Chou, Chi-Ning ; Gao, Xun

Abstract | Document (664 KB) | BibTeX

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness

Authors: Grochow, Joshua A. ; Qiao, Youming

Abstract | Document (617 KB) | BibTeX

Bounds on the QAC^0 Complexity of Approximating Parity

Authors: Rosenthal, Gregory

Abstract | Document (542 KB) | BibTeX

Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)

Authors: Ron-Zewi, Noga ; Shaltiel, Ronen ; Varma, Nithin

Abstract | Document (603 KB) | BibTeX

Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?

Authors: Mardia, Jay

Abstract | Document (659 KB) | BibTeX

Algorithms and Hardness for Multidimensional Range Updates and Queries

Authors: Lau, Joshua ; Ritossa, Angus

Abstract | Document (617 KB) | BibTeX

Two Combinatorial MA-Complete Problems

Authors: Aharonov, Dorit ; Grilo, Alex B.

Abstract | Document (652 KB) | BibTeX

Delegated Stochastic Probing

Authors: Bechtel, Curtis ; Dughmi, Shaddin

Abstract | Document (464 KB) | BibTeX

Explicit SoS Lower Bounds from High-Dimensional Expanders

Authors: Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh ; Tulsiani, Madhur

Abstract | Document (548 KB) | BibTeX

Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines

Authors: Remscrim, Zachary

Abstract | Document (611 KB) | BibTeX

On the Complexity of #CSP^d

Authors: Lin, Jiabao

Abstract | Document (464 KB) | BibTeX

Interactive Proofs for Verifying Machine Learning

Authors: Goldwasser, Shafi ; Rothblum, Guy N. ; Shafer, Jonathan ; Yehudayoff, Amir

Abstract | Document (641 KB) | BibTeX

Ordered Graph Limits and Their Applications

Authors: Ben-Eliezer, Omri ; Fischer, Eldar ; Levi, Amit ; Yoshida, Yuichi

Abstract | Document (598 KB) | BibTeX

Error Correcting Codes for Uncompressed Messages

Authors: Grossman, Ofer ; Holmgren, Justin

Abstract | Document (611 KB) | BibTeX

Total Functions in the Polynomial Hierarchy

Authors: Kleinberg, Robert ; Korten, Oliver ; Mitropolsky, Daniel ; Papadimitriou, Christos

Abstract | Document (624 KB) | BibTeX

Relaxing Common Belief for Social Networks

Authors: Burrell, Noah ; Schoenebeck, Grant

Abstract | Document (652 KB) | BibTeX

Tiered Random Matching Markets: Rank Is Proportional to Popularity

Authors: Ashlagi, Itai ; Braverman, Mark ; Saberi, Amin ; Thomas, Clayton ; Zhao, Geng

Abstract | Document (516 KB) | BibTeX

Black-Box Uselessness: Composing Separations in Cryptography

Authors: Couteau, Geoffroy ; Farshim, Pooya ; Mahmoody, Mohammad

Abstract | Document (542 KB) | BibTeX

Pseudobinomiality of the Sticky Random Walk

Authors: Guruswami, Venkatesan ; Kumar, Vinayak M.

Abstract | Document (556 KB) | BibTeX

Robust Quantum Entanglement at (Nearly) Room Temperature

Authors: Eldar, Lior

Abstract | Document (605 KB) | BibTeX

Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Authors: Mudigonda, Abhijit S. ; Williams, R. Ryan

Abstract | Document (615 KB) | BibTeX

Online Search with a Hint

Authors: Angelopoulos, Spyros

Abstract | Document (472 KB) | BibTeX

Sequential Defaulting in Financial Networks

Authors: Papp, Pál András ; Wattenhofer, Roger

Abstract | Document (492 KB) | BibTeX

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Authors: Garg, Ankit ; Kothari, Robin ; Netrapalli, Praneeth ; Sherif, Suhail

Abstract | Document (526 KB) | BibTeX

Quantum Versus Randomized Communication Complexity, with Efficient Players

Authors: Girish, Uma ; Raz, Ran ; Tal, Avishay

Abstract | Document (543 KB) | BibTeX

Agnostic Learning with Unknown Utilities

Authors: Bhatia, Kush ; Bartlett, Peter L. ; Dragan, Anca D. ; Steinhardt, Jacob

Abstract | Document (620 KB) | BibTeX

On Distributed Differential Privacy and Counting Distinct Elements

Authors: Chen, Lijie ; Ghazi, Badih ; Kumar, Ravi ; Manurangsi, Pasin

Abstract | Document (647 KB) | BibTeX

A Generalized Matching Reconfiguration Problem

Authors: Solomon, Noam ; Solomon, Shay

Abstract | Document (483 KB) | BibTeX

Sensitivity Analysis of the Maximum Matching Problem

Authors: Yoshida, Yuichi ; Zhou, Samson

Abstract | Document (613 KB) | BibTeX

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

Authors: Vazirani, Vijay V. ; Yannakakis, Mihalis

Abstract | Document (501 KB) | BibTeX

An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability

Authors: Nenadov, Rajko ; Steger, Angelika ; Su, Pascal

Abstract | Document (708 KB) | BibTeX

Communication Memento: Memoryless Communication Complexity

Authors: Arunachalam, Srinivasan ; Podder, Supartha

Abstract | Document (569 KB) | BibTeX

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

Authors: Cohen, Michael B. ; Sidford, Aaron ; Tian, Kevin

Abstract | Document (569 KB) | BibTeX

Training (Overparametrized) Neural Networks in Near-Linear Time

Authors: van den Brand, Jan ; Peng, Binghui ; Song, Zhao ; Weinstein, Omri

Abstract | Document (588 KB) | BibTeX

A New Connection Between Node and Edge Depth Robust Graphs

Authors: Blocki, Jeremiah ; Cinkoske, Mike

Abstract | Document (560 KB) | BibTeX

Towards Local Testability for Quantum Coding

Authors: Leverrier, Anthony ; Londe, Vivien ; Zémor, Gilles

Abstract | Document (421 KB) | BibTeX

Complete Problems for Multi-Pseudodeterministic Computations

Authors: Dixon, Peter ; Pavan, A. ; Vinodchandran, N. V.

Abstract | Document (522 KB) | BibTeX

Online Paging with a Vanishing Regret

Authors: Emek, Yuval ; Kutten, Shay ; Shi, Yangguang

Abstract | Document (615 KB) | BibTeX

Differentially Oblivious Turing Machines

Authors: Komargodski, Ilan ; Shi, Elaine

Abstract | Document (572 KB) | BibTeX

Quantitative Correlation Inequalities via Semigroup Interpolation

Authors: De, Anindya ; Nadimpalli, Shivam ; Servedio, Rocco A.

Abstract | Document (551 KB) | BibTeX

Shrinkage of Decision Lists and DNF Formulas

Authors: Rossman, Benjamin

Abstract | Document (570 KB) | BibTeX

Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines

Authors: Mittal, Kunal ; Raz, Ran

Abstract | Document (452 KB) | BibTeX

Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma

Authors: Dziembowski, Stefan ; Fabiański, Grzegorz ; Faust, Sebastian ; Riahi, Siavash

Abstract | Document (589 KB) | BibTeX

Majorizing Measures for the Optimizer

Authors: Borst, Sander ; Dadush, Daniel ; Olver, Neil ; Sinha, Makrand

Abstract | Document (545 KB) | BibTeX

Randomness and Fairness in Two-Sided Matching with Limited Interviews

Authors: Beyhaghi, Hedyeh ; Tardos, Éva

Abstract | Document (475 KB) | BibTeX

Counterexamples to the Low-Degree Conjecture

Authors: Holmgren, Justin ; Wein, Alexander S.

Abstract | Document (402 KB) | BibTeX

High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)

Authors: Briët, Jop ; Labib, Farrokh

Abstract | Document (252 KB) | BibTeX

Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions

Authors: Immorlica, Nicole ; Kash, Ian A. ; Lucier, Brendan

Abstract | Document (559 KB) | BibTeX

Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach

Authors: Schoenebeck, Grant ; Yu, Fang-Yi

Abstract | Document (601 KB) | BibTeX

Distributed Load Balancing: A New Framework and Improved Guarantees

Authors: Ahmadian, Sara ; Liu, Allen ; Peng, Binghui ; Zadimoghaddam, Morteza

Abstract | Document (557 KB) | BibTeX

Erasure-Resilient Sublinear-Time Graph Algorithms

Authors: Levi, Amit ; Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Varma, Nithin

Abstract | Document (618 KB) | BibTeX

How to Sell Information Optimally: An Algorithmic Study

Authors: Cai, Yang ; Velegkas, Grigoris

Abstract | Document (580 KB) | BibTeX

Computation over the Noisy Broadcast Channel with Malicious Parties

Authors: Efremenko, Klim ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R.

Abstract | Document (549 KB) | BibTeX

Sampling Arborescences in Parallel

Authors: Anari, Nima ; Hu, Nathan ; Saberi, Amin ; Schild, Aaron

Abstract | Document (548 KB) | BibTeX

Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)

Authors: Babaioff, Moshe ; Cole, Richard ; Hartline, Jason ; Immorlica, Nicole ; Lucier, Brendan

Abstract | Document (197 KB) | BibTeX

A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract)

Authors: Charikar, Moses ; Garg, Shivam ; Gordon, Deborah M. ; Shiragur, Kirankumar

Abstract | Document (202 KB) | BibTeX

Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract)

Authors: Correa, José ; Dütting, Paul ; Fischer, Felix ; Schewior, Kevin ; Ziliotto, Bruno

Abstract | Document (227 KB) | BibTeX

Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)

Authors: Dafni, Neta ; Filmus, Yuval ; Lifshitz, Noam ; Lindzey, Nathan ; Vinyals, Marc

Abstract | Document (319 KB) | BibTeX

Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)

Authors: Feng, Yiding ; Niazadeh, Rad

Abstract | Document (208 KB) | BibTeX

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract)

Authors: Filmus, Yuval ; Meir, Or ; Tal, Avishay

Abstract | Document (425 KB) | BibTeX

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

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)