Advances in Computational Complexity and Optimization

The field of computational complexity and optimization is rapidly evolving, with recent developments focusing on improving the efficiency and scalability of algorithms for solving complex problems. A key direction is the study of total search problems, which has led to a deeper understanding of the relationships between different complexity classes. Notably, research has shown that certain problems are inherently harder to solve than others, and that some algorithms are optimal in terms of their time complexity. Another area of interest is the application of semiring algebras to dynamic programming, which has enabled the solution of extended problems without increasing computational complexity. Furthermore, advances in sparsification techniques have improved the efficiency of solving stochastic packing problems, and new perspectives on local search algorithms have been proposed. The development of hybrid algorithms, such as the Las Vegas algorithm with state pruning, has also shown promise in solving classic problems like the N-Queens problem. Noteworthy papers include the study on Total Search Problems in ZPP, which separates TFZPP from major TFNP subclasses, and the work on Multiquadratic Sum-of-Squares Lower Bounds, which implies a separation between VNC^1 and VNP. Additionally, the paper on Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems presents a polyhedral sparsification framework that achieves efficient (1 - epsilon)-approximate sparsifiers.

Sources

Expected Cost Analysis of Online Facility Assignment on Regular Polygons

Total Search Problems in $\mathsf{ZPP}$

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing

The Support of Bin Packing is Exponential

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$

On the Complexity of the Ordered Covering Problem in Distance Geometry

Complexity of Local Search for CSPs Parameterized by Constraint Difference

New Perspectives on Semiring Applications to Dynamic Programming

Solving N-Queen Problem using Las Vegas Algorithm with State Pruning

Built with on top of