Assume that $w_i \in [-1, 1]$ are independent and uniformly distributed random variables for $i \in \{1,2,\ldots, n\}$, and let $w = (w_1, \ldots, w_n)^\text T$. Let $x^\star = \operatorname{argmin} \{|w^{\text{T}} x| \mid x \in \{0,1\}^n, x \neq 0\}$.
I would like to have a bound on the probability that $|w^{\text T} x^\star| \in (0,\varepsilon]$ for small $\varepsilon > 0$. In particular, I am interested in a lower bound for this probability.
I find it intuitively clear that this event should have a probability that depends exponentially on $n$, as most $w^\text T x$ have small absolute value. However, I did not succeed so far in making this rigorous.
I just found an answer. The problem has been solved by George Lueker in 1998 (Random Structures and Algorithms 12:51-62).