4 Search Results for "Hung, Wei-Chun"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.58
Testability and Local Certification of Monotone Properties in Minor-Closed Classes

Authors: Louis Esperet and Sergey Norin

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the sparse model. We prove that for any proper minor-closed class 𝒢, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from 𝒢 in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many forbidden subgraphs. Our result implies for instance that for any integers k and t, k-colorability of K_t-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.
Cite as

Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Properties in Minor-Closed Classes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.ICALP.2022.58,
  author =	{Esperet, Louis and Norin, Sergey},
  title =	{{Testability and Local Certification of Monotone Properties in Minor-Closed Classes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.58},
  URN =		{urn:nbn:de:0030-drops-163997},
  doi =		{10.4230/LIPIcs.ICALP.2022.58},
  annote =	{Keywords: Property testing, sparse model, local certification, minor-closed classes}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.21
On the Tails of the Limiting QuickSort Density

Authors: James Allen Fill and Wei-Chun Hung

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.
Cite as

James Allen Fill and Wei-Chun Hung. On the Tails of the Limiting QuickSort Density. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 21:1-21:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fill_et_al:LIPIcs.AofA.2018.21,
  author =	{Fill, James Allen and Hung, Wei-Chun},
  title =	{{On the Tails of the Limiting QuickSort Density}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{21:1--21:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.21},
  URN =		{urn:nbn:de:0030-drops-89144},
  doi =		{10.4230/LIPIcs.AofA.2018.21},
  annote =	{Keywords: Quicksort, density tails, asymptotic bounds, Landau-Kolmogorov inequality}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.29
ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization

Authors: Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Monitor objects are used extensively for thread-safety and synchronization in shared memory parallel programs. They provide ease of use, and enable straightforward correctness analysis. However, they inhibit parallelism by enforcing serial executions of critical sections, and thus the performance of parallel programs with monitors scales poorly with number of processes. Their current design and implementation is also ill-suited for thread synchronization across multiple thread-safe objects. We present ActiveMonitor - a framework that allows multi-object synchronization without global locks, and improves parallelism by exploiting asynchronous execution of critical sections. We evaluate the performance of Java based implementation of ActiveMonitor on micro-benchmarks involving light and heavy critical sections, as well as on single-source-shortest-path problem in directed graphs. Our results show that on most of these problems, ActiveMonitor based programs outperform programs implemented using Java's reentrant-lock and condition constructs.
Cite as

Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg. ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hung_et_al:LIPIcs.OPODIS.2015.29,
  author =	{Hung, Wei-Lun and Chauhan, Himanshu and Garg, Vijay K.},
  title =	{{ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.29},
  URN =		{urn:nbn:de:0030-drops-66188},
  doi =		{10.4230/LIPIcs.OPODIS.2015.29},
  annote =	{Keywords: concurrent/parallel programming, monitors, concurrency}
}
Document
DOI: 10.4230/DagSemProc.09181.3
09181 Working Group on Hybridization between R&S, DoE and Optimization

Authors: Chun-Hung Chen, Liu Hong, Paul B. Kantor, David P. Morton, Juta Pichitlamken, and Matthias Seeger

Published in: Dagstuhl Seminar Proceedings, Volume 9181, Sampling-based Optimization in the Presence of Uncertainty (2009)

Abstract
This is the report of the working group on the relation between, or hybrid combination of design experiment optimization and R&S. The rapporteur, Paul Kantor, learned a great deal at the conference which he summarized by sharing the cartoon shown here. ("A student asking the teacher'... may i be excused, my is full" (from a 1986 cartoon by Gary Larson) - omitted here for copyright reasons).
Cite as

Chun-Hung Chen, Liu Hong, Paul B. Kantor, David P. Morton, Juta Pichitlamken, and Matthias Seeger. 09181 Working Group on Hybridization between R&S, DoE and Optimization. In Sampling-based Optimization in the Presence of Uncertainty. Dagstuhl Seminar Proceedings, Volume 9181, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.09181.3,
  author =	{Chen, Chun-Hung and Hong, Liu and Kantor, Paul B. and Morton, David P. and Pichitlamken, Juta and Seeger, Matthias},
  title =	{{09181 Working Group on Hybridization between R\&S, DoE and Optimization}},
  booktitle =	{Sampling-based Optimization in the Presence of Uncertainty},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9181},
  editor =	{J\"{u}rgen Branke and Barry L. Nelson and Warren Buckler Powell and Thomas J. Santner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09181.3},
  URN =		{urn:nbn:de:0030-drops-21172},
  doi =		{10.4230/DagSemProc.09181.3},
  annote =	{Keywords: }
}
  • Refine by Author
  • 1 Chauhan, Himanshu
  • 1 Chen, Chun-Hung
  • 1 Esperet, Louis
  • 1 Fill, James Allen
  • 1 Garg, Vijay K.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Sorting and searching
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Landau-Kolmogorov inequality
  • 1 Property testing
  • 1 Quicksort
  • 1 asymptotic bounds
  • 1 concurrency
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2009
  • 1 2016
  • 1 2018
  • 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