A Levelset Algorithm for 3D-Tarski
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908632326602752 |
|---|---|
| author | Haslebacher, Sebastian Lill, Jonas |
| author_facet | Haslebacher, Sebastian Lill, Jonas |
| contents | We present a simple new algorithm for finding a Tarski fixed point of a monotone function $F : [N]^3 \rightarrow [N]^3$. Our algorithm runs in $O(\log^2 N)$ time and makes $O(\log^2 N)$ queries to $F$, matching the $Ω(\log^2 N)$ query lower bound due to Etessami et al. as well as the existing state-of-the-art algorithm due to Fearnley et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_14777 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Levelset Algorithm for 3D-Tarski Haslebacher, Sebastian Lill, Jonas Data Structures and Algorithms We present a simple new algorithm for finding a Tarski fixed point of a monotone function $F : [N]^3 \rightarrow [N]^3$. Our algorithm runs in $O(\log^2 N)$ time and makes $O(\log^2 N)$ queries to $F$, matching the $Ω(\log^2 N)$ query lower bound due to Etessami et al. as well as the existing state-of-the-art algorithm due to Fearnley et al. |
| title | A Levelset Algorithm for 3D-Tarski |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.14777 |