Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CIRCUITS COMPLEXITY:
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