Portal - CCC 2021

CCC 2021	July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference)
36th Computational Complexity Conference (CCC 2021) Valentine Kabanets (Ed.)
ISBN 978-3-95977-193-1, LIPICS Vol. 200	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 20 MB)
Search Publication Server

Authors

de Rezende, Susanna F.

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Kabanets, Valentine

Abstract | Document (497 KB) | BibTeX

Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC

Authors: Cohen, Gil ; Yankovitz, Tal

Abstract | Document (1,094 KB) | BibTeX

An Improved Protocol for the Exactly-N Problem

Authors: Linial, Nati ; Shraibman, Adi

Abstract | Document (584 KB) | BibTeX

Proof Complexity of Natural Formulas via Communication Arguments

Authors: Itsykson, Dmitry ; Riazanov, Artur

Abstract | Document (1,076 KB) | BibTeX

A Lower Bound on Determinantal Complexity

Authors: Kumar, Mrinal ; Volk, Ben Lee

Abstract | Document (672 KB) | BibTeX

Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies

Authors: Braverman, Mark ; Minzer, Dor

Abstract | Document (1,099 KB) | BibTeX

On the Power and Limitations of Branch and Cut

Authors: Fleming, Noah ; Göös, Mika ; Impagliazzo, Russell ; Pitassi, Toniann ; Robere, Robert ; Tan, Li-Yang ; Wigderson, Avi

Abstract | Document (867 KB) | BibTeX

Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

Authors: Chatterjee, Prerona

Abstract | Document (852 KB) | BibTeX

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications

Authors: Golovnev, Alexander ; Haviv, Ishay

Abstract | Document (694 KB) | BibTeX

Shadows of Newton Polytopes

Authors: Hrubeš, Pavel ; Yehudayoff, Amir

Abstract | Document (759 KB) | BibTeX

Fractional Pseudorandom Generators from Any Fourier Level

Authors: Chattopadhyay, Eshan ; Gaitonde, Jason ; Lee, Chin Ho ; Lovett, Shachar ; Shetty, Abhishek

Abstract | Document (829 KB) | BibTeX

Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

Authors: Dutta, Pranjal ; Dwivedi, Prateek ; Saxena, Nitin

Abstract | Document (1,074 KB) | BibTeX

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Authors: Goldreich, Oded ; Wigderson, Avi

Abstract | Document (1,550 KB) | BibTeX

Barriers for Recent Methods in Geodesic Optimization

Authors: Franks, W. Cole ; Reichenbach, Philipp

Abstract | Document (1,232 KB) | BibTeX

Communication Complexity with Defective Randomness

Authors: Ball, Marshall ; Goldreich, Oded ; Malkin, Tal

Abstract | Document (582 KB) | BibTeX

On the Cut Dimension of a Graph

Authors: Lee, Troy ; Li, Tongyang ; Santha, Miklos ; Zhang, Shengyu

Abstract | Document (920 KB) | BibTeX

On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors

Authors: Grochow, Joshua A. ; Qiao, Youming

Abstract | Document (1,130 KB) | BibTeX

Branching Programs with Bounded Repetitions and Flow Formulas

Authors: Sofronova, Anastasia ; Sokolov, Dmitry

Abstract | Document (899 KB) | BibTeX

A Majority Lemma for Randomised Query Complexity

Authors: Göös, Mika ; Maystre, Gilbert

Abstract | Document (735 KB) | BibTeX

Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits

Authors: Medini, Dori ; Shpilka, Amir

Abstract | Document (909 KB) | BibTeX

Variety Evasive Subspace Families

Authors: Guo, Zeyu

Abstract | Document (974 KB) | BibTeX

A Lower Bound for Polynomial Calculus with Extension Rule

Authors: Alekseev, Yaroslav

Abstract | Document (807 KB) | BibTeX

Error Reduction for Weighted PRGs Against Read Once Branching Programs

Authors: Cohen, Gil ; Doron, Dean ; Renard, Oren ; Sberlo, Ori ; Ta-Shma, Amnon

Abstract | Document (737 KB) | BibTeX

A Stress-Free Sum-Of-Squares Lower Bound for Coloring

Authors: Kothari, Pravesh K. ; Manohar, Peter

Abstract | Document (865 KB) | BibTeX

Junta Distance Approximation with Sub-Exponential Queries

Authors: Iyer, Vishnu ; Tal, Avishay ; Whitmeyer, Michael

Abstract | Document (1,178 KB) | BibTeX

Arithmetic Circuit Complexity of Division and Truncation

Authors: Dutta, Pranjal ; Jindal, Gorav ; Pandey, Anurag ; Sinhababu, Amit

Abstract | Document (1,019 KB) | BibTeX

SOS Lower Bound for Exact Planted Clique

Authors: Pang, Shuo

Abstract | Document (1,267 KB) | BibTeX

A Direct Product Theorem for One-Way Quantum Communication

Authors: Jain, Rahul ; Kundu, Srijita

Abstract | Document (840 KB) | BibTeX

Quantum Complexity of Minimum Cut

Authors: Apers, Simon ; Lee, Troy

Abstract | Document (949 KB) | BibTeX

On the Complexity of Evaluating Highest Weight Vectors

Authors: Bläser, Markus ; Dörfler, Julian ; Ikenmeyer, Christian

Abstract | Document (1,080 KB) | BibTeX

On Query-To-Communication Lifting for Adversary Bounds

Authors: Anshu, Anurag ; Ben-David, Shalev ; Kundu, Srijita

Abstract | Document (902 KB) | BibTeX

Hardness of Constant-Round Communication Complexity

Authors: Hirahara, Shuichi ; Ilango, Rahul ; Loff, Bruno

Abstract | Document (886 KB) | BibTeX

Polynomial Time Algorithms in Invariant Theory for Torus Actions

Authors: Bürgisser, Peter ; Doğan, M. Levent ; Makam, Visu ; Walter, Michael ; Wigderson, Avi

Abstract | Document (847 KB) | BibTeX

Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)

Authors: Pyne, Edward ; Vadhan, Salil

Abstract | Document (757 KB) | BibTeX

GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing

Authors: Adler, Isolde ; Köhler, Noleen ; Peng, Pan

Abstract | Document (876 KB) | BibTeX

Hardness of KT Characterizes Parallel Cryptography

Authors: Ren, Hanlin ; Santhanam, Rahul

Abstract | Document (1,359 KB) | BibTeX

On the Pseudo-Deterministic Query Complexity of NP Search Problems

Authors: Goldwasser, Shafi ; Impagliazzo, Russell ; Pitassi, Toniann ; Santhanam, Rahul

Abstract | Document (742 KB) | BibTeX

A Simple Proof of a New Set Disjointness with Applications to Data Streams

Authors: Kamath, Akshay ; Price, Eric ; Woodruff, David P.

Abstract | Document (1,307 KB) | BibTeX

Toward Better Depth Lower Bounds: The XOR-KRW Conjecture

Authors: Mihajlin, Ivan ; Smal, Alexander

Abstract | Document (872 KB) | BibTeX

Fourier Growth of Parity Decision Trees

Authors: Girish, Uma ; Tal, Avishay ; Wu, Kewen

Abstract | Document (1,107 KB) | BibTeX

The Power of Negative Reasoning

Authors: de Rezende, Susanna F. ; Lauria, Massimo ; Nordström, Jakob ; Sokolov, Dmitry

Abstract | Document (760 KB) | BibTeX

Matrix Rigidity Depends on the Target Field

Authors: Babai, László ; Kivva, Bohdan

Abstract | Document (896 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

36th Computational Complexity Conference (CCC 2021)