3 Search Results for "Gan, Junhao"

Document
DOI: 10.4230/LIPIcs.SWAT.2022.25
An Almost Optimal Algorithm for Unbounded Search with Noisy Information

Authors: Junhao Gan, Anthony Wirth, and Xin Zhang

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Given a sequence of integers, 𝒮 = s₁, s₂,… in ascending order, called the search domain, and an integer t, called the target, the predecessor problem asks for the target index N such that s_N is the largest integer in 𝒮 satisfying s_N ≤ t. We consider solving the predecessor problem with the least number of queries to a binary comparison oracle. For each query index i, the oracle returns whether s_i ≤ t or s_i > t. In particular, we study the predecessor problem under the UnboundedNoisy setting, where (i) the search domain 𝒮 is unbounded, i.e., n = |𝒮| is unknown or infinite, and (ii) the binary comparison oracle is noisy. We denote the former setting by Unbounded and the latter by Noisy. In Noisy, the oracle, for each query, independently returns a wrong answer with a fixed constant probability 0 < p < 1/2. In particular, even for two queries on the same index i, the answers from the oracle may be different. Furthermore, with a noisy oracle, the goal is to correctly return the target index with probability at least 1- Q, where 0 < Q < 1/2 is the failure probability. Our first result is an algorithm, called NoS, for Noisy that improves the previous result by Ben-Or and Hassidim [FOCS 2008] from an expected query complexity bound to a worst-case bound. We also achieve an expected query complexity bound, whose leading term has an optimal constant factor, matching the lower bound of Ben-Or and Hassidim. Building on NoS, we propose our NoSU algorithm, which correctly solves the predecessor problem in the UnboundedNoisy setting. We prove that the query complexity of NoSU is ∑_{i = 1}^k (log^{(i)} N) /(1-H(p))+ o(log N) when log Q^{-1} ∈ o(log N), where N is the target index, k = log^* N, the iterated logarithm, and H(p) is the entropy function. This improves the previous bound of O(log (N/Q) / (1-H(p))) by reducing the coefficient of the leading term from a large constant to 1. Moreover, we show that this upper bound can be further improved to (1 - Q) ∑_{i = 1}^k (log^{(i)} N) /(1-H(p))+ o(log N) in expectation, with the constant in the leading term reduced to 1 - Q. Finally, we show that an information-theoretic lower bound on the expected query cost of the predecessor problem in UnboundedNoisy is at least (1 - Q)(∑_{i = 1}^k log^{(i)} N - 2k)/(1-H(p)) - 10. This implies the constant factor in the leading term of our expected upper bound is indeed optimal.
Cite as

Junhao Gan, Anthony Wirth, and Xin Zhang. An Almost Optimal Algorithm for Unbounded Search with Noisy Information. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.SWAT.2022.25,
  author =	{Gan, Junhao and Wirth, Anthony and Zhang, Xin},
  title =	{{An Almost Optimal Algorithm for Unbounded Search with Noisy Information}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.25},
  URN =		{urn:nbn:de:0030-drops-161854},
  doi =		{10.4230/LIPIcs.SWAT.2022.25},
  annote =	{Keywords: Fault-tolerant search, noisy binary search, query complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.39
Graph Clustering in All Parameter Regimes

Authors: Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, and Xin Zhang

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Resolution parameters in graph clustering control the size and structure of clusters formed by solving a parametric objective function. Typically there is more than one meaningful way to cluster a graph, and solving the same objective function for different resolution parameters produces clusterings at different levels of granularity, each of which can be meaningful depending on the application. In this paper, we address the task of efficiently solving a parameterized graph clustering objective for all values of a resolution parameter. Specifically, we consider a new analysis-friendly objective we call LambdaPrime, involving a parameter λ ∈ (0,1). LambdaPrime is an adaptation of LambdaCC, a significant family of instances of the Correlation Clustering (minimization) problem. Indeed, LambdaPrime and LambdaCC are closely related to other parameterized clustering problems, such as parametric generalizations of modularity. They capture a number of specific clustering problems as special cases, including sparsest cut and cluster deletion. While previous work provides approximation results for a single value of the resolution parameter, we seek a set of approximately optimal clusterings for all values of λ in polynomial time. More specifically, we show that when a graph has m edges and n nodes, there exists a set of at most m clusterings such that, for every λ ∈ (0,1), the family contains an optimal solution to the LambdaPrime objective. This bound is tight on star graphs. We obtain a family of O(log n) clusterings by solving the parametric linear programming (LP) relaxation of LambdaPrime at O(log n) λ values, and rounding each LP solution using existing approximation algorithms. We prove that this is asymptotically tight: for a certain class of ring graphs, for all values of λ, Ω(log n) feasible solutions are required to provide a constant-factor approximation for the LambdaPrime LP relaxation. To minimize the size of the clustering family, we further propose an algorithm that yields a family of solutions of a size no more than twice of the minimum LP-approximating family.
Cite as

Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, and Xin Zhang. Graph Clustering in All Parameter Regimes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.MFCS.2020.39,
  author =	{Gan, Junhao and Gleich, David F. and Veldt, Nate and Wirth, Anthony and Zhang, Xin},
  title =	{{Graph Clustering in All Parameter Regimes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.39},
  URN =		{urn:nbn:de:0030-drops-127065},
  doi =		{10.4230/LIPIcs.MFCS.2020.39},
  annote =	{Keywords: Graph Clustering, Algorithms, Parametric Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.60
Result-Sensitive Binary Search with Noisy Information

Authors: Narthana S. Epa, Junhao Gan, and Anthony Wirth

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We describe new algorithms for the predecessor problem in the Noisy Comparison Model. In this problem, given a sorted list L of n (distinct) elements and a query q, we seek the predecessor of q in L: denoted by u, the largest element less than or equal to q. In the Noisy Comparison Model, the result of a comparison between two elements is non-deterministic. Moreover, multiple comparisons of the same pair of elements might have different results: each is generated independently, and is correct with probability p > 1/2. Given an overall error tolerance Q, the cost of an algorithm is measured by the total number of noisy comparisons; these must guarantee the predecessor is returned with probability at least 1 - Q. Feige et al. showed that predecessor queries can be answered by a modified binary search with Theta(log (n/Q)) noisy comparisons. We design result-sensitive algorithms for answering predecessor queries. The query cost is related to the index, k, of the predecessor u in L. Our first algorithm answers predecessor queries with O(log ((log^{*(c)} n)/Q) + log (k/Q)) noisy comparisons, for an arbitrarily large constant c. The function log^{*(c)} n iterates c times the iterated-logarithm function, log^* n. Our second algorithm is a genuinely result-sensitive algorithm whose expected query cost is bounded by O(log (k/Q)), and is guaranteed to terminate after at most O(log((log n)/Q)) noisy comparisons. Our results strictly improve the state-of-the-art bounds when k is in omega(1) intersected with o(n^epsilon), where epsilon > 0 is some constant. Moreover, we show that our result-sensitive algorithms immediately improve not only predecessor-query algorithms, but also binary-search-like algorithms for solving key applications.
Cite as

Narthana S. Epa, Junhao Gan, and Anthony Wirth. Result-Sensitive Binary Search with Noisy Information. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{epa_et_al:LIPIcs.ISAAC.2019.60,
  author =	{Epa, Narthana S. and Gan, Junhao and Wirth, Anthony},
  title =	{{Result-Sensitive Binary Search with Noisy Information}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{60:1--60:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.60},
  URN =		{urn:nbn:de:0030-drops-115568},
  doi =		{10.4230/LIPIcs.ISAAC.2019.60},
  annote =	{Keywords: Fault-tolerant search, random walks, noisy comparisons, predecessor queries}
}
  • Refine by Author
  • 3 Gan, Junhao
  • 3 Wirth, Anthony
  • 2 Zhang, Xin
  • 1 Epa, Narthana S.
  • 1 Gleich, David F.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Predecessor queries
  • 2 Theory of computation → Sorting and searching
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 2 Fault-tolerant search
  • 1 Algorithms
  • 1 Graph Clustering
  • 1 Parametric Linear Programming
  • 1 noisy binary search
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2022

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact