Results 811 - 820 of 23794

Isomorphism of tensors is a basic notion in algebraic complexity. Recently, Grochow and Qiao uncovered connections between tensor isomorphism and isomorphism problems for groups, algebras, and polynomials, leading to the formulation of the Tensor Isomorphism complexity class. By varying the groups, actions, and underlying fields or rings, tensor isomorphism problems give rise to many connections and exhibit a range of complexity behaviours. For example:
1. Over finite fields, tensor isomorphism, like Graph Isomorphism, lies in NP ∩ coAM. Complexity reductions around tensor isomorphism play a key role in recent progress on Group Isomorphism (Ivanyos–Mendoza–Qiao–Sun–Zhang, FOCS 2024).
2. Over C, tensor isomorphism is in AM (Koiran, J. Complex.). Tensor isomorphism under unitary and orthogonal group actions naturally appears as an orbit-closure intersection problem.
3. Over Z, tensor isomorphism is decidable (Grunewald–Segal, Ann. Math., 1980). The 2×2×2 case over Z is central to Bhargava’s formulation of higher Gauss composition laws (Ann. Math., 2004), which in turn leads to a quantum polynomial-time algorithm via Hallgren’s algorithm for principal ideal testing (J. ACM, 2007).

Based on joint works with Josh Grochow, Kate Stange, Xiaorui Sun.

In this talk I will discuss covering numbers of real algebraic varieties and applications to computational mathematics.  Specifically, we control the number of ell_2 balls of radius epsilon needed to cover a real variety, image of a polynomial map, and semialgebraic set in Euclidean space, in terms of the degrees of the relevant polynomials and number of variables. The bound improves upon the best known general bound, and its proof is much more straightforward.  The result is applicable to computational problems in linear and multilinear algebra, and I will discuss consequences for CP tensor decomposition as well as randomized (polynomial) optimization.  

Beyond linear spaces and Riemannian manifolds, geodesic metric spaces of nonpositive curvature, also known as Hadamard spaces when complete, provide a suitable framework for developing convex optimization. Familiar examples include Hilbert spaces and complete simply connected Riemannian manifolds of nonpositive sectional curvature, but also other spaces that are not manifolds such as CAT(0) cubical complexes. In the particular latter setting, by decomposing into Euclidean cubes, geodesically convex optimization problems can be addressed by appropriately applying some standard Euclidean convex optimization techniques. In general Hadamard spaces, geodesically convex optimization methods based on proximal steps have been developed in recent years, but they are rarely implementable. While Riemannian subgradient algorithms make use of tangent space constructions and local linearization, understanding subgradients and the algorithms relying on them is less straightforward in Hadamard spaces. By using horoballs and Busemann functions, we explore subgradient-style methods for objectives satisfying convexity conditions that are distinct from geodesic convexity. The algorithms are framed within the underlying space and the derived complexity bounds match those typically obtained in Euclidean space.

Spectral gaps play a fundamental role in many areas of mathematics, computer science, and physics. In quantum mechanics, the spectral gap of Schrödinger operators has a long history of study due to its physical relevance, while in quantum computing spectral gaps are an important proxy for efficiency, such as in the quantum adiabatic algorithm. Motivated by convex optimization, we study Schrödinger operators associated with self-concordant barriers over convex domains and prove non-asymptotic lower bounds on the spectral gap for this class of operators. Significantly, we find that the spectral gap does not display any condition-number dependence when the usual Laplacian is replaced by the Laplace--Beltrami operator, which uses second-order information of the barrier and hence can take the curvature of the barrier into account. As an algorithmic application, we construct a novel quantum interior point method that applies to arbitrary self-concordant barriers and shows no condition-number dependence. To achieve this, we combine techniques from semiclassical analysis, convex optimization, and quantum annealing.

A tensor is a multidimensional array of numbers that can be used to store data, encode a computational relation and represent quantum entanglement. In this sense a tensor can be viewed as valuable resource whose transformation can lead to an understanding of structure in data, computational complexity and quantum information.
In order to facilitate the understanding of this resource, we propose a family of information-theoretically constructed preorders on tensors, which can be used to compare tensors with each other and to assess the existence of transformations between them. The construction places copies of a given tensor at the edges of a hypergraph and allows transformations at the vertices. A preorder is then induced by the transformations possible in a given growing sequence of hypergraphs. The new family of preorders generalises the asymptotic restriction preorder which Strassen defined in order to study the computational complexity of matrix multiplication.
We derive general properties of the preorders and their associated asymptotic notions of tensor rank and view recent results on tensor rank non-additivity, tensor networks and algebraic complexity in this unifying frame. We hope that this work will provide a useful vantage point for exploring tensors in applied mathematics, physics and computer science, but also from a purely mathematical point of view.

In this talk, we address the optimization problem of minimizing Q(df_x) over a Hadamard manifold M, where f is a convex function on M, df_x is the differential of f at x in M, and
Q is a function on the cotangent bundle of M. This problem generalizes the problem of minimizing the gradient norm of f over M, studied by Hirai and Sakabe FOCS2024. We formulate a natural class of Q in terms of convexity and invariance under parallel transports, and introduce a generalization of the gradient flow of f that is expected to minimize Q(df_x).
Through the limit of this gradient flow, we establish the duality of the infimum of Q(df_x) for fundamental classes of manifolds, including the product of the manifolds of positive definite matrices. This result is applied to Kempf-Ness optimization for the GL-action on tensors, which is Euclidean convex optimization on the class of moment polytopes, called the entanglement polytopes. This type of convex optimization arises from tensor-related subjects in theoretical computer science, such as quantum functional, G-stable rank, and noncommutative rank.