Limits on the Universal Method for Matrix Multiplication (English)
Free access
- New search for: Alman, Josh
- New search for: Alman, Josh
- New search for: Shpilka, Amir
In:
LIPIcs, Volume 137, CCC 2019
: 34th Computational Complexity Conference (CCC 2019)
;
137
;
12:1-12:24
;
2019
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Limits on the Universal Method for Matrix Multiplication
-
Contributors:Alman, Josh ( author ) / Shpilka, Amir ( editor )
-
Published in:LIPIcs, Volume 137, CCC 2019 : 34th Computational Complexity Conference (CCC 2019) ; 137 ; 12:1-12:24Leibniz International Proceedings in Informatics (LIPIcs) ; 137 ; 12:1-12:24
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2019-07-16
-
Size:24 pages , 597590 byte
-
Remarks:LIPIcs, Vol. 137, 34th Computational Complexity Conference (CCC 2019), pages 12:1-12:24
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Criticality of Regular FormulasRossman, Benjamin et al. | 2019
- 2
-
Almost Optimal Distribution-Free Junta TestingBshouty, Nader H. et al. | 2019
- 3
-
UG-Hardness to NP-Hardness by Losing HalfBhangale, Amey / Khot, Subhash et al. | 2019
- 4
-
Simple and Efficient Pseudorandom Generators from Gaussian ProcessesChattopadhyay, Eshan / De, Anindya / Servedio, Rocco A. et al. | 2019
- 5
-
From DNF Compression to Sunflower Theorems via RegularityLovett, Shachar / Solomon, Noam / Zhang, Jiapeng et al. | 2019
- 6
-
Resolution and the Binary Encoding of Combinatorial PrinciplesDantchev, Stefan / Galesi, Nicola / Martin, Barnaby et al. | 2019
- 7
-
Fourier Bounds and Pseudorandom Generators for Product TestsLee, Chin Ho et al. | 2019
- 8
-
Sherali - Adams Strikes BackO'Donnell, Ryan / Schramm, Tselil et al. | 2019
- 9
-
Typically-Correct Derandomization for Small Time and SpaceHoza, William M. et al. | 2019
- 10
-
Optimal Short-Circuit Resilient FormulasBraverman, Mark / Efremenko, Klim / Gelles, Ran / Yitayew, Michael A. et al. | 2019
- 11
-
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW HeuristicStephens-Davidowitz, Noah et al. | 2019
- 12
-
Limits on the Universal Method for Matrix MultiplicationAlman, Josh et al. | 2019
- 13
-
Optimality of Linear Sketching Under Modular UpdatesHosseini, Kaave / Lovett, Shachar / Yaroslavtsev, Grigory et al. | 2019
- 14
-
Equality Alone Does not Simulate RandomnessChattopadhyay, Arkadev / Lovett, Shachar / Vinyals, Marc et al. | 2019
- 15
-
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic ApplicationsDwivedi, Ashish / Mittal, Rajat / Saxena, Nitin et al. | 2019
- 16
-
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once FormulasDoron, Dean / Hatami, Pooya / Hoza, William M. et al. | 2019
- 17
-
Fourier and Circulant Matrices Are Not RigidDvir, Zeev / Liu, Allen et al. | 2019
- 18
-
Nullstellensatz Size-Degree Trade-offs from Reversible Pebblingde Rezende, Susanna F. / Nordström, Jakob / Meir, Or / Robere, Robert et al. | 2019
- 19
-
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of ProximityChen, Lijie / Williams, R. Ryan et al. | 2019
- 20
-
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State ConversionCoudron, Matthew / Harrow, Aram W. et al. | 2019
- 21
-
Average-Case Quantum Advantage with Shallow CircuitsLe Gall, François et al. | 2019
- 22
-
Time-Space Lower Bounds for Two-Pass LearningGarg, Sumegha / Raz, Ran / Tal, Avishay et al. | 2019
- 23
-
Parity Helps to Compute MajorityOliveira, Igor Carboni / Santhanam, Rahul / Srinivasan, Srikanth et al. | 2019
- 24
-
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz ProofsAtserias, Albert / Hakoniemi, Tuomas et al. | 2019
- 25
-
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High PrecisionCoudron, Matthew / Slofstra, William et al. | 2019
- 26
-
Barriers for Fast Matrix Multiplication from IrreversibilityChristandl, Matthias / Vrana, Péter / Zuiddam, Jeroen et al. | 2019
- 27
-
Hardness Magnification near State-Of-The-Art Lower BoundsOliveira, Igor Carboni / Pich, Ján / Santhanam, Rahul et al. | 2019
- 28
-
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal ConstructionsLi, Xin et al. | 2019
- 29
-
Optimal Separation and Strong Direct Sum for Randomized Query ComplexityBlais, Eric / Brody, Joshua et al. | 2019
- 30
-
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton TheoremsChen, Lijie / McKay, Dylan M. / Murray, Cody D. / Williams, R. Ryan et al. | 2019
- 31
-
A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph PropertiesBringmann, Karl / Fischer, Nick / Künnemann, Marvin et al. | 2019
- 32
-
Imperfect Gaps in Gap-ETH and PCPsBafna, Mitali / Vyas, Nikhil et al. | 2019