# How powerful is $ACC^0$ circuit class in average case?

We know that $NEXP$ is not in $ACC^0$ .

Does the result that $NEXP$ is not in $ACC^0$ also hold in average case?

That is given a boolean function in $NEXP$ is it known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible computable in $ACC^0$?

Tying up with communication complexity I think what I seek could be the following. Since $NEXP$ is not in $ACC^0$ is known could it be that any $NEXP$ complete function has superpolylogarithmic communication complexity in NOF model with superpolylogarithmic number of players?

Then the query is could the randomized complexity still be just logarithmic. Is this possible?

Generally speaking what is the smallest class $\mathcal C$ that is known such that given a boolean function in $\mathcal C$ it is known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible inputs computable in $ACC^0$?

• Your "tying up" comment gets things backwards. NOF lower bounds imply ACC0 lower bounds, but I don't think the other direction is necessarily true. Also for your question not to be trivial, you want the probability of error to be strictly less than 1/2. – Sasho Nikolov Jan 1 '17 at 9:10
• @SashoNikolov I initially had much less than $1/2$. I will change it. – 1.. Jan 1 '17 at 9:54
• @SashoNikolov sorry I thought logarithmic communication complexity also implies problem is in ACC^0? Is it not true? – 1.. Jan 1 '17 at 9:57
• Due to widespread applicability of telescope protocols like the one by Grolmusz for GIP, even a superlogarithmic number of players has only yielded trivial lower bounds for explicit functions (let alone a superpolylogarithmic number of players). In one of your questions you are therefore asking if NEXP-complete functions are immune to telescope protocols, and more. – András Salamon Jan 1 '17 at 11:53
• @AndrásSalamon I think they are immune to this variety of protocols. – 1.. Jan 1 '17 at 12:17

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can compute $f_n$ on more than $1-1/p(n)$ inputs of length $n$?

As far as I know, this is open. But here is a possible path to doing it. We know that every $NEXP$-complete function $f$ does not have ACC0 circuits of polynomial size. Perhaps an arithmetization of some $f$ (representing $f$ naturally as a family of multilinear polynomials) over a large field of finite characteristic (e.g. characteristic two) would work. (Arithmetizations can typically give you average-case hardness "for free" ... but one would have to carry out the finite field arithmetic in ACC0, presumably.) Cite me if you figure it out. ;)

• @RyanWillians actually I think that would be little strong than what I ask. I just ask if we can show no $ACC0$ circuit of $p(n)$ size can compute $f_n$ on more than $1/p(n)$ inputs of length $n$ (so $<1/2$ fraction and I think what you say is $>1/2$ fraction - I understand if circuit is generic and works on random such fraction we can get to $>1/2$ by repeating - but can we even get $1/p(n)$ in first place - may be helpful where repetitions are not allowed or not possible?). Also do natural proof or other barriers affect such situations (where repetitions are impossible or quite non-obvious). – 1.. Jan 3 '17 at 4:32
• Also I think 'carry out the finite field arithmetic in ACC0' is likely a major open problem and may be impossible. – 1.. Jan 3 '17 at 4:37
• Regarding "no ACC0 circuit of p(n) size can compute $f_n$ on more than $1/p(n)$ inputs of length $n$" As the other answer to this question says, some ACC0 circuit of O(1) size will always compute $f_n$ on at least a $1/2$ fraction of inputs of length $n$, which is the negation of what you're asking when $p(n) \geq 2$. – Ryan Williams Jan 3 '17 at 4:38

• corrected 'growing $f(n)$'. – 1.. Dec 31 '16 at 8:38
• @ivmihajlin well even if it works for $\frac1{2^{n^c}}$ ($c\in(0,1)$) fraction of possible inputs with an $ACC^0$ circuit that would be ok. No need for constant fraction. – 1.. Dec 31 '16 at 11:16