Exponential mixed-integer lower bound for general binary oracles

Let nn be the number of integer variables, let dd be the continuous dimension, and let MM, RR, ρ\rho, and ε\varepsilon be the problem parameters. A first-order chart G\mathcal{G} determines a general binary oracle. Mixed-integer binary lower-bound conjecture. There exists a first-order chart G\mathcal{G} such that the general binary oracle based on G\mathcal{G} has information complexity

Ω(2n(1+d2log(MRρε))).\Omega\left(2^n \Big(1+d^2\log\left(\frac{MR}{\rho\varepsilon}\right)\Big)\right).

The conjecture transfers the proposed quadratic continuous-case binary-oracle lower bound to mixed-integer convex optimization; the cited continuous-case results motivate it, but it remains open.

Sources & referencesView supporting material

Primary source

Amitabh Basu, Hongyi Jiang, Phillip Kerger and Marco Molinaro, “Information Complexity of Mixed-integer Convex Optimization”, arXiv:2308.11153 (2023).

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.