Farid Ablayev

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an

ordinary branching program with the following restrictions: (i)

along every consistent path at most $k$ variables are tested more

than once, (ii) for each node $v$ on all paths from the source to

$v$ the same set $X(v)\subseteq X$ of variables is ...
more >>>

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>