no. 16 · Tuesday 17 November 2026
The Odd Shift is not sofic in dimensions $d \ge 3$
Abstract
In this paper, we prove that the Odd Shift $S_{odd}$ is not sofic for dimensions $d \ge 3$. Our proof uses lower bounds from communication complexity, specifically the result of Raz and Spieker on the nondeterministic communication complexity for the connectivity problem. We also prove that $S_{odd}$ is not sofic for dimension $d=2$ under the assumption we call Mute Ocean.
- comments
- 20 pages
- fields
- Dynamical Systems