CINXE.COM

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