<p>There seem to be typos in what you wrote; I take it you're asking: <em>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$</em>?</p>

<p>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. ;) </p>

CC BY-SA 3.0
2017-01-03T04:32:04.693Z
@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).
Turbo
CC BY-SA 3.0
2017-01-03T04:37:36.580Z
Also I think 'carry out the finite field arithmetic in ACC0' is likely a major open problem and may be impossible.
Turbo
CC BY-SA 3.0
2017-01-03T04:38:09.863Z
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
CC BY-SA 3.0
2017-01-03T04:12:03.160Z
2017-01-03T04:12:03.160Z
Ryan Williams
<p>We know that $NEXP$ is not in $ACC^0$ .</p>

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

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

<p>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? </p>

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

<hr>

<p>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&gt;0$) fraction of possible inputs computable in $ACC^0$?</p>

CC BY-SA 3.0
2017-01-01T09:10:34.697Z
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
CC BY-SA 3.0
2017-01-01T09:54:57.520Z
@SashoNikolov I initially had much less than $1/2$. I will change it.
Turbo
CC BY-SA 3.0
2017-01-01T09:57:51.310Z
@SashoNikolov sorry I thought logarithmic communication complexity also implies problem is in ACC^0? Is it not true?
Turbo
CC BY-SA 3.0
2017-01-01T11:53:51.140Z
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
CC BY-SA 3.0
2017-01-01T12:17:14.990Z
@AndrásSalamon I think they are immune to this variety of protocols.
Turbo
<cc.complexity-theory><circuit-complexity><big-picture><communication-complexity><worst-case>
How powerful is $ACC^0$ circuit class in average case?
Turbo
# How powerful is $ACC^0$ circuit class in average case?

(Asked by: username_0 on 2016-12-31)

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$?

**Tags:** cc.complexity-theory, circuit-complexity, big-picture, communication-complexity, worst-case

> **Comments:**
> **username_1**: 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.  
> **username_0**: @SashoNikolov I initially had much less than $1/2$. I will change it.  
> **username_0**: @SashoNikolov sorry I thought logarithmic communication complexity also implies problem is in ACC^0? Is it not true?  
> **username_2**: 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.  
> **username_0**: @AndrásSalamon I think they are immune to this variety of protocols.  

---

## 1 answers

### Answer by username_3 on 2017-01-03. Score: 8 | Accepted answer

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. ;)

> **Comments:**
> **username_0**: @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).  
> **username_0**: Also I think 'carry out the finite field arithmetic in ACC0' is likely a major open problem and may be impossible.  
> **username_3**: 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$.  

---

