Search Results

Documents authored by Phillips, Reed C.

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact