The Maximum Independent Set (MIS) problem is NP-complete and remains so for every minor-closed graph class that includes all planar graphs (Garey and Johnson [SIAM J. Appl. Math.'77]). On the other hand, due to the Grid Theorem of Robertson and Seymour [JCTB'95], every minor-closed graph class that excludes a planar graph has bounded treewidth, and MIS can be solved in polynomial time on such...
We introduce a linear-time algorithm for computing the Frobenius normal form (FNF) of symmetric Toeplitz matrices by utilizing their inherent structural properties through a graph-theoretic approach. Previous results of the authors established that the FNF of a symmetric Toeplitz matrix is explicitly represented as a direct sum of symmetric irreducible Toeplitz matrices, each corresponding to...
The Gowers uniformity norm has played a significant role in additive combinatorics as a measure of randomness associated with solution sets of certain linear configurations. In this talk, I introduce the notion of Gowers uniformity norms and demonstrate how they capture additive structures in a given set of integers. Gowers norms capture additive structures both through k-term arithmetic...
