2h
asked On covering by smooth numbers
5h
comment A trivial question on hierarchy
@Kaveh I am just surprised with 5000 years of mathematics with us, we still cannot show $$\mathsf{ACC^0\subsetneq PH}.$$
5h
comment What does a polynomial look like under projection of underlying space?
True. So let us call this a mock stereographic projection. All we care about is 1-1 map.
7h
comment A trivial question on hierarchy
@Kaveh what is a good text for circuit complexity?
7h
revised Complexity of algebraic problems
added 188 characters in body
8h
comment A trivial question on hierarchy
So moral of story is uniform circuits are like turing machines, non-uniformity is slightly more powerful, we get a turing machine for every input length.
8h
comment What does a polynomial look like under projection of underlying space?
Consider 8 vertex cube in R^3. When you project from north pole of sphere enclosing cube (assuming north pole middle of a face and top of it), your 8 vertices land on two squares each enclosed by a circle (concentric circles). We need to project there 8 points on the line. May be we can take outer circle's north pole, then projection of interior points have messier coordinates.
8h
accepted A trivial question on hierarchy
8h
comment A trivial question on hierarchy
oic ok... there are two things going on. non-uniform TC^0 could contain NEXP. Only uniform TC^0 does not contain NEXP.
8h
comment A trivial question on hierarchy
ACC^0 is contained in TC^0 regardless of uniformity/non-uniformity.
8h
comment A trivial question on hierarchy
@RickyDemer Nikhil states regardless of uniformity or not $\mathsf{ACC^0\subseteq TC^0\subseteq NP\subsetneq NEXP}$ holds.
8h
comment A trivial question on hierarchy
@Nikhil Then what is Ryan's result about (since we already know $\mathsf{NP\subsetneq NEXP}$, so your statement $\mathsf{\implies ACC^0\subsetneq NEXP}$?
9h
comment A trivial question on hierarchy
Ok that clarifies things a bit. Wiki is correct on that they give results on uniform classes. Ryan's work is on non-uniform classes which are more powerful than uniform classes. So Ryan's breakthrough is not included in wiki summary except for that one line sloppy statement which mentions Ryan's breakthrough. In summary $uniformACC0\subseteq uniformTC0$ is correct. But non-uniform ACC0 could be much more powerful which is what Ryan's result tries. Correct?
9h
revised A trivial question on hierarchy
added 224 characters in body
9h
comment A trivial question on hierarchy
So wiki results on $ACC^0$ are only for uniform circuits, right?
9h
comment A trivial question on hierarchy
Actually it states "It is conjectured that ACC0 is unable to compute the majority function of its inputs (i.e. the inclusion in TC0 is strict)"
9h
comment A trivial question on hierarchy
sorry what is a good reference to understand the hierarchy and uniformness/non-uniformness distinction that Ricky Demer is posting. Where could I find result on what Ricky Demer has posted?
9h
revised A trivial question on hierarchy
added 533 characters in body
9h
comment A trivial question on hierarchy
Ok certainly I am missing difference between uniform and non-uniform circuits.
9h
comment A trivial question on hierarchy
I mean wiki states $ACC0$ is contained in $TC0$ which is in $NC1$ so on.. is it talking about this in uniform context?
1 2 3 4 5