default search action
36th CCC 2021: Toronto, ON, Canada (Virtual Conference)
- Valentine Kabanets:
36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference). 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
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
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. 11:1-11:27 - Oded Goldreich
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. 12:1-12:74 - William Cole Franks
Barriers for Recent Methods in Geodesic Optimization. 13:1-13:54 - Marshall Ball
Communication Complexity with Defective Randomness. 14:1-14:10 - Troy Lee, Tongyang Li
On the Cut Dimension of a Graph. 15:1-15:35 - Joshua A. Grochow
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
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
Junta Distance Approximation with Sub-Exponential Queries. 24:1-24:38 - Pranjal Dutta
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
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
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
GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing. 34:1-34:27 - Hanlin Ren
Hardness of KT Characterizes Parallel Cryptography. 35:1-35:58 - Shafi Goldwasser, Russell Impagliazzo
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
Fourier Growth of Parity Decision Trees. 39:1-39:36 - Susanna F. de Rezende
The Power of Negative Reasoning. 40:1-40:24 - László Babai
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 2024-12-12 21:04 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: