More Like this

1. 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
2. Systematic uncertainties in the characterization of helium-dominated metal-polluted white dwarf atmospheres

   https://doi.org/10.1093/mnras/stad282  

   Izquierdo, Paula ; Gänsicke, Boris T. ; Rodríguez-Gil, Pablo ; Koester, Detlev ; Toloza, Odette ; Gentile Fusillo, Nicola P. ; Pala, Anna F. ; Tremblay, Pier-Emmanuel ( January 2023 , Monthly Notices of the Royal Astronomical Society)

   White dwarf photospheric parameters are usually obtained by means of spectroscopic or photometric analysis. These results are not always consistent with each other, with the published values often including just the statistical uncertainties. The differences are more dramatic for white dwarfs with helium-dominated photospheres, so to obtain realistic uncertainties we have analysed a sample of 13 of these white dwarfs, applying both techniques to up to three different spectroscopic and photometric data sets for each star. We found mean standard deviations of $\left\langle \sigma {T_{\mathrm{eff}}}\right\rangle = 524$ K, $\left\langle \sigma {\log g}\right\rangle = 0.27$ dex and $\left\langle \sigma {\log (\mathrm{H/He})}\right\rangle = 0.31$ dex for the effective temperature, surface gravity, and relative hydrogen abundance, respectively, when modelling diverse spectroscopic data. The photometric fits provided mean standard deviations up to $\left\langle \sigma {T_{\mathrm{eff}}}\right\rangle = 1210$ K and $\left\langle \sigma {\log g}\right\rangle = 0.13$ dex. We suggest these values to be adopted as realistic lower limits to the published uncertainties in parameters derived from spectroscopic and photometric fits for white dwarfs with similar characteristics. In addition, we investigate the effect of fitting the observational data adopting three different photospheric chemical compositions. In general, pure helium model spectra result in larger Teff compared to those derived from models with traces of hydrogen. The log g shows opposite trends: smaller spectroscopic values and larger photometric ones when compared to models with hydrogen. The addition of metals to the models also affects the derived atmospheric parameters, but a clear trend is not found.

    

   more » « less
3. MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY

   https://doi.org/10.1017/jsl.2022.60  

   LEMPP, STEFFEN ; MILLER, JOSEPH S. ; NIES, ANDRÉ ; SOSKOVA, MARIYA I. ( August 2022 , The Journal of Symbolic Logic)

   Abstract The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$ , $G_{n+1} \subseteq ^* G_n$ , and $G_n\smallsetminus G_{n+1}$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $G_n$ . A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R , there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$ . Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. 

   more » « less
4. Robust Matrix Sensing in the Semi-Random Model

   Gao, Xing ; Cheng, Yu ( December 2023 , Proceedings of the 37th Conference on Neural Information Processing Systems)

   Low-rank matrix recovery is a fundamental problem in machine learning with numerous applications. In practice, the problem can be solved by convex optimization namely nuclear norm minimization, or by non-convex optimization as it is well-known that for low-rank matrix problems like matrix sensing and matrix completion, all local optima of the natural non-convex objectives are also globally optimal under certain ideal assumptions. In this paper, we study new approaches for matrix sensing in a semi-random model where an adversary can add any number of arbitrary sensing matrices. More precisely, the problem is to recover a low-rank matrix $X^\star$ from linear measurements $b_i = \langle A_i, X^\star \rangle$, where an unknown subset of the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the $A_i$'s are chosen adversarially. It is known that in the semi-random model, existing non-convex objectives can have bad local optima. To fix this, we present a descent-style algorithm that provably recovers the ground-truth matrix $X^\star$. For the closely-related problem of semi-random matrix completion, prior work [CG18] showed that all bad local optima can be eliminated by reweighting the input data. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which is a condition that is NP-hard to check. Instead, we build on the framework proposed in [KLL$^+$23] for semi-random sparse linear regression, where the algorithm in each iteration reweights the input based on the current solution, and then takes a weighted gradient step that is guaranteed to work well locally. Our analysis crucially exploits the connection between sparsity in vector problems and low-rankness in matrix problems, which may have other applications in obtaining robust algorithms for sparse and low-rank problems. 

   more » « less
5. Universal features of higher-form symmetries at phase transitions

   https://doi.org/10.21468/SciPostPhys.11.2.033  

   Wu, Xiao-Chuan ; Jian, Chao-Ming ; Xu, Cenke ( January 2021 , SciPost Physics)

   We investigate the behavior of higher-form symmetries at variousquantum phase transitions. We consider discrete 1-form symmetries, whichcan be either part of the generalized concept “categorical symmetry”(labelled as \tilde{Z}_N^{(1)} Z ̃ N ( 1 ) )introduced recently, or an explicit Z_N^{(1)} Z N ( 1 ) 1-form symmetry. We demonstrate that for many quantum phase transitionsinvolving a Z_N^{(1)} Z N ( 1 ) or \tilde{Z}_N^{(1)} Z ̃ N ( 1 ) symmetry, the following expectation value \langle \left( O_\mathcal{C}\right)^2 \rangle ⟨ ( O 𝒞 ) 2 ⟩ takes the form \langle \left( \log O_\mathcal{C} \right)^2 \rangle \sim - \frac{A}{\epsilon} P + b \log P ⟨ ( log O 𝒞 ) 2 ⟩ ∼ − A ϵ P + b log P , where O_\mathcal{C} O 𝒞 is an operator defined associated with loop \mathcal{C} 𝒞 (or its interior \mathcal{A} 𝒜 ),which reduces to the Wilson loop operator for cases with an explicit Z_N^{(1)} Z N ( 1 ) 1-form symmetry. P P is the perimeter of \mathcal{C} 𝒞 ,and the b \log P b log P term arises from the sharp corners of the loop \mathcal{C} 𝒞 ,which is consistent with recent numerics on a particular example. b b is a universal microscopic-independent number, which in (2+1)d ( 2 + 1 ) d is related to the universal conductivity at the quantum phasetransition. b b can be computed exactly for certain transitions using the dualitiesbetween (2+1)d ( 2 + 1 ) d conformal field theories developed in recent years. We also compute the"strange correlator" of O_\mathcal{C} O 𝒞 : S_{\mathcal{C}} = \langle 0 | O_\mathcal{C} | 1 \rangle / \langle 0 | 1 \rangle S 𝒞 = ⟨ 0 | O 𝒞 | 1 ⟩ / ⟨ 0 | 1 ⟩ where |0\rangle | 0 ⟩ and |1\rangle | 1 ⟩ are many-body states with different topological nature. 

   more » « less