## Videos (newest first) (by topic instead)

**Polynomial-time Axioms of Choice and polynomial-time
cardinality**

U. Connecticut Logic Colloquium, Jan 2023

Based on the paper Polynomial-Time Axioms of Choice and
Polynomial-Time Cardinality,

Abstract

Many versions of the Axiom of Choice (AC), though equivalent in ZF set theory, are inequivalent from the computational point of view. When we consider polynomial-time analogues of AC, many of these different versions can be shown to be equivalent to other more standard questions about the relationship between complexity classes. We will use some of these formulations of AC to motivate several complexity questions that might otherwise seem a bit bespoke and unrelated from one another.

Next, as many versions of AC are about cardinals, in the second half of the talk we introduce a polynomial-time version of cardinality, in the spirit of polynomial-time model theory. As this is a new theory, we will discuss some of the foundational properties of polynomial-time cardinality, some of which may be surprising when contrasted with their set-theoretic counterparts. The talk will contain many open questions, and the paper contains even more! Based on arXiv:2301.07123 [cs.CC].

**Matrix multiplication via matrix groups**

*14th Innovations in Theoretical Computer Science (ITCS)*, Jan 2023

Based on our paper Matrix multiplication via matrix
groups,

Joint with

**Polynomial identity testing & the ideal proof
system**

DIMACS Workshop on Metacomplexity, Barriers, and
Derandomization, Apr 2022

Based on work in progress.

**Algebraic proof complexity: a gentle
introduction**
(expository)

FOCS '21 (in '22) Workshop: Reflections
on
Propositional Proofs in Algorithms & Complexity, Feb 2022

Slides

Abstract

**Part I: Motivation, history, and introduction to algebraic proof complexity (Toniann Pitassi)**

This first talk will give a quick primer on proof complexity, especially as it relates to algebraic proof systems. It will cover some of the history and motivation that led to the study of algebraic proof systems, as well as introduce some well-studied algebraic proof systems and the relations between them.

**Part II: Circuit complexity, ideals and proof systems: connections and recent results (Joshua A.
Grochow)**

The second talk will cover connections between the Ideal Proof System (IPS), circuit complexity, and more generally complexity in ideals. In particular, it will cover the relation between IPS and VP vs VNP, as well as the recent result of Andrews & Forbes that extends the constant-depth algebraic circuit lower bound of Limaye-Srinivasan-Tavenas to a lower bound on refuting certain polynomial equations in IPS. The talk will highlight the connection between algebraic circuit complexity, algebraic proof complexity, and even Boolean circuit complexity to the complexity not of individual (families of) polynomials, but of arbitrary (families of) polynomials inside an ideal or coset of an ideal.

**On p-Group Isomorphism: search-to-decision, counting-to-decision,
and nilpotency class reductions via tensors**

*Conference on Computational Complexity (CCC 2021)*, Jul 2021

Based on our paper On p-Group Isomorphism:
search-to-decision, counting-to-decision, and nilpotency class reductions via tensors,

Joint with

**Codes and Expansions in Algorithms for Matrix Multiplication**
(expository)

Codes and Expansions Seminar (CodEx), Feb 2021

Based partly on our paper Designing Strassen's algorithm,

Joint with .

Slides

Abstract

We overview some relationships between codes (and various code-like objects) and constructing algorithms for multiplying matrices, ranging from concrete results to intriguing observations of things that look similar if you squint just right.

This includes a connection between codes and bilinear complexity from Lempel & Winograd '77, symmetric algorithms for matrix multiplication (studied by many authors), and a construction of Strassen's 1969 matrix multiplication algorithm from a unitary 2-design (G. & Moore, arXiv:1708.09398). And more connections we won't have time for, but promise at least one slide about.

**Designing Strassen's algorithm for matrix
multiplication**

LA Combinatorics & Complexity
Seminar, Nov 2020

Based on our paper Designing Strassen's algorithm,

Joint with .

**On the complexity of isomorphism problems for tensors, groups, and
polynomials I: Tensor Isomorphism-completeness**

*12th Innovations in Theoretical Computer Science (ITCS)*, Jan 2021

Based on our paper On the complexity of isomorphism
problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness,

Joint with

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

Banff BIRS 2019 Workshop on Algebraic
Techniques in Computational Complexity, 12 Jul 2019

Based on the papers:

, Wildness for tensors

, Incorporating Weisfeiler-Leman into algorithms for group
isomorphism

,
On the Complexity of Isomorphism Problems for Tensors,
Groups, and Polynomials I: Tensor Isomorphism-Completeness

,
On p-Group Isomorphism: search-to-decision,
counting-to-decision, and nilpotency class reductions via tensors

Abstract

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, 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, even q^{n2} 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)). This raises the question of finding new algorithmic techniques for these problems,
and/or of
proving hardness results.

We show that all of these problems are equivalent under polynomial-time reductions, giving rise to a class of
problems we call Tensor Isomorphism-complete (TI-complete). We further show that testing isomorphism of
d-tensors
for any fixed d (at least 3) is equivalent to testing isomorphism of 3-tensors. Using the same techniques, we
show
two first-of-their-kind results for Group Isomorphism (GpI): (a) a reduction from isomorphism of p-groups of
exponent p and class c < p, to isomorphism of p-groups of exponent p and class 2, and (b) a
search-to-decision
reduction for the latter class of groups in time |G|^{O(log log|G|)}. We note that while p-groups of
class 2 have
long been believed to be the hardest cases of GpI, as far as we are aware this is the first reduction from any
larger class to this class of groups. Finally, we discuss a way to apply combinatorial methods from Graph
Isomorphism (namely, Weisfeiler-Leman) to Group and Tensor Isomorphism.

Based on joint works with Vyacheslav V. Futorny and Vladimir V. Sergeichuk (Lin. Alg. Appl., 2019; arXiv:1810.09219), with Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson (arXiv:1905.02518), and with Youming Qiao (arXiv:1907.00309).

**Tensors & Complexity I** (expository)

Tensors: Algebra-Computation-Applications (TACA),
Jun 2019

Expository talk, parts of which mention key results from the following papers:

, Wildness for tensors

,
On the Complexity of Isomorphism Problems for Tensors,
Groups, and Polynomials I: Tensor Isomorphism-Completeness

Abstract

The first lecture will be about what computational complexity can tell us about tensors. We will review notions of reductions between problems, how we can use these notions of reduction to learn about computational difficulty. We will then cover what is known about the complexity of a variety of problems on tensors, including a first look at some very recent results (only going up on the arXiv this week!).

**Tensors & Complexity II** (expository)

Tensors: Algebra-Computation-Applications (TACA),
Jun 2019

Abstract

This second lecture will be about what tensors can tell us about computational complexity. We will see several ways - both direct and indirect - in which problems on tensors lie at the heart of lower bounds in complexity theory.

**Introduction to
Computation Theory**

Complexity Explorer tutorial, timeless

**Algorithms and Complex Systems**

Part of my Complexity Explorer tutorial, March 2019: Introduction to
Computation Theory

**Sorting and
the information-theoretic lower bound: a structural analysis**

Santa Fe Institute REU final presentation, 2015

Extended into her undergraduate thesis The Structure of Partial
Orders in the Face of Lower Bounds

**Total
information flow in stochastic networks**

Santa Fe Institute REU final presentation, 2015

Eventually turned into Comparing Information-Theoretic Measures
of Complexity in Boltzmann Machines,

Joint with myself and .

**5-minute Lightning Research Talk**

Santa Fe Institute Board Meeting, 2015

**Graph automorphism & circuit size**

Simons Institute Workshop: Connections
Between Algorithm Design and Complexity Theory, Oct 2015

Based on , Graph Isomorphism and circuit size.

Eventually became , Minimum Circuit Size, Graph Isomorphism, and Related Problems.

**An introduction to Geometric Complexity
Theory** (expository)

ICERM Workshop: Mathematical Aspects of P
versus NP and its Variants, Aug 2011.