2 Search Results for "Jiamjitrak, Wanchote Po"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.11
On Finding Randomly Planted Cliques in Arbitrary Graphs

Authors: Francesco Agrimonti, Marco Bressan, and Tommaso d'Orsi

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

Abstract
We study a planted clique model introduced by Feige [Uriel Feige, 2021] where a complete graph of size c⋅ n is planted uniformly at random in an arbitrary n-vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size (c/3)^O(1/c) ⋅ n as long as the original graph has maximum degree at most (1-p)n for some fixed p > 0. The proof hinges on showing that the degrees of the final graph are correlated with the planted clique, in a way similar to (but more intricate than) the classical G(n,1/2)+K_√n planted clique model. Our algorithm suggests a separation from the worst-case model, where, assuming the Unique Games Conjecture, no polynomial algorithm can find cliques of size Ω(n) for every fixed c > 0, even if the input graph has maximum degree (1-p)n. Our techniques extend beyond the planted clique model. For example, when the planted graph is a balanced biclique, we recover a balanced biclique of size larger than the best guarantees known for the worst case.
Cite as

Francesco Agrimonti, Marco Bressan, and Tommaso d'Orsi. On Finding Randomly Planted Cliques in Arbitrary Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrimonti_et_al:LIPIcs.APPROX/RANDOM.2025.11,
  author =	{Agrimonti, Francesco and Bressan, Marco and d'Orsi, Tommaso},
  title =	{{On Finding Randomly Planted Cliques in Arbitrary Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{11:1--11:18},
  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.11},
  URN =		{urn:nbn:de:0030-drops-243774},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.11},
  annote =	{Keywords: Computational Complexity, Planted Clique, Semi-random, Unique Games Conjecture, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.28
New Binary Search Tree Bounds via Geometric Inversions

Authors: Parinya Chalermsook and Wanchote Po Jiamjitrak

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The long-standing dynamic optimality conjecture postulates the existence of a dynamic binary search tree (BST) that is O(1)-competitive to all other dynamic BSTs. Despite attempts from many groups of researchers, we believe the conjecture is still far-fetched. One of the main reasons is the lack of the "right" potential functions for the problem: existing results that prove various consequences of dynamic optimality rely on very different potential function techniques, while proving dynamic optimality requires a single potential function that can be used to derive all these consequences. In this paper, we propose a new potential function, that we call extended (geometric) inversion. Inversion is arguably the most natural potential function principle that has been used in competitive analysis but has never been used in the context of BSTs. We use our potential function to derive new results, as well as streamlining/strengthening existing results. First, we show that a broad class of BST algorithms (including Greedy and Splay) are O(1)-competitive to Move-to-Root algorithm and therefore have simulation embedding property - a new BST property that was recently introduced and studied by Levy and Tarjan (SODA 2019). This result, besides substantially expanding the list of BST algorithms having this property, gives the first potential function proof of the simulation embedding property for BSTs (thus unifying apparently different kinds of results). Moreover, our analysis is the first where the costs of two dynamic binary search trees are compared against each other directly and systematically. Secondly, we use our new potential function to unify and strengthen known BST bounds, e.g., showing that Greedy satisfies the weighted dynamic finger property within a multiplicative factor of (5+o(1)).
Cite as

Parinya Chalermsook and Wanchote Po Jiamjitrak. New Binary Search Tree Bounds via Geometric Inversions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ESA.2020.28,
  author =	{Chalermsook, Parinya and Jiamjitrak, Wanchote Po},
  title =	{{New Binary Search Tree Bounds via Geometric Inversions}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.28},
  URN =		{urn:nbn:de:0030-drops-128944},
  doi =		{10.4230/LIPIcs.ESA.2020.28},
  annote =	{Keywords: Binary Search Tree, Potential Function, Inversion, Data Structures, Online Algorithms}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2020

  • Refine by Author
  • 1 Agrimonti, Francesco
  • 1 Bressan, Marco
  • 1 Chalermsook, Parinya
  • 1 Jiamjitrak, Wanchote Po
  • 1 d'Orsi, Tommaso

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Binary Search Tree
  • 1 Computational Complexity
  • 1 Data Structures
  • 1 Inversion
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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