Tarski Lower Bounds from Multi-Dimensional Herringbones

Simina Brânzei, Reed Phillips, Nicholas Recker

Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We analyze the query complexity of finding such a fixed point on the $k$-d…