pipette
ESEspañol

The Six-Dimensional Tarski Problem is -Hard

Krist\'of Z\'olomy

Preprint

In the authors' words

We study the deterministic query complexity of finding a fixed point of a monotone function , where querying returns . For fixed , earlier work established a lower bound of and an upper bound of for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to . In particular, we obtain the optimal deterministic query complexity in six dimensions.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 17 pages, 7 figures