# Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

201 questions
Filter by
Sorted by
Tagged with
87 views

• 203
410 views

• 1,095
119 views

### Is Circuit Minimization $P$-hard under logspace reductions?

By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string $x$ and a number $k$. Question: Does there exist a Boolean Circuit $C$...
• 4,900
187 views

### Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
• 51
130 views

### Average-case analogue of Small-bias Spaces

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias | \mathbb{E}_{x \in S} [ (-...
• 383
116 views

• 778
67 views

### $p$-biased two-function hypercontractivity

The Hypercontractivity theorem (or Bonami Beckner inequality) is a very useful tool. Unfortunately, it isn't easy to carry over to other spaces than the uniform boolean cube. In Ryan O'Donnel's ...
• 778
221 views

• 133
143 views

### Has what I am calling "helpfulness" here been studied?

We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
• 1,552
1 vote