3 papers
cs.DS2025
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization…
cs.DS2025
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Aditya Anand, Euiwoong Lee, Jason Li +1
Given a directed graph with vertices and edges, a parameter and two disjoint subsets , we show that the number of all-subsets important separato…
cs.DS2025
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
Aditya Anand, Euiwoong Lee, Davide Mazzali +1
This paper studies complete -Constraint Satisfaction Problems (CSPs), where an -variable instance has exactly one nontrivial constraint for each subset of variables, i.e.…