Submodular separation conjecture for low-degree monomial families

About 7 years old · traced to

Let 0⩽r⩽d0\leqslant r\leqslant d be integers and let n=(d⩽r)n=\binom{d}{\leqslant r}. Define

ϕ:{0,1}d→{0,1}n,ϕ(x)=(∏i∈Sxi)S⊂[d]:∣S∣⩽r,\phi:\{0,1\}^d\to\{0,1\}^n, \qquad \phi(x)=\left(\prod_{i\in S}x_i\right)_{S\subset[d]:|S|\leqslant r},

and let Fr,d=ϕ({0,1}d){\mathcal F}_{r,d}=\phi(\{0,1\}^d). A function f:{0,1}n→Zf:\{0,1\}^n\to\mathbb Z is submodular if f(x)+f(y)⩾f(x∨y)+f(x∧y)f(x)+f(y)\geqslant f(x\vee y)+f(x\wedge y) for all x,yx,y.

Submodular separation conjecture. For every such r,dr,d, there exists a submodular function ff such that f(x)f(x) is computable in poly(n)\mathrm{poly}(n) time, f(x)⩽−1f(x)\leqslant-1 for every x∈Fr,dx\in\mathcal F_{r,d}, and f(x)⩾0f(x)\geqslant0 for every x∉Fr,dx\notin\mathcal F_{r,d}. 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.

References

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.