default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID36th CCC 2021: Toronto, ON, Canada (Virtual Conference)
- Valentine Kabanets:
36th Computational Complexity Conference, CCC 2021, Toronto, Ontario, Canada (Virtual Conference), July 20-23, 2021. LIPIcs 200, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-193-1 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Gil Cohen, Tal Yankovitz:
Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. 1:1-1:57 - Nati Linial, Adi Shraibman:
An Improved Protocol for the Exactly-N Problem. 2:1-2:8 - Dmitry Itsykson
, Artur Riazanov:
Proof Complexity of Natural Formulas via Communication Arguments. 3:1-3:34 - Mrinal Kumar, Ben Lee Volk:
A Lower Bound on Determinantal Complexity. 4:1-4:12 - Mark Braverman, Dor Minzer:
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. 5:1-5:48 - Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. 6:1-6:30 - Prerona Chatterjee:
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. 7:1-7:24 - Alexander Golovnev, Ishay Haviv:
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. 8:1-8:15 - Pavel Hrubes, Amir Yehudayoff:
Shadows of Newton Polytopes. 9:1-9:23 - Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty:
Fractional Pseudorandom Generators from Any Fourier Level. 10:1-10:24 - Pranjal Dutta, Prateek Dwivedi, Nitin Saxena:
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. 11:1-11:27 - Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. 12:1-12:74 - William Cole Franks, Philipp Reichenbach:
Barriers for Recent Methods in Geodesic Optimization. 13:1-13:54 - Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. 14:1-14:10 - Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang:
On the Cut Dimension of a Graph. 15:1-15:35 - Joshua A. Grochow, Youming Qiao:
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. 16:1-16:38 - Anastasia Sofronova, Dmitry Sokolov:
Branching Programs with Bounded Repetitions and Flow Formulas. 17:1-17:25 - Mika Göös, Gilbert Maystre:
A Majority Lemma for Randomised Query Complexity. 18:1-18:15 - Dori Medini, Amir Shpilka:
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. 19:1-19:27 - Zeyu Guo:
Variety Evasive Subspace Families. 20:1-20:33 - Yaroslav Alekseev:
A Lower Bound for Polynomial Calculus with Extension Rule. 21:1-21:18 - Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma:
Error Reduction for Weighted PRGs Against Read Once Branching Programs. 22:1-22:17 - Pravesh K. Kothari, Peter Manohar:
A Stress-Free Sum-Of-Squares Lower Bound for Coloring. 23:1-23:21 - Vishnu Iyer, Avishay Tal, Michael Whitmeyer:
Junta Distance Approximation with Sub-Exponential Queries. 24:1-24:38 - Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu:
Arithmetic Circuit Complexity of Division and Truncation. 25:1-25:36 - Shuo Pang:
SOS Lower Bound for Exact Planted Clique. 26:1-26:63 - Rahul Jain, Srijita Kundu:
A Direct Product Theorem for One-Way Quantum Communication. 27:1-27:28 - Simon Apers, Troy Lee:
Quantum Complexity of Minimum Cut. 28:1-28:33 - Markus Bläser, Julian Dörfler, Christian Ikenmeyer:
On the Complexity of Evaluating Highest Weight Vectors. 29:1-29:36 - Anurag Anshu, Shalev Ben-David, Srijita Kundu:
On Query-To-Communication Lifting for Adversary Bounds. 30:1-30:39 - Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Hardness of Constant-Round Communication Complexity. 31:1-31:30 - Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson:
Polynomial Time Algorithms in Invariant Theory for Torus Actions. 32:1-32:30 - Edward Pyne, Salil P. Vadhan:
Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). 33:1-33:15 - Isolde Adler, Noleen Köhler, Pan Peng:
GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing. 34:1-34:27 - Hanlin Ren, Rahul Santhanam:
Hardness of KT Characterizes Parallel Cryptography. 35:1-35:58 - Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam:
On the Pseudo-Deterministic Query Complexity of NP Search Problems. 36:1-36:22 - Akshay Kamath, Eric Price, David P. Woodruff:
A Simple Proof of a New Set Disjointness with Applications to Data Streams. 37:1-37:24 - Ivan Mihajlin, Alexander Smal:
Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. 38:1-38:24 - Uma Girish, Avishay Tal, Kewen Wu:
Fourier Growth of Parity Decision Trees. 39:1-39:36 - Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov:
The Power of Negative Reasoning. 40:1-40:24 - László Babai, Bohdan Kivva:
Matrix Rigidity Depends on the Target Field. 41:1-41:26
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-12-05 22:23 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:
