default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID12th ITCS 2021
- James R. Lee:
12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. LIPIcs 185, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-177-1 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:14
- Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran:
The Entropy of Lies: Playing Twenty Questions with a Liar. 1:1-1:16 - Russell Impagliazzo
, Sam McGuire:
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). 2:1-2:20 - Martin Hoefer, Pasin Manurangsi, Alexandros Psomas:
Algorithmic Persuasion with Evidence. 3:1-3:20 - Ishay Haviv:
The Complexity of Finding Fair Independent Sets in Cycles. 4:1-4:14 - Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Sharp Threshold Rates for Random Codes. 5:1-5:20 - Cameron Musco, Christopher Musco, David P. Woodruff:
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. 6:1-6:20 - William M. Hoza, Edward Pyne, Salil P. Vadhan:
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. 7:1-7:20 - Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani:
Pipeline Interventions. 8:1-8:20 - Mrinal Kumar, Ben Lee Volk:
A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. 9:1-9:9 - Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm:
The Strongish Planted Clique Hypothesis and Its Consequences. 10:1-10:21 - Nengkun Yu:
Sample Efficient Identity Testing and Independence Testing of Quantum States. 11:1-11:20 - Olaf Beyersdorff, Benjamin Böhm:
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution. 12:1-12:20 - William Kretschmer:
The Quantum Supremacy Tsirelson Inequality. 13:1-13:13 - Kimberly Ding, S. Matthew Weinberg:
Approximately Strategyproof Tournament Rules in the Probabilistic Setting. 14:1-14:20 - Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana:
Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! 15:1-15:19 - William Kuszmaul, Alek Westover:
The Variable-Processor Cup Game. 16:1-16:20 - Uri Meir:
Comparison Graphs: A Unified Method for Uniformity Testing. 17:1-17:20 - Shyam Narayanan, Michael Ren:
Circular Trace Reconstruction. 18:1-18:18 - Tony Metger, Thomas Vidick:
Self-Testing of a Single Quantum Device Under Computational Assumptions. 19:1-19:12 - Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. 20:1-20:20 - Sébastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke:
Metrical Service Systems with Transformations. 21:1-21:20 - Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman:
Tight Hardness Results for Training Depth-2 ReLU Networks. 22:1-22:14 - Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. 23:1-23:21 - Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams:
Circuit Depth Reductions. 24:1-24:20 - Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin:
Dynamic Inference in Probabilistic Graphical Models. 25:1-25:20 - Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. 26:1-26:17 - Mark Braverman, Subhash Khot, Dor Minzer:
On Rich 2-to-1 Games. 27:1-27:20 - Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz:
Distributed Quantum Proofs for Replicated Data. 28:1-28:20 - Mikito Nanashima:
On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions. 29:1-29:15 - Boaz Barak, Chi-Ning Chou, Xun Gao:
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. 30:1-30:20 - Joshua A. Grochow, Youming Qiao:
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. 31:1-31:19 - Gregory Rosenthal:
Bounds on the QAC^0 Complexity of Approximating Parity. 32:1-32:20 - 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). 33:1-33:18 - Jay Mardia:
Is the Space Complexity of Planted Clique Recovery the Same as That of Detection? 34:1-34:17 - Joshua Lau, Angus Ritossa:
Algorithms and Hardness for Multidimensional Range Updates and Queries. 35:1-35:20 - Dorit Aharonov, Alex B. Grilo:
Two Combinatorial MA-Complete Problems. 36:1-36:20 - Curtis Bechtel, Shaddin Dughmi:
Delegated Stochastic Probing. 37:1-37:19 - Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit SoS Lower Bounds from High-Dimensional Expanders. 38:1-38:16 - Zachary Remscrim:
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. 39:1-39:20 - Jiabao Lin:
On the Complexity of #CSP^d. 40:1-40:10 - Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff:
Interactive Proofs for Verifying Machine Learning. 41:1-41:19 - Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Yuichi Yoshida:
Ordered Graph Limits and Their Applications. 42:1-42:20 - Ofer Grossman, Justin Holmgren:
Error Correcting Codes for Uncompressed Messages. 43:1-43:18 - Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos H. Papadimitriou:
Total Functions in the Polynomial Hierarchy. 44:1-44:18 - Noah Burrell, Grant Schoenebeck:
Relaxing Common Belief for Social Networks. 45:1-45:20 - Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao:
Tiered Random Matching Markets: Rank Is Proportional to Popularity. 46:1-46:16 - Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody:
Black-Box Uselessness: Composing Separations in Cryptography. 47:1-47:20 - Venkatesan Guruswami, Vinayak M. Kumar:
Pseudobinomiality of the Sticky Random Walk. 48:1-48:19 - Lior Eldar:
Robust Quantum Entanglement at (Nearly) Room Temperature. 49:1-49:20 - Abhijit Mudigonda, R. Ryan Williams:
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. 50:1-50:20 - Spyros Angelopoulos:
Online Search with a Hint. 51:1-51:16 - Pál András Papp, Roger Wattenhofer:
Sequential Defaulting in Financial Networks. 52:1-52:20 - Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif:
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. 53:1-53:20 - Uma Girish, Ran Raz, Avishay Tal:
Quantum Versus Randomized Communication Complexity, with Efficient Players. 54:1-54:20 - Kush Bhatia, Peter L. Bartlett, Anca D. Dragan, Jacob Steinhardt:
Agnostic Learning with Unknown Utilities. 55:1-55:20 - Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi:
On Distributed Differential Privacy and Counting Distinct Elements. 56:1-56:18 - Noam Solomon, Shay Solomon:
A Generalized Matching Reconfiguration Problem. 57:1-57:20 - Yuichi Yoshida, Samson Zhou:
Sensitivity Analysis of the Maximum Matching Problem. 58:1-58:20 - Vijay V. Vazirani, Mihalis Yannakakis:
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. 59:1-59:19 - Rajko Nenadov, Angelika Steger, Pascal Su:
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. 60:1-60:17 - Srinivasan Arunachalam, Supartha Podder:
Communication Memento: Memoryless Communication Complexity. 61:1-61:20 - Michael B. Cohen, Aaron Sidford, Kevin Tian:
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. 62:1-62:18 - Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein:
Training (Overparametrized) Neural Networks in Near-Linear Time. 63:1-63:15 - Jeremiah Blocki, Mike Cinkoske:
A New Connection Between Node and Edge Depth Robust Graphs. 64:1-64:18 - Anthony Leverrier, Vivien Londe, Gilles Zémor:
Towards Local Testability for Quantum Coding. 65:1-65:11 - Peter Dixon, A. Pavan, N. V. Vinodchandran:
Complete Problems for Multi-Pseudodeterministic Computations. 66:1-66:16 - Yuval Emek, Shay Kutten, Yangguang Shi:
Online Paging with a Vanishing Regret. 67:1-67:20 - Ilan Komargodski, Elaine Shi:
Differentially Oblivious Turing Machines. 68:1-68:19 - Anindya De, Shivam Nadimpalli, Rocco A. Servedio:
Quantitative Correlation Inequalities via Semigroup Interpolation. 69:1-69:20 - Benjamin Rossman:
Shrinkage of Decision Lists and DNF Formulas. 70:1-70:14 - Kunal Mittal, Ran Raz:
Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. 71:1-71:15 - Stefan Dziembowski, Grzegorz Fabianski, Sebastian Faust, Siavash Riahi:
Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma. 72:1-72:20 - Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha:
Majorizing Measures for the Optimizer. 73:1-73:20 - Hedyeh Beyhaghi, Éva Tardos:
Randomness and Fairness in Two-Sided Matching with Limited Interviews. 74:1-74:18 - Justin Holmgren, Alexander S. Wein:
Counterexamples to the Low-Degree Conjecture. 75:1-75:9 - Jop Briët, Farrokh Labib:
High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract). 76:1-76:2 - Nicole Immorlica, Ian A. Kash, Brendan Lucier:
Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions. 77:1-77:14 - Grant Schoenebeck, Fang-Yi Yu:
Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach. 78:1-78:20 - Sara Ahmadian, Allen Liu, Binghui Peng, Morteza Zadimoghaddam:
Distributed Load Balancing: A New Framework and Improved Guarantees. 79:1-79:20 - Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. 80:1-80:20 - Yang Cai, Grigoris Velegkas:
How to Sell Information Optimally: An Algorithmic Study. 81:1-81:20 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Computation over the Noisy Broadcast Channel with Malicious Parties. 82:1-82:19 - Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild:
Sampling Arborescences in Parallel. 83:1-83:18 - Moshe Babaioff, Richard Cole, Jason D. Hartline, Nicole Immorlica, Brendan Lucier:
Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract). 84:1-84:1 - Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur:
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). 85:1-85:2 - José Correa, Paul Dütting, Felix A. Fischer, Kevin Schewior, Bruno Ziliotto:
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract). 86:1-86:1 - Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals:
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract). 87:1-87:5 - Yiding Feng, Rad Niazadeh:
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). 88:1-88:1 - Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). 89:1-89:7
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-13 22:07 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
