The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

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 ...
• 27.5k
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 ...
• 18.2k
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, ...
• 2,261

### 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] ...
• 14.5k
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
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 ...
• 2,174
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}}$....
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 ...