Advances in Matrix Theory and Computational Complexity

The field of matrix theory and computational complexity is experiencing significant developments, with a focus on advancing our understanding of matrix properties and improving the efficiency of computational algorithms. Researchers are exploring new methods for characterizing nondefinite matrices, introducing zeros to their diagonals, and developing more efficient algorithms for solving linear systems of equations. Additionally, there is a growing interest in the study of reconfiguration problems, which involve transforming one solution into another while satisfying certain constraints. The development of new computing frameworks, such as wave computing, is also showing promise in solving NP-hard problems. Noteworthy papers in this area include: Zeroing Diagonals, Conjugate Hollowization, and Characterizing Nondefinite Operators, which proves a conjecture on the existence of orthogonal matrices that can transform traceless matrices into hollow or almost hollow matrices. Near instantaneous O(1) Analog Solver Circuit for Linear Symmetric Positive-Definite Systems, which presents a novel analog solver circuit for accelerating the solution of linear systems of equations. NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing, which resolves a long-standing question on the complexity of computing deterministic communication complexity.

Sources

Zeroing Diagonals, Conjugate Hollowization, and Characterizing Nondefinite Operators

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

Exact Matching in Matrix Multiplication Time

Square packing with $O(x^{0.6})$ wasted area

Near instantaneous O(1) Analog Solver Circuit for Linear Symmetric Positive-Definite Systems

Wave Computing based on Dynamical Networks: Applications in Optimization Problems

Aircraft routing: periodicity and complexity

NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing

Built with on top of