Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 depthd AC0 circuit needs a size Θ(2n1d1). But PARITY is in NC1 and PARITY is also the negation of ...
gradstudent's user avatar
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 2n gates. For me, it should be ...
user avatar
2 votes
1 answer
80 views

MOD2017(x1,,xk) computable by bounded depth polynomial size circuit in basis {¬,MAJ}?

Now, I have the following conjecture. MOD2017(x1,,xk) is computable by a bounded depth polynomial size circuit in the basis {¬,MAJ}. However, I am at a loss at ...
Alex's user avatar
  • 121
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 ...
user53733's user avatar
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 ...
gradstudent's user avatar
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 ...
user avatar