6
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jan 1, 2017 at 9:10
  • $\begingroup$ @SashoNikolov I initially had much less than $1/2$. I will change it. $\endgroup$
    – Turbo
    Commented Jan 1, 2017 at 9:54
  • $\begingroup$ @SashoNikolov sorry I thought logarithmic communication complexity also implies problem is in ACC^0? Is it not true? $\endgroup$
    – Turbo
    Commented Jan 1, 2017 at 9:57
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Jan 1, 2017 at 11:53
  • $\begingroup$ @AndrásSalamon I think they are immune to this variety of protocols. $\endgroup$
    – Turbo
    Commented Jan 1, 2017 at 12:17

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ @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). $\endgroup$
    – Turbo
    Commented Jan 3, 2017 at 4:32
  • $\begingroup$ Also I think 'carry out the finite field arithmetic in ACC0' is likely a major open problem and may be impossible. $\endgroup$
    – Turbo
    Commented Jan 3, 2017 at 4:37
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Ryan Williams
    Commented Jan 3, 2017 at 4:38
0
$\begingroup$

The answer depends on how your phrasing is to be parsed.
In any case, the constant functions from ​ {0,1}* ​ to {0,1} are both in ACC0
and for all languages L and non-negative integers n, at least one of
those constant functions agrees with L on at least 1/2 of the n-bit strings.
You might be interested in "errorless" heuristics.

Improve this answer
$\endgroup$
15
  • $\begingroup$ corrected 'growing $f(n)$'. $\endgroup$
    – Turbo
    Commented Dec 31, 2016 at 8:38
  • $\begingroup$ changed my f ​ ​ $\endgroup$
    – user6973
    Commented Dec 31, 2016 at 8:41
  • $\begingroup$ ok updated mine to what I mean by growing. $\endgroup$
    – Turbo
    Commented Dec 31, 2016 at 8:44
  • $\begingroup$ I edited to point to the current issue. ​ ​ $\endgroup$
    – user6973
    Commented Dec 31, 2016 at 8:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Turbo
    Commented Dec 31, 2016 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.