research
∙
06/28/2023
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Many isomorphism problems for tensors, groups, algebras, and polynomials...
share
research
∙
06/05/2023
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
We study the complexity of isomorphism problems for d-way arrays, or ten...
research
∙
06/03/2023
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system
The Ideal Proof System (IPS) of Grochow Pitassi (FOCS 2014, J. ACM, ...
research
∙
05/30/2023
On the algebraic proof complexity of Tensor Isomorphism
The Tensor Isomorphism problem (TI) has recently emerged as having conne...
research
∙
01/17/2023
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality
There is no single canonical polynomial-time version of the Axiom of Cho...
research
∙
09/27/2022
On the Descriptive Complexity of Groups without Abelian Normal Subgroups
In this paper, we explore the descriptive complexity theory of finite gr...
research
∙
04/26/2022
Experience Report: Standards-Based Grading at Scale in Algorithms
We report our experiences implementing standards-based grading at scale ...
research
∙
04/08/2022
Matrix multiplication via matrix groups
In 2003, Cohn and Umans proposed a group-theoretic approach to bounding ...
research
∙
12/21/2021
Weisfeiler-Leman for Group Isomorphism: Action Compatibility
In this paper, we show that the constant-dimensional Weisfeiler-Leman al...
research
∙
12/22/2020
An Improved Algorithm for Coarse-Graining Cellular Automata
In studying the predictability of emergent phenomena in complex systems,...
research
∙
12/02/2020
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
We study the problems of testing isomorphism of polynomials, algebras, a...
research
∙
06/30/2019
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
In this paper we consider the problems of testing isomorphism of tensors...
research
∙
05/06/2019
Incorporating Weisfeiler-Leman into algorithms for group isomorphism
In this paper we combine many of the standard and more recent algebraic ...
research
∙
03/19/2018
Computational topology and the Unique Games Conjecture
Covering spaces of graphs have long been useful for studying expanders (...
research
∙
12/06/2017
Which groups are amenable to proving exponent two for matrix multiplication?
The Cohn-Umans group-theoretic approach to matrix multiplication suggest...
research
∙
10/26/2017
Minimum Circuit Size, Graph Isomorphism, and Related Problems
We study the computational power of deciding whether a given truth-table...
research
∙
08/30/2017
Designing Strassen's algorithm
In 1969, Strassen shocked the world by showing that two n x n matrices c...
research
∙
06/29/2017
Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines
In the past three decades, many theoretical measures of complexity have ...
research
∙
09/25/2014