Nikolay V. Proskurin

collaborators

2 papers

cs.CC2022

Polynomial Threshold Functions for Decision Lists

Vladimir Podolskii, Nikolay V. Proskurin

For $S \subseteq {0, 1}^{n}$ a Boolean function $f : S \to {- 1, 1}$ is a polynomial threshold function (PTF) of degree $d$ and weight $W$ if there is a polynomial $p$ with int…

cs.CC2021

On Separation between the Degree of a Boolean Function and the Block Sensitivity

Nikolay V. Proskurin

In this paper we study the separation between two complexity measures: the degree of a Boolean function as a polynomial over the reals and its block sensitivity. We show that separ…