Tag Info

Accepted

Is $f(X)f^d(X) = 0$ for a Boolean function $f$?

$$f^d(X)f(X) \lor f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1} = f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1}$$ The equality above comes from the general equality below. It has nothing to do with the context. ...
• 38.5k
Accepted

Can Boolean circuits of polylog depth represent all Boolean functions?

A $k$-ary circuit of depth $d$ has size at most $k^d$, hence polylog-depth circuits of fan-in $2$ have quasipolynomial size. Thus, the vast majority of Boolean functions cannot be computed by such ...
• 955

Shannon's result that some Boolean functions require exponential circuits

The best known lower bounds for explicit functions are $\Omega(n)$. The only superpolynomial lower bounds are in restricted models of circuits, such as monotone circuits and bounded-depth circuits. NP-...
• 274k
Accepted

How many different boolean functions exist up to permutation of its $n$ variables

You are looking for A003180. The related sequence A003181 counts functions depending on all variables. Often one allows further operations: negation of inputs, and negation of the output. The ...
• 274k

sum of Boolean characters larger degree

This is related to higher-order Fourier analysis. A classical result of Dickson ("Dickson's lemma") states that up to a change of basis, any quadratic form over $\mathit{GF}(2)$ is of the ...
• 274k

Boolean function represented as a column vector: easy way to see if it has full degree?

Every function $f\colon \{0,1\}^n \to \{0,1\}$, whose input we style $x_1,\ldots,x_n$, has a unique expansion as a multilinear polynomial in the variables $y_i = (-1)^{x_i} = 1-2x_i$. It also has a ...
• 274k

How to construct a carry-lookahead adder of the optimal $O(n)$ size

Actually, upon working on this problem for a bit more time, I discovered one method to build a size $O(n)$ and depth $O(\log n)$ CLA circuit. The key ingredient is the work-efficient parallel ...
• 31
1 vote
Accepted

Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?

The problem is $\Sigma_2^P$-complete, which means that it is hard -- it is even "harder" than NP-complete problems. In particular, there is unlikely to be any polynomial-time algorithm. ...
• 154k
1 vote

influence of neighourhood points

No. Suppose $h$ is the parity function and $f(x)=-h(x)$. Then $\sum_x h(x) f(x) = -2^n \le 0.5$, but $\sum_i h(x) f(x) h(x^i) f(x^i) = n$ (which is as large as it can get) for all $x$.
• 154k
1 vote
Accepted

Is there a notation for boolean algebra complexity?

This is called Circuit Complexity: https://en.wikipedia.org/wiki/Circuit_complexity The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an ...
• 2,469
1 vote

Time-complexity of evaluating a CNF formula

No. You can't even do it in $O(n^2)$ time, if $n$ is the number of variables. The formula might be much longer than $\Theta(n^2)$ (it might have many more clauses than that), and obviously any ...
• 154k

Only top scored, non community-wiki answers of a minimum length are eligible