Search Results

Documents authored by Wang, Haoyu

Document
DOI: 10.4230/LIPIcs.MFCS.2026.78
Randomized and Quantum Lifting for One-Way Conservative NOF Model

Authors: Haoyu Wang and Pei Wu

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
We consider lifting theorems that transfer lower bounds for two-party communication problems to multiparty communication problems. In particular, following the deterministic Number-on-Forehead (NOF) lifting framework of Yang and Zhang, we study randomized and quantum one-way NOF lifting for composed problems F(z,𝐱) = f(z,G(𝐱)). We work in a one-way NOF model in which only the last player’s view is restricted. The other players have their usual NOF views and communicate as usual, but the last player sees only the gadget output G(𝐱), not the gadget input 𝐱. This kind of restricted-view has appeared in the NOF literature under the name conservative model. Our main contribution is a pair of lifting theorems for this model. In the randomized setting, we show that lifting follows when each preimage G^{-1}(v), the set of gadget inputs with output v, looks pseudorandom to large cylinder intersections. In the quantum setting, we prove an analogous theorem. Equivalently, conservative protocols for F(z,𝐱) = f(z,G(𝐱)) can be converted into two-party one-way protocols for f(z,v) with comparable cost, and the error loss controlled by the corresponding pseudorandomness parameters. Thus, this restriction isolates a setting in which both randomized and quantum one-way NOF lifting can be proved by a direct simulation argument. We prove the required pseudorandomness properties for the generalized inner product gadget over finite fields, using the multiparty character-sum bounds of Yang and Zhang, and for random gadgets, which give non-explicit lifting. As applications, Boolean Hidden Matching yields a randomized-versus-quantum separation in the conservative NOF model, and lifting INDEX gives randomized and quantum conservative NOF lower bounds for O(log n) players.
Cite as

Haoyu Wang and Pei Wu. Randomized and Quantum Lifting for One-Way Conservative NOF Model. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 78:1-78:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.MFCS.2026.78,
  author =	{Wang, Haoyu and Wu, Pei},
  title =	{{Randomized and Quantum Lifting for One-Way Conservative NOF Model}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{78:1--78:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.78},
  URN =		{urn:nbn:de:0030-drops-274604},
  doi =		{10.4230/LIPIcs.MFCS.2026.78},
  annote =	{Keywords: communication complexity, lifting theorem, number-on-forehead model}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2025.19
Search Space Reduction Using Species Distribution Modeling with Simulated Pollen Signatures

Authors: Haoyu Wang, Jennifer A. Miller, and Shalene Jha

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

Abstract
Microscopic trace materials, such as pollen, are an important category of forensic evidence recovered during investigations. As an environmentally ubiquitous substance that can attach to various surfaces, pollen enables the linking of objects and people in space and time. In this study, we assessed the extent to which the search space could be reduced using simulated pollen signatures. These signatures were compiled by randomly selecting pairs of geographic coordinates on the Earth’s terrestrial land and querying the Global Biodiversity Information Facility (GBIF) database to identify plant taxa within 50 meters of the coordinates. These taxa were then treated as the parent taxa of the pollen, simulating the hypothetical attachment of pollen signatures to objects or individuals. For each identified pollen taxon, we modeled habitat suitability for the parent plant taxa and combined the spatial distributions to refine the geolocation search area. Since the actual coordinates for these locations of interest were known, we were able to evaluate the global performance of the search space reduction under the assumption of an extreme constraint that no other contextual information was available.
Cite as

Haoyu Wang, Jennifer A. Miller, and Shalene Jha. Search Space Reduction Using Species Distribution Modeling with Simulated Pollen Signatures. In 13th International Conference on Geographic Information Science (GIScience 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 346, pp. 19:1-19:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.GIScience.2025.19,
  author =	{Wang, Haoyu and Miller, Jennifer A. and Jha, Shalene},
  title =	{{Search Space Reduction Using Species Distribution Modeling with Simulated Pollen Signatures}},
  booktitle =	{13th International Conference on Geographic Information Science (GIScience 2025)},
  pages =	{19:1--19:6},
  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.19},
  URN =		{urn:nbn:de:0030-drops-238485},
  doi =		{10.4230/LIPIcs.GIScience.2025.19},
  annote =	{Keywords: geoforensics, species distribution modeling, search space reduction}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.77
How to Improve Joint Suitability Mapping for Search Space Reduction? (Short Paper)

Authors: Haoyu Wang and Jennifer A. Miller

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Geoforensic analyses are used to identify the location history of objects or people of interest. An effective method for location history identification is to use joint probability or suitability of trace materials. Species distribution models have been used to derive joint suitability distributions using suitable biotic trace evidence such as pollen. One of the key objectives for such analyses is to effectively reduce potential search space and search effort for investigators. This research presents a novel framework for modeling the habitat suitability of pollen identified at the plant species-level to generate joint suitability maps. We provide major limitations and challenges faced by current geolocation analyses based on species distribution models, including opportunities to improve the joint suitability analyses for search space reduction. A conditional probability approach for geolocation identification is also demonstrated for possible future applications in real-world forensic cases.
Cite as

Haoyu Wang and Jennifer A. Miller. How to Improve Joint Suitability Mapping for Search Space Reduction? (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 77:1-77:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.GIScience.2023.77,
  author =	{Wang, Haoyu and Miller, Jennifer A.},
  title =	{{How to Improve Joint Suitability Mapping for Search Space Reduction?}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{77:1--77:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.77},
  URN =		{urn:nbn:de:0030-drops-189723},
  doi =		{10.4230/LIPIcs.GIScience.2023.77},
  annote =	{Keywords: forensic geolocation, species distribution modeling, conditional probability, search space reduction}
}

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