Advances in Discrete Optimization and Computational Algebra

The field of discrete optimization is moving towards a deeper understanding of the structural parameters that govern the complexity of problems. Recent research has highlighted the importance of rank as a key parameter in discrete optimization, analogous to treewidth in algorithmic graph theory. This has led to the development of new exact algorithms for problems such as quadratic unconstrained binary optimization (QUBO) and its cardinality-constrained extension. Additionally, there is a growing interest in the study of lexicographic cost functions and their impact on the complexity of optimization problems. In computational algebra, researchers are exploring the connections between optimization problems and Hilbert's Nullstellensatz, a fundamental problem in algebraic geometry. This has led to a better understanding of the complexity of problems such as the Affine Polynomial Projection Problem and the Sparse Shift Problem. Noteworthy papers in this area include: Affine Predicate Geometry: A Courcelle-Type Metatheorem for Rank-Bounded Pseudo-Boolean Optimization, which establishes rank as a structural parameter for discrete optimization. A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem, which proposes a quantum-inspired algorithm for solving QUBO problems. Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz, which shows that many important problems from optimization and algebra are complete or hard for the complexity class associated with Hilbert's Nullstellensatz.

Sources

Affine Predicate Geometry: A Courcelle-Type Metatheorem for Rank-Bounded Pseudo-Boolean Optimization

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz

A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem

Computing excited states with isometric tensor networks in two-dimensions

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Built with on top of