# Tag Info

11

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem. The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs ...

5

Reingold's algorithm solves undirected s-t connectivity in logarithmic space. If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no longer be solved with a constant number of pointers. Paper "Pointer Programs and Undirected Reachability" by Schopp and Hofmann https://ulrichschoepp.de/...

2

If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot ...

2

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., Tarui's Theorem in communication complexity), which would then imply lower bounds on matrix rigidity (over the real numbers). For inner product, there is $O(1)$-bit public coin protocol for $\epsilon=1/n^{O(1)}$. Let me simplify by assuming ...

1

Although not exactly what you're looking for, this paper seems to be the most current (2019) efforts towards tight $AC^0[2]$ bounds as of yet, and provides a good summary of the difference between $AC^0$ and $AC^0[2]$ bounds.

1

You may find this video useful: https://www.youtube.com/watch?v=0vrqCDcxbxs&t=22s Also, this video here (time 00:43) states some books that can help: https://www.youtube.com/watch?v=mQQ36cDnmR8&t=158s

Only top voted, non community-wiki answers of a minimum length are eligible