Advances in Computational Complexity and Constraint Programming

The field of computational complexity and constraint programming is moving towards more efficient and expressive methods for solving complex problems. Recent developments have focused on improving the scalability and performance of existing algorithms, as well as exploring new approaches to tackle challenging problems. Notably, research has been conducted on structure-aware encodings, symmetry breaking, and monitoring techniques, which have led to significant advancements in the field. Some noteworthy papers have made innovative contributions to the field. For example, the paper on Structure-Aware Encodings of Argumentation Properties for Clique-width presents novel reductions from argumentation problems to (Q)SAT, resulting in directed decomposition-guided reductions. The paper on Faster Symmetry Breaking Constraints for Abstract Structures demonstrates a new incomplete method of breaking symmetries of abstract structures, outperforming previous methods. Overall, the field is witnessing a shift towards more sophisticated and powerful techniques, enabling the solution of complex problems that were previously intractable.

Sources

Structure-Aware Encodings of Argumentation Properties for Clique-width

Faster Symmetry Breaking Constraints for Abstract Structures

Automata-less Monitoring via Trace-Checking (Extended Version)

Arity hierarchies for quantifiers closed under partial polymorphisms

Decomposition and Preprocessing of Ternary Constraint Networks

Expressive Temporal Specifications for Reward Monitoring

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

Fast Verification of Strong Database Isolation (Extended Version)

Redundancy rules for MaxSAT

The Solver's Paradox in Formal Problem Spaces

Towards Practical Zero-Knowledge Proof for PSPACE

Filling the Gaps of Polarity: Implementing Dependent Data and Codata Types with Implicit Arguments

An Aligned Constraint Programming Model For Serial Batch Scheduling With Minimum Batch Size

Faster Certified Symmetry Breaking Using Orders With Auxiliary Variables

Built with on top of