DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.52

Tarski Lower Bounds from Multi-Dimensional Herringbones

Authors: Simina Brânzei, Reed C. Phillips, and Nicholas J. Recker

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

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-dimensional grid of side length n under the ≤ relation. In this setting, there is an unknown monotone function f: {0,1,…, n-1}^k → {0,1,…, n-1}^k and an algorithm must query a vertex v to learn f(v). The goal is to find a fixed point of f using as few oracle queries as possible. We show that the randomized query complexity of this problem is Ω((k⋅log²n)/log k) for all n,k ≥ 2. This unifies and improves upon two prior results: a lower bound of Ω(log²n) from [Etessami et al., 2020] and a lower bound of Ω((k⋅log(n)/log(k)) from [Brânzei et al., 2024], respectively.

Cite as

Simina Brânzei, Reed C. Phillips, and Nicholas J. Recker. Tarski Lower Bounds from Multi-Dimensional Herringbones. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{branzei_et_al:LIPIcs.APPROX/RANDOM.2025.52,
  author =	{Br\^{a}nzei, Simina and Phillips, Reed C. and Recker, Nicholas J.},
  title =	{{Tarski Lower Bounds from Multi-Dimensional Herringbones}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  URN =		{urn:nbn:de:0030-drops-244186},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  annote =	{Keywords: Tarski’s theorem, monotone functions, lattices, fixed points, computational complexity, oracle model, query complexity, lower bounds}
}

@InProceedings{branzei_et_al:LIPIcs.APPROX/RANDOM.2025.52,
  author =	{Br\^{a}nzei, Simina and Phillips, Reed C. and Recker, Nicholas J.},
  title =	{{Tarski Lower Bounds from Multi-Dimensional Herringbones}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  URN =		{urn:nbn:de:0030-drops-244186},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  annote =	{Keywords: Tarski’s theorem, monotone functions, lattices, fixed points, computational complexity, oracle model, query complexity, lower bounds}
}

Search Results

Documents authored by Recker, Nicholas J.

Tarski Lower Bounds from Multi-Dimensional Herringbones

Abstract

Cite as

Thanks for your feedback!

Could not send message