# Questions tagged [boolean-functions]

Questions about Boolean functions and their analysis

21 questions
Filter by
Sorted by
Tagged with
1k views

### Cohomological approach to boolean complexity

A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
• 2,786
1k views

### Monotone arithmetic circuits

The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
• 21.3k
1k views

• 31.7k
405 views

### Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
• 717
947 views

### Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
• 523
1k views

### Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier. For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine ...
• 10.4k
339 views

### Given a subset of the hypercube and a copy translated by s, find s

Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
• 173
347 views

### Boolean functions with exponential size OBDD representation in all orders except one order?

Are there boolean functions with exponential size OBDD representation in all orders except one order? ...exponential size in all orders except very few orders? The exceptional orders should be ...
• 343
630 views

### Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the most ...
• 201
306 views

### Reverse Skolemization?

I'm wondering if there are any references on "reverse skolemization", that is, converting a formula with functions into one purely consisting of quantifiers by eliminating function applications. I'm ...
• 2,724
90 views

### Representing boolean function by a rational function

What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?
• 12.5k
1 vote
Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be a boolean function. Let $d$ be the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents \$P(x_1,...