Shonan Meeting 246

About

Isomorphism problems for algebraic structures form a central family of algorithmic questions, with connections to graph isomorphism, group isomorphism, computer algebra, cryptography, quantum information, and algebraic geometry. The meeting aims to create space for tutorials, research talks, open problems, and informal discussion on the algorithmic, geometric, and applied aspects of tensor isomorphism.

Dates: May 25-29, 2026

Check-in: May 24, 2026

Venue: Shonan Village Center ( Directions)

Official page: NII Shonan Meeting No. 246

Organizers:

Topics

The meeting will center on three themes.

1. Algorithms for the Tensor Isomorphism Problem. Tensor isomorphism asks whether two tensors are equivalent under local general linear group actions. This theme will discuss faster algorithms for tensor isomorphism and related algebraic isomorphism problems, including connections with group isomorphism.
2. Algebraic and geometric structure of tensor isomorphism. This theme will explore algebraic and geometric tools for tensors, including structures such as associated algebras and hypersurfaces, and their role in algorithms.
3. Applications of the Tensor Isomorphism Problem. This theme will cover applications in areas such as cryptography, quantum information, computer algebra, graph theory, group theory, representation theory, and the enumeration of algebraic structures.

Schedule

Check-in: Sunday, May 24 15:00 – 19:00

Welcome Banquet: Sunday, May 24 19:00 – 21:00

Tutorials:

• Youming Qiao. Tensor isomorphism: Algorithms and complexity
• James Wilson. Algebraic and geometric methods for tensor isomorphism
• Christian Ikenmeyer. Tensors in algebraic complexity theory and matrix multiplication

Titles and Abstracts

Youming Qiao

Tensor Isomorphism: Algorithms and Complexity

In this tutorial, we survey the complexity and algorithms of the tensor isomorphism problem. After introducing the basic definitions, we explain how tensor isomorphism serves as a unifying framework for several central isomorphism problems, including those for graphs, groups, polynomials, and algebras. We also discuss its relevance to cryptography and quantum information. We then turn to algorithmic developments, covering worst-case, average-case, and heuristic approaches. Along the way, we explain how the algorithmic study of tensor isomorphism naturally leads to questions in invariant theory and random matrix theory.

Nitin Saxena

Primes via zeros: interactive proofs for testing primality of natural classes of ideals

Given a set of polynomials as an algebraic circuit, we study the problem of testing if the ideal generated by these polynomials is prime. This is a generalisation of the problem of testing if the polynomials have a common solution. It is also a generalisation of the problem of testing if a polynomial is absolutely irreducible. Assuming GRH, we show that for certain classes of ideals, namely radical ideals and complete intersection ideals, the problem of testing primality lies in the third level of the polynomial hierarchy. This is almost optimal since the problems are NP-hard. Previously, the best known bound for these problems was PSPACE.

Our method is a vast generalisation of the method used by Koiran to show that satisfiability of polynomials is in PH. We study how algebraic and geometric properties of ideals such as irreducibility and dimension behave under mod p reduction of coefficients. We give new effective versions of classical results from algebraic geometry and commutative algebra that may have independent applications.

This is joint work with Abhibhav Garg and Rafael Oliveira; presented in STOC 2025.

https://www.cse.iitk.ac.in/users/nitin/research.html

Pascal Schweitzer

Tensor isomorphism’s older, smaller, and tenacious sibling: the graph isomorphism problem

From the perspective of tensor isomorphism, the graph isomorphism problem appears as a special case. It captures isomorphism questions for algebraic structures after the surrounding algebraic context has been stripped away. Conversely, one may view it as the isomorphism problem for combinatorial objects given in an explicit, “verbose” representation, whereas tensor isomorphism deals with more succinct descriptions via generators within an algebraic framework.

In this talk, I will survey recent advances on the graph isomorphism problem. In particular, I will discuss developments related to the complexity of the Weisfeiler-Leman algorithm, a well-known combinatorial approach to graph isomorphism. I will highlight its connections to logic and combinatorial games, and discuss current limitations in our understanding, especially regarding its behavior on groups.

Antoine Joux

Indefiniteness makes lattice reduction easier

Since the invention of the famous LLL algorithm, lattice reduction has been an extremely useful tool in computational number theory. By construction, the LLL algorithm deals with lattices living in a vector space endowed with a positive definite scalar product. However, it seems quite natural to ask about the indefinite case, where the scalar product is replaced by an arbitrary quadratic form, possibly indefinite. This question was considered independently in two lines of work, one by Gábor Ivanyos and Ágnes Szántó and one by Denis Simon. Both lines lead to an algorithm that generalizes LLL and whose performance is very similar to LLL, namely a polynomial-time algorithm that approximates the shortest vector within an approximation factor that is exponential in the dimension. Denis Simon achieves an approximation factor close to that of LLL under the assumption that no isotropic vectors arise during reduction. Gábor Ivanyos and Ágnes Szántó show that it is possible to avoid isotropic vectors altogether, at the cost of a somewhat worse approximation factor. In this talk, we revisit the reduction of indefinite lattices and conclude that it can lead to much better reduced representations than previously thought. We also conclude that the approximation factor depends on the signature of the indefinite lattice rather than on its dimension.

Fang Song

Continuous HSP

In this talk, I will introduce the continuous hidden subgroup problem (CHSP), an extension of HSP to certain continuous groups. I will present an efficient quantum algorithm to solve it, and applications in basic algebraic number-theory problems. Based on joint work with Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Jean-François Biasse.

James Wilson

On the missing structure in tensors

While it is hard to compare two tensors, once an isomorphism is declared it is easy to verify that it is an isomorphism. But when two tensors are declared non-isomorphic, the evidence is a grab bag of esoteric or complex machine calculations depending on a host of declared and implicit conventions. Such invariants are difficult to reproduce exactly by independent analysis.

We will survey the history of counting, comparing, and classifying tensors and their related objects in algebra in search for what should qualify as “invariant structure” and conclude with constructions that seem to suggest such structure may not actually exist.

Colva Roney-Dougal

Computing normalisers of permutation groups

The normaliser problem takes as input generating sets for two subgroups G and H of some symmetric group S_n, and asks one to compute generators for the normaliser in G of H. Since each element of N_G(H) induces an automorphism of H, there is a natural connection to the isomorphism problem. I will give a survey of the area.

Bettina Eick

On the isomorphism problem for finite p-groups

The talk reviews practical methods for solving the isomorphism problem of finite p-groups and their application in the classification and enumeration of finite p-groups. The basic ideas of these methods go back to 1990 and have been continued and developed further since then. This talk recalls the basic ideas and also exhibits some of the recent developments.

Christopher Voll

Tensor invariants and poles of local zeta functions

Tensors are a natural language in which to cast questions about commutator structures of algebraic structures such as groups or (Lie) rings. Various zeta functions offer an analytic perspective on enumerative and asymptotic questions on the distribution of subgroups or subrings. I would like to advertise such zeta functions as tensor invariants. More specifically, I will invite you to view the pole spectra of local zeta functions associated with certain tensors as measures of the singularity complexity of these tensors. As I will explain, this perspective is informed by an analogy with the Monodromy Conjecture, a long-standing conjecture in the singularity theory of complex algebraic varieties. I will assume no knowledge about any of the technical terms featuring in this abstract, but rather explain things from scratch, illustrated by examples.

Tobias Rossmann

Enumeration via tensors

Algebra, particularly group theory, provides a rich source of counting problems that can be approached through generating functions associated with tensors. Isomorphisms and weaker equivalence relations between tensors thus become tools for establishing identities between generating functions. I will discuss (and speculate on) algebraic, arithmetic, and geometric invariants of tensors that are (or might be) useful in this context.

Dhara Thakkar

Group Order and Group Non-Membership is in QCMA

In this talk, I will discuss recent progress on the role of classical proofs in quantum complexity theory, focusing on group-theoretic problems in the black-box model. In particular, I will present QCMA protocols for two long-standing open questions in this area. First, we show that the Group Non-Membership problem, known to lie in QMA but not in MA, is in fact in QCMA, settling a 2006 conjecture by Aaronson and Kuperberg. This result follows from a more general result that the Group Order Verification problem lies in QCMA, answering an open question posed by Watrous in 2000. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box group settings.

This talk is based on joint work with François Le Gall and Harumichi Nishimura.

Peter Brooksbank

Testing for isometry in polynomial time

This talk concerns the following computational problem: given two Hermitian maps between vector spaces over a finite field, decide if they are isometric. Aspects of this problem have been investigated for over 40 years by several communities of researchers with various motivations, but its main relevance to the current program comes from its applications to isomorphism testing in tensors and finite p-groups. It was shown in 2012 that the problem can be solved in polynomial time for fields of odd characteristic, but a satisfactory solution for the characteristic 2 case has remained elusive. In this talk, I will discuss some of the key ideas from joint work with Martin Kassabov and James Wilson that extends the result to fields of characteristic 2.

Harold Nieuwboer

Moment polytopes as a tensor monotone

Moment polytopes are a classical object arising in symplectic geometry and geometric invariant theory. They have been studied in the context of tensor rank and the GCT programme (Bürgisser-Ikenmeyer STOC’11) but until recently not much was known about their power as a degeneration monotone. I will survey recent results on this subject, and discuss future directions. Based on joint works with M. van den Berg, M. Christandl, V. Lysikov, M. Walter and J. Zuiddam.

J. M. Landsberg

Centroids and symmetries of tensors, and applications to the complexity of matrix multiplication and tensor isomorphism

Centroids have a long history. They were re-discovered by J. Jelisiejew, A. Pal, and me while proving complexity lower bounds for tensors. Symmetry groups of tensors have an even longer history. I will describe connections between these two tensor invariants and applications to tensor isomorphism (work with J. Jelisiejew and A. Pal, as well as F. Gesmundo, Jelisiejew, and T. Mandziuk), upper bounds on the exponent of matrix multiplication, and explicit border rank decompositions of tensors (work with M. Kassabov, V. Souza, and P. Speegle).

Nick Vannieuwenhoven

Reshape, project, and chisel for structured tensor decompositions

We will present refinements of the chiseling framework by Brooksbank, Kassabov, and Wilson (2024), suitable for extracting the elementary structured tensors of a structured tensor known to admit a particular structured tensor decomposition. We propose an extraction procedure based on (i) reshaping to a third-order tensor, (ii) projecting to a low-dimensional subspace along the third factor, and (iii) applying an adjoint chisel. This procedure applies to broad families of tensors satisfying mild algebraic assumptions, such as Segre, Veronese, subspace, Chow, and Grassmann decompositions. Some results on the computational complexity of this procedure will be presented.

This presentation is based on joint works with Daniele Taufer, David Thorsteinsson, and Tim Seynnaeve.

Michael Levet

Circuit Complexity Landscape of the Isomorphism Problem for Groups and Quasigroups

The Quasigroup Isomorphism (QGpI) problem takes as input two quasigroups G and H, given by their multiplication tables, and asks if G is isomorphic to H. QGpI is known to be strictly easier than Graph Isomorphism (GI), under AC⁰-reductions (Chattopadhyay, Torán, and Wagner; FSTTCS 2010, ACM Trans. Comput. Theory 2013). In the setting of GI, the best known lower bound is DET (Torán; SIAM J. Comput. 2004). On the other hand, the work of Chattopadhyay, Torán, and Wagner (ibid.) rules out standard techniques for obtaining circuit lower bounds, including low-depth reductions from Parity and Majority to QGpI. In particular, lower bounds even against depth-2 AC circuits remain open for QGpI.

In this talk, we will discuss recent advances in the circuit complexity landscape for QGpI, including a new upper bound using depth-4 AC circuits of size n^{O(log n)}. Additionally, this talk will highlight NC algorithms for isomorphism testing of several important families, including Abelian groups, coprime extensions, Fitting-free groups, and central quasigroups. In the process, we also obtain an unconditional separation in the descriptive complexity of Abelian groups vs. Fitting-free groups. Our results leverage a diverse range of techniques, including the Weisfeiler-Leman algorithm, permutation group algorithms, and simultaneously time-space bounded Turing machines.

These works are the result of collaborations with Nathaniel A. Collins, Joshua A. Grochow, Dan Johnson, Petr Vojtěchovský, Armin Weiß, and Brett Widholm.

Steven Duong

Tensor Isomorphism and Post-Quantum Signatures

Alternating trilinear forms give a natural family of structured tensors with an action of the general linear group. Their associated equivalence problem has been considered as a possible foundation for post-quantum digital signatures. In this talk, I will discuss how signature constructions motivate computational questions in tensor isomorphism, using alternating trilinear forms as a guiding example.

Martin Kassabov

Tensors with Large Centroids

The centroid of a (non-degenerate) tensor of valency d and size n is a commutative subalgebra of the algebra of n x n matrices. If this algebra is semisimple, then it is straightforward to see that it has dimension at most n; however, there are significantly larger commutative subalgebras of dimension n²/4. We show that the dimension of the centroid is bounded above by n^d/(d-1) and classify all tensors where the bound is achieved.

(joint work with JM Landsberg, V. Souza, P. Speegle)

Participants

Acknowledgement

National Institute of Informatics, Japan.