Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
16 votes
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 ...
Dylan McKay's user avatar
3 votes
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 ...
Bart Jansen's user avatar
  • 5,275
3 votes

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 ...
Mikhail Rudoy's user avatar
2 votes
Accepted

$\mathrm{AC}^0$ upper bound for Hamming weight

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-...
Emil Jeřábek's user avatar
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 $$...
Ryan Williams's user avatar
2 votes

About the sign-rank of the Minsky-Pappert function

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}}$....
Robin Kothari's user avatar

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