Extensibility of Association Schemes and GRH-Based Deterministic Polynomial Factoring

Abstract

The subject of the present work is the application of the theory of combinatorial schemes to problems in computational algebra. The principal notions of combinatorial schemes which are studied in this work are association schemes (Bannai & Ito (1984), Zieschang (1996, 2005)), m-schemes (Ivanyos, Karpinski & Saxena (2009), Arora et al. (2012)), and presuperschemes (Smith (1994, 2007), Wojdylo (1998, 2001)). The main computational problems considered in this work are polynomial factoring over finite fields, the Schurity problem of association schemes (and its relaxation in the notion of extensibility), and matrix multiplication. We show that each of the latter problems admits a deep connection to the theory of combinatorial schemes, and describe natural algebraic-combinatorial frameworks which capture the essence of their algebraic complexity. As a logical application, we delineate how structural results for combinatorial schemes can translate to fundamental improvements in the realm of computational algebra.