Advances in Computational Complexity and Logic

The field of computational complexity and logic is moving towards a deeper understanding of the relationships between complexity classes and the development of new techniques for analyzing and solving problems. Recent research has focused on strengthening lower bounds for complexity classes such as NEXP and EXP, as well as exploring the connections between complexity theory and logic. Notably, there have been significant advances in the study of fixed-point logic with counting and its relationship to approximation problems. Additionally, new algorithms and data structures have been developed for solving problems in temporal graphs and other areas. These developments have the potential to impact a wide range of applications, from optimization and verification to machine learning and artificial intelligence. Noteworthy papers include: The paper on Undefinability of Approximation of 2-to-2 Games, which extends previous work on fixed-point logic with counting to show the undefinability of certain approximation problems. The paper on Polynomial-Time PIT from (Almost) Necessary Assumptions, which constructs polynomial-time algorithms for certain problems in algebraic complexity theory. The paper on New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications, which develops new algorithms and data structures for solving problems in temporal graphs.

Sources

On the consistency of stronger lower bounds for NEXP

Undefinability of Approximation of 2-to-2 Games

A framework for computing upper bounds in passive learning settings

Meta-Mathematics of Computational Complexity Theory

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems

Infinite precedence graphs for consistency verification in P-time event graphs

Polynomial-Time PIT from (Almost) Necessary Assumptions

Matching and Edge Cover in Temporal Graphs

Built with on top of