Mathematics
Seminar
|
|
|
Rocky Mountain Algebraic Combinatorics Seminar
Tensor Isomorphism
Joshua Grochow
University of Colorado, Boulder
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)
Colorado State University
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.
PDF version
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
- Farid Aliniaeifard,
Brady Tyburski
- 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
- Vladimir D. Tonchev,
Morgan Rodgers
- 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
- John MacLaren Walsh,
Henry Adams
- 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
- Jason Cantarella,
Michal Adamaszek
- 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
- Ross McConnell,
Henry Adams
- September 11, 2015
- James B. Wilson,
Tim Penttila
- May 8, 2015
- Amanda Schaeffer Fry,
Peter Brooksbank
- April 24, 2015
- Heide Gluesing-Luerssen,
Phil DeOrsey
- 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
Fort Collins, Colorado 80523
|