More Like this

1. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits

   https://doi.org/10.1145/3406325.3451096  

   Bhargava, Vishwas ; Saraf, Shubhangi ; Volkovich, Ilya ( June 2021 , STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’). 

   more » « less
2. Type 𝐼𝐼 quantum subgroups of 𝔰𝔩_{𝔑}. ℑ: Symmetries of local modules

   https://doi.org/10.1090/cams/19  

   Edie-Michell, Cain ( May 2023 , Communications of the American Mathematical Society)

   This paper is the first of a pair that aims to classify a large number of the type I I II quantum subgroups of the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . In this work we classify the braided auto-equivalences of the categories of local modules for all known type I I quantum subgroups of C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . We find that the symmetries are all non-exceptional except for four cases (up to level-rank duality). These exceptional cases are the orbifolds C ( s l 2 , 16 ) Rep ⁡ ( Z 2 ) 0 \mathcal {C}(\mathfrak {sl}_{2}, 16)^0_{\operatorname {Rep}(\mathbb {Z}_{2})} , C ( s l 3 , 9 ) Rep ⁡ ( Z 3 ) 0 \mathcal {C}(\mathfrak {sl}_{3}, 9)^0_{\operatorname {Rep}(\mathbb {Z}_{3})} , C ( s l 4 , 8 ) Rep ⁡ ( Z 4 ) 0 \mathcal {C}(\mathfrak {sl}_{4}, 8)^0_{\operatorname {Rep}(\mathbb {Z}_{4})} , and C ( s l 5 , 5 ) Rep ⁡ ( Z 5 ) 0 \mathcal {C}(\mathfrak {sl}_{5}, 5)^0_{\operatorname {Rep}(\mathbb {Z}_{5})} . We develop several technical tools in this work. We give a skein theoretic description of the orbifold quantum subgroups of C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . Our methods here are general, and the techniques developed will generalise to give skein theory for any orbifold of a braided tensor category. We also give a formulation of orthogonal level-rank duality in the type D D - D D case, which is used to construct one of the exceptionals. We uncover an unexpected connection between quadratic categories and exceptional braided auto-equivalences of the orbifolds. We use this connection to construct two of the four exceptionals. In the sequel to this paper we will use the classified braided auto-equivalences to construct the corresponding type I I II quantum subgroups of the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . This will essentially finish the type I I II classification for s l n \mathfrak {sl}_n modulo type I I classification. When paired with Gannon’s type I I classification for r ≤ 6 r\leq 6 , our results will complete the type I I II classification for these same ranks. This paper includes an appendix by Terry Gannon, which provides useful results on the dimensions of objects in the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . 

   more » « less
3. Anisotropic dielectric function, direction dependent bandgap energy, band order, and indirect to direct gap crossover in α -(Al x Ga 1−x ) 2 O 3 (0≤x≤1)

   https://doi.org/10.1063/5.0087602  

   Hilfiker, Matthew ; Kilic, Ufuk ; Stokey, Megan ; Jinno, Riena ; Cho, Yongjin ; Xing, Huili Grace ; Jena, Debdeep ; Korlacki, Rafał ; Schubert, Mathias ( August 2022 , Applied Physics Letters)

   Mueller matrix spectroscopic ellipsometry is applied to determine anisotropic optical properties for a set of single-crystal rhombohedral structure α-(Al x Ga 1− x ) 2 O 3 thin films (0 [Formula: see text] x [Formula: see text] 1). Samples are grown by plasma-assisted molecular beam epitaxy on m-plane sapphire. A critical-point model is used to render a spectroscopic model dielectric function tensor and to determine direct electronic band-to-band transition parameters, including the direction dependent two lowest-photon energy band-to-band transitions associated with the anisotropic bandgap. We obtain the composition dependence of the direction dependent two lowest band-to-band transitions with separate bandgap bowing parameters associated with the perpendicular ([Formula: see text] = 1.31 eV) and parallel ([Formula: see text] = 1.61 eV) electric field polarization to the lattice c direction. Our density functional theory calculations indicate a transition from indirect to direct characteristics between α-Ga 2 O 3 and α-Al 2 O 3 , respectively, and we identify a switch in band order where the lowest band-to-band transition occurs with polarization perpendicular to c in α-Ga 2 O 3 whereas for α-Al 2 O 3 the lowest transition occurs with polarization parallel to c. We estimate that the change in band order occurs at approximately 40% Al content. Additionally, the characteristic of the lowest energy critical point transition for polarization parallel to c changes from M 1 type in α-Ga 2 O 3 to M 0 type van Hove singularity in α-Al 2 O 3 . 

   more » « less
4. New lower bounds for matrix multiplication and

   https://doi.org/10.1017/fmp.2023.14  

   Conner, Austin ; Harper, Alicia ; Landsberg, J.M. ( January 2023 , Forum of Mathematics, Pi)

   Let$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$denote the matrix multiplication tensor (and write$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$), and let$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$denote the determinant polynomial considered as a tensor. For a tensorT, let$\underline {\mathbf {R}}(T)$denote its border rank. We (i) give the first hand-checkable algebraic proof that$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$, (ii) prove$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$and$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$M_{\langle 2\rangle }$, (iii) prove$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$, (iv) prove$\underline {\mathbf {R}}(\operatorname {det}_3)=17$, improving the previous lower bound of$12$, (v) prove$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$for all$\mathbf {n}\geq 25$, where previously only$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$was known, as well as lower bounds for$4\leq \mathbf {n}\leq 25$, and (vi) prove$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$for all$\mathbf {n} \ge 18$, where previously only$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors.

   The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, calledborder apolaritydeveloped by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorTand an integerr, in a finite number of steps, either outputs that there is no border rankrdecomposition forTor produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenThas a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory.

    

   more » « less
5. Kronecker Powers of Tensors and Strassen’s Laser Method

   https://doi.org/10.4230/LIPIcs.ITCS.2020.10  

   Conner, Austin ; Landsberg, Joseph M. ; Gesmundo, Fulvio ; Ventura, Emanuele ( April 2020 , 11th Innovations in Theoretical Computer Science Conference (ITCS 2020))

   We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3. 

   more » « less