# Tag Info

Accepted

### Small circuits for circuit evaluation problem

I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear ...
• 548
Accepted

### OR-weft Hierarchy

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this ...
• 5,275

### Deciding whether an NC${}^0_3$ circuit computes a permutation or not

This problem with $k=3$ is coNP-hard (and therefore coNP-complete). To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a ...
• 2,768
Accepted

Yes, the bound is essentially tight. The following is a straightforward construction of depth-$d$ Majority circuits of size $$2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}\le2^{n^{1/(d-1)}\log n}=n^{n^{1/(d-... • 17.6k 2 votes ### Some questions about the depth hierarchy for threshold circuits In the same paper that shows the n^{1.5} lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least$$...
• 27.5k
There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$....