Advances in Computational Complexity and Algebraic Methods

The field of computational complexity and algebraic methods is experiencing significant developments, driven by innovative approaches to fundamental problems. Researchers are exploring new frontiers in p-adic numbers, linear recurrence sequences, and polynomial-time algorithms, leading to breakthroughs in our understanding of complex systems. Notably, recent studies have made progress in solving long-standing problems, such as the Skolem Problem, and have introduced new concepts, like spectral sparsification for Constraint Satisfaction Problems. These advances have far-reaching implications for cryptography, optimization, and computer science as a whole. Noteworthy papers include: Polynomial-time Tractable Problems over the p-adic Numbers, which solves a longstanding problem on the computational complexity of systems of linear equations over p-adic numbers. On the p-adic Skolem Problem, which presents algorithms for determining whether a given linear recurrence sequence has a p-adic zero. Rank Bounds and PIT for Σ^3 Π Σ Π^d circuits via a non-linear Edelstein-Kelly theorem, which proves a non-linear Edelstein-Kelly theorem for polynomials of constant degree and obtains constant rank bounds for depth-4 circuits. A Theory of Spectral CSP Sparsification, which introduces a notion of spectral energy for fractional assignments and defines a spectral sparsifier for Constraint Satisfaction Problems. On the Degree Automatability of Sum-of-Squares Proofs, which broadens the class of polynomial systems for which degree-d SoS proofs can be automated.

Sources

Polynomial-time Tractable Problems over the $p$-adic Numbers

On the $p$-adic Skolem Problem

Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem

Deterministic Depth-4 PIT and Normalization

A Theory of Spectral CSP Sparsification

Catalytic Computing and Register Programs Beyond Log-Depth

On the Degree Automatability of Sum-of-Squares Proofs

Built with on top of