A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ...
more >>>
We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has an n^{O(k^3)}-size witness circuit: a witness for x that can be encoded with a circuit ... more >>>
We prove that all functions that have low degree torus polynomials approximating them with small error also have MidBit^+ circuits computing them. This serves as a partial converse to the result that all ACC functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>
We give a conversion from non-classical polynomials to \mathit{MidBit}^+ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and \mathit{MidBit}^+ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>
The class ACC consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with AND, NOT and MOD_m gates, where m is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that MAJORITY does not belong to ACC. The Boolean ... more >>>