Submodular separation conjecture for low-degree monomial families

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

ϕ:{0,1}d{0,1}n,ϕ(x)=(iSxi)S[d]:Sr,\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}nZf:\{0,1\}^n\to\mathbb Z is submodular if f(x)+f(y)f(xy)+f(xy)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 xFr,dx\in\mathcal F_{r,d}, and f(x)0f(x)\geqslant0 for every xFr,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.

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

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.