5 problems

An intersection of $k$ halfspaces on $\mathbb{R}^n$ is a Boolean function $f:\mathbb{R}^n\to\{\pm1\}$ that equals $1$ exactly when all of its $k$ linear threshold functions equal…

Computational hardness conjecture. Obtaining better error guarantees than the algorithm's guarantee is computationally intractable.

Let $f_t$ be the halfspace appearing in the paper, and let $\mathrm{VB}_1(f_t)$ and $I_1(f_t)$ denote the corresponding boundary quantity and first-coordinate influence. The paper…

Let $f(x)=\mathbbm{1}\left(\sum_i a_i x_i>t\right)$ be a halfspace, with the weight vector normalized by $\sum_i a_i^2=1$. Let $I_k(f)$ denote the influence of coordinate $k$, and…

Kalai–Keller–Mossel conjecture. There is a universal constant $c>0$ such that every halfspace satisfies