Submodular separation conjecture for low-degree monomial families
Submodular separation conjecture for low-degree monomial families
Let be integers and let . Define
and let . A function is submodular if for all .
Submodular separation conjecture. For every such , there exists a submodular function such that is computable in time, for every , and for every . If true, this would yield a hardness result for submodular minimization with modular constraints, complementing the known prime-power algorithms; the source does not resolve the conjecture.
Sources & referencesView supporting material
Primary source
Joshua Brakensiek, Sivakanth Gopi and Venkatesan Guruswami, “CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations”, arXiv:1902.04740 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.