Questions tagged [bounded-degree]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
186 views

Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
2
votes
0answers
120 views

Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
1
vote
0answers
51 views

relations between the degrees of a boolean function and its absolute function

Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
0
votes
0answers
56 views

Which research fields deal with this variant definition of Boolean circuit depth?

Disclaimer: I admit that the question is not very clear. I think it cannot be helped because the question is very open-ended. First of all, I present the interested type of circuits. We only consider ...