# Seminar

## Rocky Mountain Algebraic Combinatorics Seminar

### Tensor Isomorphism

Joshua Grochow

Full title: Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism

We consider the problems of testing isomorphism of tensors, p-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, computational complexity, and cryptography. Despite a perhaps seeming similarity with Graph Isomorphism, the current-best algorithms for these problems (when given by bases) are still exponential - for most of them, qn2 over GF(q). Similarly, while efficient practical software exists for Graph Isomorphism, for these problems even the best current software can only handle very small instances (e.g., 10 x 10 x 10 over GF(13)). We will discuss what is known (some of it very recent) about algorithms and complexity for these problems. A small spoiler: They are all equivalent! Even isomorphism of d-tensors and isomorphism of 3-tensors. Various parts based on joint works with V. Futorny & V. V. Sergeichuk (Lin. Alg. Appl. , 2019; preprint arXiv:1810.09219), Y. Qiao (arXiv:1907.00309), and P. Brooksbank, Y. Li, J. B. Wilson, & Y. Qiao (arXiv:1905.02518).

### Enumerating Anchored Permutations with Bounded Gaps

Maria Gillespie
CSU

Suppose you start on the bottom stair of a staircase with n stairs and climb to the top stair, using up or down steps of no more than k stairs at a time, such that every stair is stepped on exactly once. In how many different ways can you climb the stairs?

We will show that there always exists a finite-depth homogeneous linear recurrence relation to enumerate such stair climbing patterns, which may be expressed as permutations with bounded differences of consecutive entires. We provide explicit recursions for k=2 and k=3, resolving a conjecture that was previously listed on OEIS A249665. We then use techniques from spectral graph theory to give asymptotic bounds for the sequences for all k.
This is joint work with Ken G. Monks and Ken M. Monks.

Weber 223
4–6 pm
Friday, Nov 15, 2019
(Refreshments in Weber 117, 3:30–4 pm)

This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.

### Previous Seminars:

Nov 1, 2019
Eilidh McKemmie, Michael Epstein
Oct 11, 2019
Martin Kassabov, Eric Moorhouse
Oct 11, 2019
Martin Kassabov, Eric Moorhouse
Sep 27, 2019
Alexander Hulpke, Tianjuan Xu
Sep 13, 2019
Laura Scull, Emily King
Sep 28, 2018
Sep 7, 2018
James Wilson, Alexander Hulpke
Apr 20, 2018
Maria Monks Gillespie, Alistair Savage
Apr 6, 2018
Susan Hermiller, Nathaniel Thiem
March 23, 2018
Henry Tucker, Richard Green
March 2, 2018
Nik Ruskuc, Joshua Grochow
February 16, 2018
Hamidreza Chitsaz, Mark Lewis
February 2, 2018
James B. Wilson, Anton Betten
November 10, 2017
Michael Kinyon, Petr Vojt\v{e}chovsk\'y
October 20, 2017
Eric Moorhouse, William DeMeo
October 6, 2017
Spencer Gerhardt, Joshua Grochow
September 22, 2017
Amanda Schaeffer Fry, Henry Kvinge
September 8, 2017
Peter Mayr, James B. Wilson
May 5, 2017
Ferdinand Ihringer, Gavin King
April 21, 2017
April 7, 2017
Jason Williford, Anton Betten
March 24, 2017
Isabella Novik, Peter Brooksbank
March 3, 2017
Jintai Ding, Curtis Bennett
February 17, 2017
Fatma Karaoglu, Eric Moorhouse
February 3, 2017
Tim Penttila, James B. Wilson
December 2, 2016
Jim Fowler, Andrew Kelley
November 11, 2016
Joseph Gersch, Joshua Maglione
October 28, 2016
October 14, 2016
JM Landsberg, James B. Wilson
September 30, 2016
Alexander Hulpke, Oscar Levin
September 16, 2016
Delaram Kahrobaei, Amit Patel
June 23, 2016
April 29, 2016
Nick Loehr, Jason Williford
April 15, 2016
Alexander Hulpke, Klaus Lux
April 1, 2016
Eamonn O'Brien, Izabella Stuhl
February 19, 2015
James Wilson, Anton Betten
December 4, 2015
Maria Monks Gillespie, Dane Flannery
November 13, 2015
Richard Green, Tim Penttila
October 23, 2015
Christina Boucher, Sylvia Hobart
October 9, 2015
Josh Maglione, Ghodratollah Aalipour
September 25, 2015
September 11, 2015
James B. Wilson, Tim Penttila
May 8, 2015
Amanda Schaeffer Fry, Peter Brooksbank
April 24, 2015
March 6, 2015
Felice Manganiello, Eric Moorhouse
February 20, 2015
Anton Dzhamay, Anton Betten
February 6, 2015
Alexander Hulpke, Morgan Rodgers
December 5, 2014
Stefaan De Winter, Gretchen Matthews
November 14, 2014
Greg Coxson, Tom Dorsey
October 31, 2014
Octavio Paez Osuna, Sylvia Hobart
October 10, 2014
Takunari Miyazaki, Eric Moorhouse
September 26, 2014
Elissa Ross, Anton Betten
September 12, 2014
Petr Vojtěchovský, Alexander Hulpke
May 9, 2014
Philip DeOrsey, Tim Penttila
April 25, 2014
William J Martin, Jason Williford
April 11, 2014
Victor Pambuccian, George Shakan
March 7, 2014
Nathan Lindzey, Jens Harlander
February 21, 2014
Ross McConnell, Anton Betten
November 22, 2013
Justin Hughes, Josh Maglione

Department of Mathematics