Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Circuits complexity:
TR99-044 | 30th September 1999
Farid Ablayev

On Complexity of Regular $(1,+k)$-Branching Programs

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

TR24-092 | 16th May 2024
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

Hilbert Functions and Low-Degree Randomness Extractors

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

ISSN 1433-8092 | Imprint