Timeline for How powerful is $ACC^0$ circuit class in average case?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 1, 2017 at 3:50 | comment | added | Turbo | @RickyDemer then please interpret it in all possible sensible ways. I am done updating. | |
| Jan 1, 2017 at 2:35 | comment | added | Turbo | 'gargantuan beast'. | |
| Jan 1, 2017 at 0:50 | comment | added | user6973 | @AJ. : That class is probably ALL. For the opposite way, I'm not aware of anything for ACC0 that doesn't also work for P/poly. | |
| Jan 1, 2017 at 0:45 | history | edited | user6973 | CC BY-SA 3.0 |
changed since fractions referred to are now less than 1
|
| Dec 31, 2016 at 11:46 | comment | added | Turbo | I ask if for $\frac1{f(n)}$ fraction of inputs if an $ACC^0$ circuit computes $f$ then what is the largest class that is known that $f$ can belong to? In opposite way if there is no $ACC^0$ circuit that can do the job for this fraction what is the smallest class we have separation from $ACC^0$. | |
| Dec 31, 2016 at 11:33 | comment | added | ivmihajlin | @AJ so, the definition of complexity you are interested is: the smallest number $c$, such that $\forall S$ - subset of inputs, size of the smallest $ACC_0$ circuit that agrees with $f$ on S is $\leq c$. Right? | |
| Dec 31, 2016 at 11:16 | comment | added | Turbo | @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. | |
| Dec 31, 2016 at 9:24 | comment | added | ivmihajlin | It also not clear what exactly you mean by "fraction of inputs computable in $ACC0$?". Do you want to have agreement on $(1/2 + \epsilon)$ fraction of inputs for some $\epsilon$? Or there is a fraction of inputs, such that corresponding partial function is hard? | |
| Dec 31, 2016 at 9:20 | comment | added | ivmihajlin | He was just pointing that you are using word fraction incorrectly. You want to say $\frac{2^n}{f(n)}$ inputs, rather then "fraction of inputs." | |
| Dec 31, 2016 at 9:15 | comment | added | Turbo | I have changed my problem scaling. It is no longer $\omega(1)$ and $o(2^n)$ so your argument will not work. | |
| Dec 31, 2016 at 9:12 | comment | added | user6973 | Yes. [Fractions of the inputs on which something is computable] are at most 1, so for sufficiently large n, we cannot have $\omega(1)$ fraction of inputs computable. | |
| Dec 31, 2016 at 9:07 | history | edited | user6973 | CC BY-SA 3.0 |
indicated uncertainty
|
| Dec 31, 2016 at 8:58 | comment | added | Turbo | Do I still have an issue? Also $\omega(1)\neq O(1)$ and so the function could still grow. | |
| Dec 31, 2016 at 8:52 | comment | added | user6973 | I edited to point to the current issue. | |
| Dec 31, 2016 at 8:51 | history | edited | user6973 | CC BY-SA 3.0 |
mentioned current issue
|
| Dec 31, 2016 at 8:44 | comment | added | Turbo | ok updated mine to what I mean by growing. | |
| Dec 31, 2016 at 8:41 | comment | added | user6973 | changed my f | |
| Dec 31, 2016 at 8:41 | history | edited | user6973 | CC BY-SA 3.0 |
changed my f
|
| Dec 31, 2016 at 8:38 | comment | added | Turbo | corrected 'growing $f(n)$'. | |
| Dec 31, 2016 at 8:30 | history | answered | user6973 | CC BY-SA 3.0 |