ITCS 2021 Accepted Papers

  • Yuval Dagan; Yuval Filmus; Daniel Kane; Shay Moran. The entropy of lies: playing twenty questions with a liar.
  • Russell Impagliazzo; Sam McGuire. Comparing computational entropies below majority (or: When is the dense model theorem false?).
  • Martin Hoefer; Pasin Manurangsi; Alexandros Psomas. Algorithmic Persuasion with Evidence.
  • Ishay Haviv. The Complexity of Finding Fair Independent Sets in Cycles.
  • Venkatesan Guruswami; Jonathan Mosheiff; Nicolas Resch; Shashwat Silas; Mary Wootters. Sharp Threshold Rates for Random Codes.
  • Cameron Musco; Christopher Musco; David P. Woodruff. Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation.
  • William Hoza; Edward Pyne; Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.
  • Eshwar Ram Arunachaleswaran; Sampath Kannan; Aaron Roth; Juba Ziani. Pipeline Interventions.
  • Mrinal Kumar; Ben Lee Volk. A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits.
  • Pasin Manurangsi; Aviad Rubinstein; Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences.
  • Nengkun Yu. Sample efficient identity testing and independence testing of quantum states.
  • Olaf Beyersdorff; Benjamin Böhm. Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
  • William Kretschmer. The Quantum Supremacy Tsirelson Inequality.
  • Moses Charikar; Shivam Garg; Deborah M. Gordon; Kirankumar Shiragur. A New Model for Ant Trail Formation and its Convergence Properties.
  • Kimberly Ding; S. Matthew Weinberg. Approximately Strategyproof Tournament Rules in the Probabilistic Setting.
  • Anup Bhattacharya; Arijit Bishnu; Gopinath Mishra; Anannya Upasana. Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!.
  • Alek Westover; William Kuszmaul. The Variable-Processor Cup Game.
  • Neta Dafni; Yuval Filmus; Noam Lifshitz; Nathan Lindzey; Marc Vinyals. Complexity measures on symmetric group and beyond.
  • Uri Meir. Comparison Graphs: a Unified Method for Uniformity Testing.
  • Shyam Narayanan; Michael Ren. Circular Trace Reconstruction.
  • Metger Tony; Vidick Thomas. Self-testing of a single quantum device under computational assumptions.
  • Xi Chen; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha. Polynomial-time trace reconstruction in the low deletion rate regime.
  • Sebastien Bubeck; Niv Buchbinder; Christian Coester; Mark Sellke. Metrical Service Systems with Transformations.
  • Daniel Reichman; Pasin Manurangsi; Subhi Goel; Adam R. Klivans. Tight Hardness Results for Training Depth-2 ReLU Networks.
  • Pranjal Dutta; Nitin Saxena; Thomas Thierauf. A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization.
  • Alexander Golovnev; Alexander S. Kulikov; Ryan Williams. Circuit Depth Reductions.
  • Weiming Feng; Kun He; Xiaoming Sun; Yitong Yin. Dynamic inference in probabilistic graphical models.
  • Esty Kelman; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
  • Mark Braverman; Subhash Khot; Dor Minzer. On Rich 2-to-1 Games.
  • Pierre Fraigniaud; François Le Gall; Harumichi Nishimura; Ami Paz. Distributed Quantum Proofs for Replicated Data.
  • Mikito Nanashima. On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions.
  • Boaz Barak; Chi-Ning Chou; Xun Gao. Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits.
  • Joshua A. Grochow; Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness.
  • Gregory Rosenthal. Bounds on the QAC0 Complexity of Approximating Parity.
  • Noga Ron-Zewi; Ronen Shaltiel; Nithin Varma. Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).
  • Jay Mardia. Is the space complexity of planted clique recovery the same as that of detection?.
  • Joshua Lau; Angus Ritossa. Algorithms and Hardness for Multidimensional Range Updates and Queries.
  • Dorit Aharonov; Alex B. Grilo. Two combinatorial MA-complete problems.
  • Curtis Bechtel; Shaddin Dughmi. Delegated Stochastic Probing.
  • Irit Dinur; Yuval Filmus; Prahladh Harsha; Madhur Tulsiani. Explicit SoS lower bounds from high-dimensional expanders.
  • Nima Anari; Nathan Hu; Amin Saberi; Aaron Schild. Sampling Arborescences in Parallel.
  • Zachary Remscrim. Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines.
  • Jiabao Lin. On the Complexity of #CSP^d.
  • Jonathan Shafer; Guy N. Rothblum; Shafi Goldwasser; Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning.
  • Yuval Filmus; Or Meir; Avishay Tal. Shrinkage under random projections, and cubic formula lower bounds in AC^0.
  • Omri Ben-Eliezer; Eldar Fischer; Amit Levi; Yuichi Yoshida. Ordered Graph Limits and Their Applications.
  • Ofer Grossman; Justin Holmgren. Error Correcting Codes for Uncompressed Messages.
  • Daniel Mitropolsky; Christos Papadimitriou; Robert Kleinberg. Total Functions in the Polynomial Hierarchy.
  • Noah Burrell; Grant Schoenebeck. Relaxing Common Belief for Social Networks.
  • Itai Ashlagi; Mark Braverman; Clayton Thomas; Geng Zhao. Tiered Random Matching Markets: Rank is Proportional to Popularity.
  • Geoffroy Couteau; Pooya Farshim; Mohammad Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography.
  • Venkatesan Guruswami; Vinayak Kumar. Pseudobinomiality of the Sticky Random Walk.
  • Lior Eldar. Robust Quantum Entanglement at (nearly) Room Temperature.
  • Abhijit Mudigonda; Ryan Williams. Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers.
  • Spyros Angelopoulos. Online Search With a Hint.
  • Moshe Babaioff; Richard Cole; Jason Hartline; Nicole Immorlica; Brendan Lucier. Non-quasi-linear Agents in Quasi-linear Mechanisms.
  • Pál András Papp; Roger Wattenhofer. Sequential Defaulting in Financial Networks.
  • Ankit Garg; Robin Kothari; Praneeth Netrapalli; Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization.
  • Uma Girish; Ran Raz; Avishay Tal. Quantum versus Randomized Communication Complexity, with Efficient Players.
  • Kush Bhatia; Peter L. Bartlett; Anca Dragan; Jacob Steinhardt. Agnostic learning with unknown utilities.
  • Lijie Chen; Badih Ghazi; Ravi Kumar; Pasin Manurangsi. On Distributed Differential Privacy and Counting Distinct Elements.
  • Noam Solomon; Shay Solomon. A Generalized Matching Reconfiguration Problem.
  • Yuichi Yoshida; Samson Zhou. Sensitivity Analysis of the Maximum Matching Problem.
  • Vijay Vazirani; Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets.
  • Rajko Nenadov; Angelika Steger; Pascal Su. An O(n) time algorithm for finding Hamilton cycles with high probability.
  • Srinivasan Arunachalam; Supartha Podder. Communication memento: Memoryless communication complexity.
  • Michael B. Cohen; Aaron Sidford; Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
  • Binghui Peng; Zhao Song; Jan van den Brand; Omri Weinstein. Training (Overparametrized) Neural Networks in Near-Linear Time.
  • Jeremiah Blocki; Mike Cinkoske. A New Connection Between Node and Edge Depth Robust Graphs.
  • Anthony Leverrier; Vivien Londe; Gilles Zémor. Towards local testability for quantum coding.
  • Peter Dixon; A Pavan; N. V. Vinodchandran. Complete Problems for Multi-Pseudodeterministic Computations.
  • Yuval Emek; Shay Kutten; Yangguang Shi. Online Paging with a Vanishing Regret.
  • José Correa; Paul Dütting; Felix Fischer; Kevin Schewior; Bruno Ziliotto. Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility.
  • Ilan Komargodski; Elaine Shi. Differentially Oblivious Turing Machines.
  • Shivam Nadimpalli; Rocco A. Servedio; Anindya De. A new approach to quantitative correlation inequalities.
  • Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas.
  • Kunal Mittal; Ran Raz. Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines.
  • Stefan Dziembowski; Grzegorz Fabiański; Sebastian Faust; Siavash Riahi. Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma.
  • Sander Borst; Daniel Dadush; Neil Olver; Makrand Sinha. Majorizing Measures for the Optimizer.
  • Hedyeh Beyhaghi; Eva Tardos. Randomness and Fairness in Two-Sided Matching with Limited Interviews.
  • Justin Holmgren; Alexander S. Wein. Counterexamples to the Low-Degree Conjecture.
  • Farrokh Labib; Jop Briet. High-entropy dual functions and locally decodable codes.
  • Nicole Immorlica; Ian Kash; Brendan Lucier. Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions.
  • Yiding Feng; Rad Niazadeh. Batching and Optimal Multi-stage Bipartite Allocations.
  • Grant Schoenebeck; Fang-Yi Yu. Learning and Strongly Truthful Multi-task Setting Peer Prediction: A Variational Approach.
  • Allen Liu; Sara Ahmadian; Binghui Peng; Morteza Zadimoghaddam. Distributed load balancing: a new framework and improved guarantees.
  • Amit Levi; Ramesh Krishnan S. Pallavoor; Sofya Raskhodnikova; Nithin Varma. Sublinear Algorithms for Graphs with Incomplete Information.
  • Yang Cai; Grigoris Velegkas. How to Sell Information Optimally: an Algorithmic Study.
  • Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh R. Saxena. Computation Over the Noisy Broadcast Channel with Malicious Parties.