Kronecker Powers of Tensors and Strassen’s Laser Method (English)
Free access
- New search for: Conner, Austin
- New search for: Landsberg, Joseph M.
- New search for: Gesmundo, Fulvio
- Further information on Gesmundo, Fulvio:
- https://orcid.org/0000-0001-6402-021X
- New search for: Ventura, Emanuele
- Further information on Ventura, Emanuele:
- https://orcid.org/0000-0002-6035-309X
- New search for: Conner, Austin
- New search for: Landsberg, Joseph M.
- New search for: Gesmundo, Fulvio
- Further information on Gesmundo, Fulvio:
- https://orcid.org/0000-0001-6402-021X
- New search for: Ventura, Emanuele
- Further information on Ventura, Emanuele:
- https://orcid.org/0000-0002-6035-309X
- New search for: Vidick, Thomas
In:
LIPIcs, Volume 151, ITCS 2020
: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
;
151
;
10:1-10:28
;
2020
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Kronecker Powers of Tensors and Strassen’s Laser Method
-
Contributors:Conner, Austin ( author ) / Landsberg, Joseph M. ( author ) / Gesmundo, Fulvio ( author ) / Ventura, Emanuele ( author ) / Vidick, Thomas ( editor )
-
Published in:LIPIcs, Volume 151, ITCS 2020 : 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) ; 151 ; 10:1-10:28Leibniz International Proceedings in Informatics (LIPIcs) ; 151 ; 10:1-10:28
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2020-01-06
-
Size:28 pages , 706294 byte
-
Remarks:LIPIcs, Vol. 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pages 10:1-10:28
-
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
-
Hardness Amplification of Optimization ProblemsGoldenberg, Elazar / Karthik C. S. et al. | 2020
- 2
-
Smooth and Strong PCPsParadise, Orr et al. | 2020
- 3
-
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-ConsistenceSchvartzman, Ariel / Weinberg, S. Matthew / Zlatin, Eitan / Zuo, Albert et al. | 2020
- 4
-
Span Programs and Quantum Space ComplexityJeffery, Stacey et al. | 2020
- 5
-
DEEP-FRI: Sampling Outside the Box Improves SoundnessBen-Sasson, Eli / Goldberg, Lior / Kopparty, Swastik / Saraf, Shubhangi et al. | 2020
- 6
-
On the Cryptographic Hardness of Local SearchBitansky, Nir / Gerichter, Idan et al. | 2020
- 7
-
Interactive Coding with Constant Round and Communication BlowupEfremenko, Klim / Haramaty, Elad / Kalai, Yael Tauman et al. | 2020
- 8
-
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix SpacesBei, Xiaohui / Chen, Shiteng / Guan, Ji / Qiao, Youming / Sun, Xiaoming et al. | 2020
- 9
-
Hard Properties with (Very) Short PCPPs and Their ApplicationsBen-Eliezer, Omri / Fischer, Eldar / Levi, Amit / Rothblum, Ron D. et al. | 2020
- 10
-
Kronecker Powers of Tensors and Strassen’s Laser MethodConner, Austin / Landsberg, Joseph M. / Gesmundo, Fulvio / Ventura, Emanuele et al. | 2020
- 11
-
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse GraphsLincoln, Andrea / Vyas, Nikhil et al. | 2020
- 12
-
High-Dimensional Expanders from ExpandersLiu, Siqi / Mohanty, Sidhanth / Yang, Elizabeth et al. | 2020
- 13
-
Approximating Cumulative Pebbling Cost Is Unique Games HardBlocki, Jeremiah / Lee, Seunghoon / Zhou, Samson et al. | 2020
- 14
-
Scheduling with Predictions and the Price of MispredictionMitzenmacher, Michael et al. | 2020
- 15
-
Reducing Inefficiency in Carbon Auctions with Imperfect CompetitionGoldner, Kira / Immorlica, Nicole / Lucier, Brendan et al. | 2020
- 16
-
Preference-Informed FairnessKim, Michael P. / Korolova, Aleksandra / Rothblum, Guy N. / Yona, Gal et al. | 2020
- 17
-
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of HCai, Jin-Yi / Govorov, Artem et al. | 2020
- 18
-
Tarski’s Theorem, Supermodular Games, and the Complexity of EquilibriaEtessami, Kousha / Papadimitriou, Christos / Rubinstein, Aviad / Yannakakis, Mihalis et al. | 2020
- 19
-
Resolution with Counting: Dag-Like Lower Bounds and Different ModuliPart, Fedor / Tzameret, Iddo et al. | 2020
- 20
-
The Random-Query Model and the Memory-Bounded Coupon CollectorRaz, Ran / Zhan, Wei et al. | 2020
- 21
-
Strategy-Stealing Is Non-ConstructiveBodwin, Greg / Grossman, Ofer et al. | 2020
- 22
-
Distribution-Free Testing of Linear Functions on ℝⁿFleming, Noah / Yoshida, Yuichi et al. | 2020
- 23
-
Random Sketching, Clustering, and Short-Term Memory in Spiking Neural NetworksHitron, Yael / Lynch, Nancy / Musco, Cameron / Parter, Merav et al. | 2020
- 24
-
Signed Tropical ConvexityLoho, Georg / Végh, László A. et al. | 2020
- 25
-
Distributional Property Testing in a Quantum WorldGilyén, András / Li, Tongyang et al. | 2020
- 26
-
On Local Testability in the Non-Signaling SettingChiesa, Alessandro / Manohar, Peter / Shinkar, Igor et al. | 2020
- 27
-
Local Access to Huge Random Objects Through Partial SamplingBiswas, Amartya Shankha / Rubinfeld, Ronitt / Yodpinyanee, Anak et al. | 2020
- 28
-
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear SamplesRubinfeld, Ronitt / Vasilyan, Arsen et al. | 2020
- 29
-
Sample Complexity Bounds for Influence MaximizationSadeh, Gal / Cohen, Edith / Kaplan, Haim et al. | 2020
- 30
-
On Oblivious Amplification of Coin-Tossing ProtocolsBitansky, Nir / Geier, Nathan et al. | 2020
- 31
-
A New Analysis of Differential Privacy’s Generalization GuaranteesJung, Christopher / Ligett, Katrina / Neel, Seth / Roth, Aaron / Sharifi-Malvajerdi, Saeed / Shenfeld, Moshe et al. | 2020
- 32
-
Robust Algorithms for the Secretary ProblemBradac, Domagoj / Gupta, Anupam / Singla, Sahil / Zuzic, Goran et al. | 2020
- 33
-
Universal Communication, Universal Graphs, and Graph LabelingHarms, Nathaniel et al. | 2020
- 34
-
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]Ilango, Rahul et al. | 2020
- 35
-
Equivalence of Systematic Linear Data Structures and Matrix RigidityNatarajan Ramamoorthy, Sivaramakrishnan / Rashtchian, Cyrus et al. | 2020
- 36
-
Computationally Data-Independent Memory Hard FunctionsAmeri, Mohammad Hassan / Blocki, Jeremiah / Zhou, Samson et al. | 2020
- 37
-
Learning and Testing Variable PartitionsBogdanov, Andrej / Wang, Baoxiang et al. | 2020
- 38
-
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size SixBera, Suman K. / Pashanasangi, Noujan / Seshadhri, C. et al. | 2020
- 39
-
Parameterization Above a Multiplicative GuaranteeFomin, Fedor V. / Golovach, Petr A. / Lokshtanov, Daniel / Panolan, Fahad / Saurabh, Saket / Zehavi, Meirav et al. | 2020
- 40
-
Ad Hoc Multi-Input Functional EncryptionAgrawal, Shweta / Clear, Michael / Frieder, Ophir / Garg, Sanjam / O'Neill, Adam / Thaler, Justin et al. | 2020
- 41
-
Unexpected Power of Random StringsHirahara, Shuichi et al. | 2020
- 42
-
Consensus vs Broadcast, with and Without Noise (Extended Abstract)Clementi, Andrea / Gualà, Luciano / Natale, Emanuele / Pasquale, Francesco / Scornavacca, Giacomo / Trevisan, Luca et al. | 2020
- 43
-
Testing Linear Inequalities of Subgraph StatisticsGishboliner, Lior / Shapira, Asaf / Stagni, Henrique et al. | 2020
- 44
-
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent LimitationsBlanc, Guy / Lange, Jane / Tan, Li-Yang et al. | 2020
- 45
-
Algorithms and Adaptivity Gaps for Stochastic k-TSPJiang, Haotian / Li, Jian / Liu, Daogao / Singla, Sahil et al. | 2020
- 46
-
Strategic Payments in Financial NetworksBertschinger, Nils / Hoefer, Martin / Schmand, Daniel et al. | 2020
- 47
-
Fault Tolerant Subgraphs with Applications in KernelizationLochet, William / Lokshtanov, Daniel / Misra, Pranabendu / Saurabh, Saket / Sharma, Roohani / Zehavi, Meirav et al. | 2020
- 48
-
The Computational Cost of Asynchronous Neural CommunicationHitron, Yael / Parter, Merav / Perri, Gur et al. | 2020
- 49
-
Certified Algorithms: Worst-Case Analysis and BeyondMakarychev, Konstantin / Makarychev, Yury et al. | 2020
- 50
-
Low Diameter Graph Decompositions by Approximate Distance ComputationBecker, Ruben / Emek, Yuval / Lenzen, Christoph et al. | 2020
- 51
-
Generalized List DecodingZhang, Yihan / Budkuley, Amitalok J. / Jaggi, Sidharth et al. | 2020
- 52
-
Online Computation with Untrusted AdviceAngelopoulos, Spyros / Dürr, Christoph / Jin, Shendan / Kamali, Shahin / Renault, Marc et al. | 2020
- 53
-
Monochromatic Triangles, Intermediate Matrix Products, and ConvolutionsLincoln, Andrea / Polak, Adam / Vassilevska Williams, Virginia et al. | 2020
- 54
-
Matching Is as Easy as the Decision Problem, in the NC ModelAnari, Nima / Vazirani, Vijay V. et al. | 2020
- 55
-
Advancing Subgroup Fairness via Sleeping ExpertsBlum, Avrim / Lykouris, Thodoris et al. | 2020
- 56
-
Instance Complexity and Unlabeled Certificates in the Decision Tree ModelGrossman, Tomer / Komargodski, Ilan / Naor, Moni et al. | 2020
- 57
-
On the Impossibility of Probabilistic Proofs in Relativized WorldsChiesa, Alessandro / Liu, Siqi et al. | 2020
- 58
-
Lower Bounds for (Non-Monotone) Comparator CircuitsGál, Anna / Robere, Robert et al. | 2020
- 59
-
A Tight Lower Bound For Non-Coherent Index ErasureLindzey, Nathan / Rosmanis, Ansis et al. | 2020
- 60
-
Optimal Single-Choice Prophet Inequalities from SamplesRubinstein, Aviad / Wang, Jack Z. / Weinberg, S. Matthew et al. | 2020
- 61
-
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-HardCai, Linda / Thomas, Clay / Weinberg, S. Matthew et al. | 2020
- 62
-
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games HardDemaine, Erik D. / Hendrickson, Dylan H. / Lynch, Jayson et al. | 2020
- 63
-
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)Bouland, Adam / Fefferman, Bill / Vazirani, Umesh et al. | 2020
- 64
-
New Query Lower Bounds for Submodular Function MinimizationGraur, Andrei / Pollner, Tristan / Ramaswamy, Vidhya / Weinberg, S. Matthew et al. | 2020
- 65
-
Computation-Aware Data AggregationHaeupler, Bernhard / Hershkowitz, D. Ellis / Kahng, Anson / Procaccia, Ariel D. et al. | 2020
- 66
-
Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed StorageMaturana, Francisco / Rashmi, K. V. et al. | 2020
- 67
-
Incentive Compatible Active LearningEchenique, Federico / Prasad, Siddharth et al. | 2020
- 68
-
Pseudorandomness and the Minimum Circuit Size ProblemSanthanam, Rahul et al. | 2020
- 69
-
Testing Properties of Multiple Distributions with Few SamplesAliakbarpour, Maryam / Silwal, Sandeep et al. | 2020
- 70
-
Beyond Natural Proofs: Hardness Magnification and LocalityChen, Lijie / Hirahara, Shuichi / Oliveira, Igor C. / Pich, Ján / Rajgopal, Ninad / Santhanam, Rahul et al. | 2020
- 71
-
Separating Two-Round Secure Computation From Oblivious TransferApplebaum, Benny / Brakerski, Zvika / Garg, Sanjam / Ishai, Yuval / Srinivasan, Akshayaram et al. | 2020
- 72
-
Trade-Offs Between Size and Degree in Polynomial CalculusLagarde, Guillaume / Nordström, Jakob / Sokolov, Dmitry / Swernofsky, Joseph et al. | 2020
- 73
-
Smoothed Efficient Algorithms and Reductions for Network Coordination GamesBoodaghians, Shant / Kulkarni, Rucha / Mehta, Ruta et al. | 2020
- 74
-
Local-To-Global Agreement Expansion via the Variance MethodKaufman, Tali / Mass, David et al. | 2020
- 75
-
MPC for MPC: Secure Computation on a Massively Parallel Computing ArchitectureChan, T-H. Hubert / Chung, Kai-Min / Lin, Wei-Kai / Shi, Elaine et al. | 2020
- 76
-
Choice and Bias in Random WalksGeorgakopoulos, Agelos / Haslegrave, John / Sauerwald, Thomas / Sylvester, John et al. | 2020
- 77
-
Graph Spanners in the Message-Passing ModelFernández V, Manuel / Woodruff, David P. / Yasuda, Taisuke et al. | 2020
- 78
-
Computational Hardness of Certifying Bounds on Constrained PCA ProblemsBandeira, Afonso S. / Kunisky, Dmitriy / Wein, Alexander S. et al. | 2020
- 79
-
Pseudo-Deterministic StreamingGoldwasser, Shafi / Grossman, Ofer / Mohanty, Sidhanth / Woodruff, David P. et al. | 2020
- 80
-
Limits to Non-MalleabilityBall, Marshall / Dachman-Soled, Dana / Kulkarni, Mukul / Malkin, Tal et al. | 2020
- 81
-
Cryptography from Information LossBall, Marshall / Boyle, Elette / Degwekar, Akshay / Deshpande, Apoorvaa / Rosen, Alon / Vaikuntanathan, Vinod / Vasudevan, Prashant Nalini et al. | 2020
- 82
-
Affine Determinant Programs: A Framework for Obfuscation and Witness EncryptionBartusek, James / Ishai, Yuval / Jain, Aayush / Ma, Fermi / Sahai, Amit / Zhandry, Mark et al. | 2020
- 83
-
OV Graphs Are (Probably) Hard InstancesAlman, Josh / Vassilevska Williams, Virginia et al. | 2020
- 84
-
Finding Skewed Subcubes Under a DistributionGopalan, Parikshit / Levin, Roie / Wieder, Udi et al. | 2020
- 85
-
Combinatorial Lower Bounds for 3-Query LDCsBhattacharyya, Arnab / Chandran, L. Sunil / Ghoshal, Suprovat et al. | 2020
- 86
-
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?Ball, Marshall / Holmgren, Justin / Ishai, Yuval / Liu, Tianren / Malkin, Tal et al. | 2020