Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
Simina Brânzei, Reed Phillips, Nicholas Recker
The Knaster-Tarski theorem, also known as Tarski's theorem, guarantees that every monotone function defined on a complete lattice has a fixed point. We analyze the query complexity…
cs.CC2025
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 -d…