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 >>>

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 >>>