The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912482221621248 |
|---|---|
| author | Brânzei, Simina Phillips, Reed Recker, Nicholas |
| author_facet | Brânzei, Simina Phillips, Reed Recker, Nicholas |
| contents | 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 of finding such a fixed point on the $k$-dimensional grid of side length $n$ under the $\leq$ relation. Specifically, there is an unknown monotone function $f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, n-1\}^k$ and an algorithm must query a vertex $v$ to learn $f(v)$.
A key special case of interest is the Boolean hypercube $\{0,1\}^k$, which is isomorphic to the power set lattice--the original setting of the Knaster-Tarski theorem. We prove a lower bound that characterizes the randomized and deterministic query complexity of the Tarski search problem on the Boolean hypercube as $Θ(k)$. More generally, we give a randomized lower bound of $Ω\left( k + \frac{k \log{n}}{\log{k}} \right)$ for the $k$-dimensional grid of side length $n$, which is asymptotically optimal in high dimensions when $k$ is large relative to $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03751 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube Brânzei, Simina Phillips, Reed Recker, Nicholas Computational Complexity Computer Science and Game Theory 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 of finding such a fixed point on the $k$-dimensional grid of side length $n$ under the $\leq$ relation. Specifically, there is an unknown monotone function $f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, n-1\}^k$ and an algorithm must query a vertex $v$ to learn $f(v)$. A key special case of interest is the Boolean hypercube $\{0,1\}^k$, which is isomorphic to the power set lattice--the original setting of the Knaster-Tarski theorem. We prove a lower bound that characterizes the randomized and deterministic query complexity of the Tarski search problem on the Boolean hypercube as $Θ(k)$. More generally, we give a randomized lower bound of $Ω\left( k + \frac{k \log{n}}{\log{k}} \right)$ for the $k$-dimensional grid of side length $n$, which is asymptotically optimal in high dimensions when $k$ is large relative to $n$. |
| title | The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.03751 |