All Questions
6 questions
2
votes
0
answers
40
views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
- 493
2
votes
1
answer
458
views
Why each function may be computed with circuit with 2^n gates?
Why each function may be computed with circuit with 2^n gates ?
I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be ...
user54001
1
vote
0
answers
102
views
How many bits we can negate using two/three NOT gates?
How many bits we can negate using two/three NOT gates ?
I am newbie at this subject so I ask for help. It is about circuits.
Edit
After reading link given in comments by @D.W I think that I can ...
user54001
2
votes
1
answer
80
views
$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?
Now, I have the following conjecture.
$\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$.
However, I am at a loss at ...
- 121
2
votes
1
answer
71
views
What are the gap functions in the $AC$ hierarchy?
Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of ...
- 493
2
votes
1
answer
341
views
What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates
In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
- 21