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

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

$\endgroup$
  • $\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$ – T.... Jan 3 '17 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$ – T.... Jan 3 '17 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 Jan 3 '17 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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