10 votes
Accepted

$AC^0$[subexp] vs. NC

No, $\mathrm{AC}^0[2^{n^\delta}]$ is not included in NC; it is not even included in $\mathrm{SIZE}[2^{n^\epsilon}]$ for $\epsilon<\delta$. Indeed, any Boolean function on $n^\delta$ inputs, padded ...
Emil Jeřábek's user avatar
10 votes
Accepted

Trade-off for Barrington's theorem

Perhaps what you're looking for is theorem 2 in Cleve, R. Towards optimal simulations of formulas by bounded-width programs. I don't think the precise statement that you're asking about is known (note ...
Ryan Williams's user avatar
7 votes
Accepted

What circuit depth is enough to compute a log-space complete problem?

It seems that nobody has added to the discussion of this question since February. I'm quite sure that no better depth upper bound is known for L than $\log^2 n$, in the bounded fan-in circuit model, ...
Eric Allender's user avatar
4 votes

Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that $$ \Pr_g[\Pr[f=g] ...
Yuval Filmus's user avatar
  • 14.4k
3 votes
Accepted

In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

You do not cite the part of the survey that is actually relevant for getting the $s/3$ lower bound: Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree ...
holf's user avatar
  • 2,174
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,255
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
2 votes
Accepted

Is unbounded quantum fanout operation experimentally feasible?

There are two way to see your question : Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ? Is there a realistic quantum architecture which is effectively equivalent to ...
Frédéric Grosshans's user avatar
1 vote
Accepted

doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

See that $w\in \mathcal{F}_m$ so $\deg(w)\geq m$ but $\deg(w_L),\deg(w_R)<m$. So if $\deg(w_L)=\deg(w_R)=m-1$ then $\deg(w)$ becomes $2m-2$. If $m$ is large enough then $2m-2 >m$. Hence we can ...
Soham Chatterjee's user avatar

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