5 Search Results for "Nguyen, Hoai-An"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.140
Streaming Complexity Separations for Dense and Sparse Graphs

Authors: Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, and David P. Woodruff

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that O(n/ε²) space is sufficient and that Ω(n) space is necessary. In contrast, for graphs with Θ(n/ε²) edges, the situation is markedly different: we show that the problem requires Ω(n log(ε² n)/ε²) space for any ε = ω(1/√n), which is tight for the full range of ε. We also give an Ω(n log n/ε²)-space lower bound against deterministic algorithms for outputting a (1-ε) approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.
Cite as

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, and David P. Woodruff. Streaming Complexity Separations for Dense and Sparse Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 140:1-140:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ICALP.2026.140,
  author =	{Liu, Yang P. and Nguyen, Hoai-An and Singer, Noah G. and Woodruff, David P.},
  title =	{{Streaming Complexity Separations for Dense and Sparse Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{140:1--140:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.140},
  URN =		{urn:nbn:de:0030-drops-265290},
  doi =		{10.4230/LIPIcs.ICALP.2026.140},
  annote =	{Keywords: streaming, maximum cut, complexity separations}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.54
Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space

Authors: Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantly more efficient under a promise that the arboricity of the graph is bounded by some parameter ̅α. However, when this promise is violated, the estimates given by these algorithms are no longer guaranteed to be correct. For the triangle counting task, we give an algorithm that requires no promise on the input graph G, and computes a (1±ε)-approximation for the number of triangles t in G in time O^*((m⋅ α(G))/t + m/(t^{2/3)}), where α(G) is the arboricity of the graph. The algorithm can be used on any graph G (no prior knowledge of the arboricity α(G) is required), and the algorithm adapts its run-time on the fly based on the graph G. We accomplish this by trying a sequence of candidate values α̃ for α(G) and using a novel algorithm in the framework of testable algorithms. This ensures that wrong candidates α̃ cannot lead to wrong estimates: if the advice is incorrect, the algorithm either succeeds despite this or detects this and continues with a new candidate. Once the algorithm accepts the candidate, its output is guaranteed to be correct with high probability. We prove that this approach preserves - up to an additive overhead - the dramatic efficiency gains obtainable when good arboricity bounds are known in advance, while ensuring robustness against misleading advice. We further complement this result with a lower bound, showing that such an overhead is unavoidable whenever the advice may be faulty. We further demonstrate implications of our results for triangle counting in the streaming model.
Cite as

Talya Eden, Ronitt Rubinfeld, and Arsen Vasilyan. Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 54:1-54:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ITCS.2026.54,
  author =	{Eden, Talya and Rubinfeld, Ronitt and Vasilyan, Arsen},
  title =	{{Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{54:1--54:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.54},
  URN =		{urn:nbn:de:0030-drops-253417},
  doi =		{10.4230/LIPIcs.ITCS.2026.54},
  annote =	{Keywords: Sublinear Algorithms, Triangle Counting, Edge Counting, Arboricity}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2025.5
Analysis of Points of Interests Recommended for Leisure Walk Descriptions

Authors: Ehsan Hamzei, Thi Minh Hoai Bui, Martin Tomko, and Stephan Winter

Published in: LIPIcs, Volume 346, 13th International Conference on Geographic Information Science (GIScience 2025)

Abstract
Leisure walking is a physical activity where locomotion through a natural or even urban environment is the goal in itself, e.g., in pursuit of health and wellbeing. In contrast to destination-oriented walks that are focused on navigation efficiency (i.e., shortest or simplest walk from source to destination), leisure walks emphasize experiencing the environment, engaging in activities, and discovering places that may be off route, or intermediate destinations en-route, summarily called points of interest (POIs). POIs are key for recommending leisure walks, yet a detailed analysis of POIs in the context of leisure walking is missing in the literature. This study extracts and annotates POIs of leisure walking recommendations available in WalkingMaps.com.au, creating an annotated dataset to address this research gap and provide a first analysis of leisure walking descriptions. We classify POIs using the verbal description provided in the dataset, match them with data available in OpenStreetMap (OSM), and compare the POIs with nearby alternatives in OSM. Our analysis reveals thematic and spatial patterns in POI selection, offering a machine learning approach to model POI choices for leisure walks. We further evaluate the availability of rich data in OSM for future automated leisure walking recommendation. This study contributes to automated systems for recommending leisure walks, tailoring suggestions based on available information in the spatial open data, and presents an annotated dataset to facilitate future research in this field.
Cite as

Ehsan Hamzei, Thi Minh Hoai Bui, Martin Tomko, and Stephan Winter. Analysis of Points of Interests Recommended for Leisure Walk Descriptions. In 13th International Conference on Geographic Information Science (GIScience 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 346, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hamzei_et_al:LIPIcs.GIScience.2025.5,
  author =	{Hamzei, Ehsan and Bui, Thi Minh Hoai and Tomko, Martin and Winter, Stephan},
  title =	{{Analysis of Points of Interests Recommended for Leisure Walk Descriptions}},
  booktitle =	{13th International Conference on Geographic Information Science (GIScience 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-378-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{346},
  editor =	{Sila-Nowicka, Katarzyna and Moore, Antoni and O'Sullivan, David and Adams, Benjamin and Gahegan, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2025.5},
  URN =		{urn:nbn:de:0030-drops-238341},
  doi =		{10.4230/LIPIcs.GIScience.2025.5},
  annote =	{Keywords: leisure walks, points of interest, places, platial information}
}
Document
Resource Paper
DOI: 10.4230/TGDK.2.2.6
TØIRoads: A Road Data Model Generation Tool

Authors: Grunde Haraldsson Wesenberg and Ana Ozaki

Published in: TGDK, Volume 2, Issue 2 (2024): Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 2, Issue 2

Abstract
We describe road data models which can represent high level features of a road network such as population, points of interest, and road length/cost and capacity, while abstracting from time and geographic location. Such abstraction allows for a simplified traffic usage and congestion analysis that focus on the high level features. We provide theoretical results regarding mass conservation and sufficient conditions for avoiding congestion within the model. We describe a road data model generation tool, which we call "TØI Roads". We also describe several parameters that can be specified by a TØI Roads user to create graph data that can serve as input for training graph neural networks (or another learning approach that receives graph data as input) for predicting congestion within the model. The road data model generation tool allows, for instance, the study of the effects of population growth and how changes in road capacity can mitigate traffic congestion.
Cite as

Grunde Haraldsson Wesenberg and Ana Ozaki. TØIRoads: A Road Data Model Generation Tool. In Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 2, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{wesenberg_et_al:TGDK.2.2.6,
  author =	{Wesenberg, Grunde Haraldsson and Ozaki, Ana},
  title =	{{T{\O}IRoads: A Road Data Model Generation Tool}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{6:1--6:12},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.2.6},
  URN =		{urn:nbn:de:0030-drops-225901},
  doi =		{10.4230/TGDK.2.2.6},
  annote =	{Keywords: Road Data, Transportation, Graph Neural Networks, Synthetic Dataset Generation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.48
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting

Authors: Sepehr Assadi and Hoai-An Nguyen

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

Abstract
The h-index is a metric used to measure the impact of a user in a publication setting, such as a member of a social network with many highly liked posts or a researcher in an academic domain with many highly cited publications. Specifically, the h-index of a user is the largest integer h such that at least h publications of the user have at least h units of positive feedback. We design an algorithm that, given query access to the n publications of a user and each publication’s corresponding positive feedback number, outputs a (1± ε)-approximation of the h-index of this user with probability at least 1-δ in time O(n⋅ln(1/δ) / (ε²⋅h)), where h is the actual h-index which is unknown to the algorithm a-priori. We then design a novel lower bound technique that allows us to prove that this bound is in fact asymptotically optimal for this problem in all parameters n,h,ε, and δ. Our work is one of the first in sublinear time algorithms that addresses obtaining asymptotically optimal bounds, especially in terms of the error and confidence parameters. As such, we focus on designing novel techniques for this task. In particular, our lower bound technique seems quite general - to showcase this, we also use our approach to prove an asymptotically optimal lower bound for the problem of estimating the number of triangles in a graph in sublinear time, which now is also optimal in the error and confidence parameters. This latter result improves upon prior lower bounds of Eden, Levi, Ron, and Seshadhri (FOCS'15) for this problem, as well as multiple follow-up works that extended this lower bound to other subgraph counting problems.
Cite as

Sepehr Assadi and Hoai-An Nguyen. Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2022.48,
  author =	{Assadi, Sepehr and Nguyen, Hoai-An},
  title =	{{Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{48:1--48:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.48},
  URN =		{urn:nbn:de:0030-drops-171708},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.48},
  annote =	{Keywords: Sublinear time algorithms, h-index, asymptotically optimal bounds, lower bounds, subgraph counting}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2025
  • 1 2024
  • 1 2022

  • Refine by Author
  • 2 Nguyen, Hoai-An
  • 1 Assadi, Sepehr
  • 1 Bui, Thi Minh Hoai
  • 1 Eden, Talya
  • 1 Hamzei, Ehsan
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 3 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 General and reference → Evaluation
  • 1 Information systems → Geographic information systems
  • 1 Information systems → Location based services

  • Refine by Keyword
  • 1 Arboricity
  • 1 Edge Counting
  • 1 Graph Neural Networks
  • 1 Road Data
  • 1 Sublinear Algorithms
  • 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