36th Computational Complexity Conference : CCC 2021, July 20-23 Toronto, Ontario, Canada (virtual conference) (Englisch)
Freier Zugriff
- Neue Suche nach: Computational Complexity Conference
- Weitere Informationen zu Computational Complexity Conference:
- http://d-nb.info/gnd/1236847342
- Neue Suche nach: Kabanets, Valentine
- Neue Suche nach: Computational Complexity Conference
- Weitere Informationen zu Computational Complexity Conference:
- http://d-nb.info/gnd/1236847342
2021
-
ISBN:
- Konferenzband / Elektronische Ressource
-
Titel:36th Computational Complexity Conference : CCC 2021, July 20-23 Toronto, Ontario, Canada (virtual conference)
-
Weitere Titelangaben:CCC 2021
-
Beteiligte:Kabanets, Valentine ( Herausgeber:in ) / Computational Complexity Conference ( Autor:in )
-
Kongress:Conference on Computational Complexity ; 36 ; 2021 ; Online
CCC ; 36 ; 2021 ; Online -
Erschienen in:LIPIcs ; vol. 200
-
Verlag:
-
Erscheinungsort:Saarbrücken/Wadern, Germany
-
Erscheinungsdatum:2021
-
Format / Umfang:1 Online-Ressource
-
Anmerkungen:Literaturangaben
-
ISBN:
-
DOI:
-
Medientyp:Konferenzband
-
Format:Elektronische Ressource
-
Sprache:Englisch
- Neue Suche nach: 54.10
- Weitere Informationen zu Basisklassifikation
-
Schlagwörter:
-
Klassifikation:
BKL: 54.10 Theoretische Informatik -
Lizenzbestimmungen:
-
Datenquelle:
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDCCohen, Gil / Yankovitz, Tal et al. | 2021
- 2
-
An Improved Protocol for the Exactly-N ProblemLinial, Nati / Shraibman, Adi et al. | 2021
- 3
-
Proof Complexity of Natural Formulas via Communication ArgumentsItsykson, Dmitry / Riazanov, Artur et al. | 2021
- 4
-
A Lower Bound on Determinantal ComplexityKumar, Mrinal / Volk, Ben Lee et al. | 2021
- 5
-
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric BodiesBraverman, Mark / Minzer, Dor et al. | 2021
- 6
-
On the Power and Limitations of Branch and CutFleming, Noah / Göös, Mika / Impagliazzo, Russell / Pitassi, Toniann / Robere, Robert / Tan, Li-Yang / Wigderson, Avi et al. | 2021
- 7
-
Separating ABPs and Some Structured Formulas in the Non-Commutative SettingChatterjee, Prerona et al. | 2021
- 8
-
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and ApplicationsGolovnev, Alexander / Haviv, Ishay et al. | 2021
- 9
-
Shadows of Newton PolytopesHrubeš, Pavel / Yehudayoff, Amir et al. | 2021
- 10
-
Fractional Pseudorandom Generators from Any Fourier LevelChattopadhyay, Eshan / Gaitonde, Jason / Lee, Chin Ho / Lovett, Shachar / Shetty, Abhishek et al. | 2021
- 11
-
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 CircuitsDutta, Pranjal / Dwivedi, Prateek / Saxena, Nitin et al. | 2021
- 12
-
Robustly Self-Ordered Graphs: Constructions and Applications to Property TestingGoldreich, Oded / Wigderson, Avi et al. | 2021
- 13
-
Barriers for Recent Methods in Geodesic OptimizationFranks, W. Cole / Reichenbach, Philipp et al. | 2021
- 14
-
Communication Complexity with Defective RandomnessBall, Marshall / Goldreich, Oded / Malkin, Tal et al. | 2021
- 15
-
On the Cut Dimension of a GraphLee, Troy / Li, Tongyang / Santha, Miklos / Zhang, Shengyu et al. | 2021
- 16
-
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via TensorsGrochow, Joshua A. / Qiao, Youming et al. | 2021
- 17
-
Branching Programs with Bounded Repetitions and Flow FormulasSofronova, Anastasia / Sokolov, Dmitry et al. | 2021
- 18
-
A Majority Lemma for Randomised Query ComplexityGöös, Mika / Maystre, Gilbert et al. | 2021
- 19
-
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ CircuitsMedini, Dori / Shpilka, Amir et al. | 2021
- 20
-
Variety Evasive Subspace FamiliesGuo, Zeyu et al. | 2021
- 21
-
A Lower Bound for Polynomial Calculus with Extension RuleAlekseev, Yaroslav et al. | 2021
- 22
-
Error Reduction for Weighted PRGs Against Read Once Branching ProgramsCohen, Gil / Doron, Dean / Renard, Oren / Sberlo, Ori / Ta-Shma, Amnon et al. | 2021
- 23
-
A Stress-Free Sum-Of-Squares Lower Bound for ColoringKothari, Pravesh K. / Manohar, Peter et al. | 2021
- 24
-
Junta Distance Approximation with Sub-Exponential QueriesIyer, Vishnu / Tal, Avishay / Whitmeyer, Michael et al. | 2021
- 25
-
Arithmetic Circuit Complexity of Division and TruncationDutta, Pranjal / Jindal, Gorav / Pandey, Anurag / Sinhababu, Amit et al. | 2021
- 26
-
SOS Lower Bound for Exact Planted CliquePang, Shuo et al. | 2021
- 27
-
A Direct Product Theorem for One-Way Quantum CommunicationJain, Rahul / Kundu, Srijita et al. | 2021
- 28
-
Quantum Complexity of Minimum CutApers, Simon / Lee, Troy et al. | 2021
- 29
-
On the Complexity of Evaluating Highest Weight VectorsBläser, Markus / Dörfler, Julian / Ikenmeyer, Christian et al. | 2021
- 30
-
On Query-To-Communication Lifting for Adversary BoundsAnshu, Anurag / Ben-David, Shalev / Kundu, Srijita et al. | 2021
- 31
-
Hardness of Constant-Round Communication ComplexityHirahara, Shuichi / Ilango, Rahul / Loff, Bruno et al. | 2021
- 32
-
Polynomial Time Algorithms in Invariant Theory for Torus ActionsBürgisser, Peter / Doğan, M. Levent / Makam, Visu / Walter, Michael / Wigderson, Avi et al. | 2021
- 33
-
Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)Pyne, Edward / Vadhan, Salil et al. | 2021
- 34
-
GSF-Locality Is Not Sufficient For Proximity-Oblivious TestingAdler, Isolde / Köhler, Noleen / Peng, Pan et al. | 2021
- 35
-
Hardness of KT Characterizes Parallel CryptographyRen, Hanlin / Santhanam, Rahul et al. | 2021
- 36
-
On the Pseudo-Deterministic Query Complexity of NP Search ProblemsGoldwasser, Shafi / Impagliazzo, Russell / Pitassi, Toniann / Santhanam, Rahul et al. | 2021
- 37
-
A Simple Proof of a New Set Disjointness with Applications to Data StreamsKamath, Akshay / Price, Eric / Woodruff, David P. et al. | 2021
- 38
-
Toward Better Depth Lower Bounds: The XOR-KRW ConjectureMihajlin, Ivan / Smal, Alexander et al. | 2021
- 39
-
Fourier Growth of Parity Decision TreesGirish, Uma / Tal, Avishay / Wu, Kewen et al. | 2021
- 40
-
The Power of Negative Reasoningde Rezende, Susanna F. / Lauria, Massimo / Nordström, Jakob / Sokolov, Dmitry et al. | 2021
- 41
-
Matrix Rigidity Depends on the Target FieldBabai, László / Kivva, Bohdan et al. | 2021