16 Search Results for "Liu, Chih-Hung"

Document
DOI: 10.4230/LIPIcs.SEA.2023.8
Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Authors: Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.
Cite as

Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
  author =	{Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8},
  URN =		{urn:nbn:de:0030-drops-183585},
  doi =		{10.4230/LIPIcs.SEA.2023.8},
  annote =	{Keywords: sorting, algorithms, randomization, experimentation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.37
Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Authors: Shengyu Huang, Chih-Hung Liu, and Daniel Rutschmann

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log 1/Q), Θ(n log k/Q) and Θ(n log n/Q) comparisons, respectively, to achieve success probability 1-Q [Uriel Feige et al., 1994]. Considering the increasing complexity of modern computing, it is of great interest to develop approximation algorithms that enable a trade-off between the solution quality and the number of comparisons. In particular, approximation algorithms would even be able to attain a sublinear number of comparisons. Very recently, Leucci and Liu [Stefano Leucci and Chih-Hung Liu, 2022] proved that the approximate minimum selection problem, which covers the case that k ≤ nε, requires expected Θ(ε^{-1} log 1/Q) comparisons, but the general case, i.e., for nε < k ≤ n/2, is still open. We develop a randomized algorithm that performs expected O(k/n ε^{-2} log 1/Q) comparisons to achieve success probability at least 1-Q. For k = n ε, the number of comparisons is O(ε^{-1} log 1/Q), matching Leucci and Liu’s result [Stefano Leucci and Chih-Hung Liu, 2022], whereas for k = n/2 (i.e., approximating the median), the number of comparisons is O(ε^{-2} log 1/Q). We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(min{n, k/n ε^{-2} log 1/Q}) comparisons. As long as n is large enough, i.e., when n = Ω(k/n ε^{-2} log 1/Q), our lower bound demonstrates the optimality of our algorithm, which covers the possible range of attaining a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε^{-2}) comparisons, matching the best possible approximation algorithm in the absence of computation faults. In contrast, for the exact selection problem, the expected number of comparisons is Θ(n log k) with faults versus Θ(n) without faults. Our results also indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k = n/2, Q = 1/n and ε = n^{-α} for α ∈ (0, 1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^{2α}).
Cite as

Shengyu Huang, Chih-Hung Liu, and Daniel Rutschmann. Approximate Selection with Unreliable Comparisons in Optimal Expected Time. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 37:1-37:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2023.37,
  author =	{Huang, Shengyu and Liu, Chih-Hung and Rutschmann, Daniel},
  title =	{{Approximate Selection with Unreliable Comparisons in Optimal Expected Time}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.37},
  URN =		{urn:nbn:de:0030-drops-176898},
  doi =		{10.4230/LIPIcs.STACS.2023.37},
  annote =	{Keywords: Approximate Selection, Unreliable Comparisons, Independent Faults}
}
Document
DOI: 10.4230/LITES.8.1.1
Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness

Authors: Martin Knoche, Stefan Hörmann, and Gerhard Rigoll

Published in: LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1

Abstract
Many face recognition approaches expect the input images to have similar image resolution. However, in real-world applications, the image resolution varies due to different image capture mechanisms or sources, affecting the performance of face recognition systems. This work first analyzes the image resolution susceptibility of modern face recognition. Face verification on the very popular LFW dataset drops from 99.23% accuracy to almost 55% when image dimensions of both images are reduced to arguable very poor resolution. With cross-resolution image pairs (one HR and one LR image), face verification accuracy is even worse. This characteristic is investigated more in-depth by analyzing the feature distances utilized for face verification. To increase the robustness, we propose two training strategies applied to a state-of-the-art face recognition model: 1) Training with 50% low resolution images within each batch and 2) using the cosine distance loss between high and low resolution features in a siamese network structure. Both methods significantly boost face verification accuracy for matching training and testing image resolutions. Training a network with different resolutions simultaneously instead of adding only one specific low resolution showed improvements across all resolutions and made a single model applicable to unknown resolutions. However, models trained for one particular low resolution perform better when using the exact resolution for testing. We improve the face verification accuracy from 96.86% to 97.72% on the popular LFW database with uniformly distributed image dimensions between 112 × 112 px and 5 × 5 px. Our approaches improve face verification accuracy even more from 77.56% to 87.17% for distributions focusing on lower images resolutions. Lastly, we propose specific image dimension sets focusing on high, mid, and low resolution for five well-known datasets to benchmark face verification accuracy in cross-resolution scenarios.
Cite as

Martin Knoche, Stefan Hörmann, and Gerhard Rigoll. Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness. In LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1, pp. 01:1-01:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{knoche_et_al:LITES.8.1.1,
  author =	{Knoche, Martin and H\"{o}rmann, Stefan and Rigoll, Gerhard},
  title =	{{Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness}},
  booktitle =	{LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision},
  pages =	{01:1--01:20},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Knoche, Martin and H\"{o}rmann, Stefan and Rigoll, Gerhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.1.1},
  doi =		{10.4230/LITES.8.1.1},
  annote =	{Keywords: recognition, resolution, cross, face, identification}
}
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.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.ITCS.2022.100
Beating Classical Impossibility of Position Verification

Authors: Jiahui Liu, Qipeng Liu, and Luowen Qian

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Chandran et al. (SIAM J. Comput. '14) formally introduced the cryptographic task of position verification, where they also showed that it cannot be achieved by classical protocols. In this work, we initiate the study of position verification protocols with classical verifiers. We identify that proofs of quantumness (and thus computational assumptions) are necessary for such position verification protocols. For the other direction, we adapt the proof of quantumness protocol by Brakerski et al. (FOCS '18) to instantiate such a position verification protocol. As a result, we achieve classically verifiable position verification assuming the quantum hardness of Learning with Errors. Along the way, we develop the notion of 1-of-2 non-local soundness for a natural non-local game for 1-of-2 puzzles, first introduced by Radian and Sattath (AFT '19), which can be viewed as a computational unclonability property. We show that 1-of-2 non-local soundness follows from the standard 2-of-2 soundness (and therefore the adaptive hardcore bit property), which could be of independent interest.
Cite as

Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating Classical Impossibility of Position Verification. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 100:1-100:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2022.100,
  author =	{Liu, Jiahui and Liu, Qipeng and Qian, Luowen},
  title =	{{Beating Classical Impossibility of Position Verification}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{100:1--100:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.100},
  URN =		{urn:nbn:de:0030-drops-156963},
  doi =		{10.4230/LIPIcs.ITCS.2022.100},
  annote =	{Keywords: cryptographic protocol, position verification, quantum cryptography, proof of quantumness, non-locality}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.64
Dual-Mode Greedy Algorithms Can Save Energy

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti

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

Abstract
In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti. Dual-Mode Greedy Algorithms Can Save Energy. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 64:1-64:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ISAAC.2019.64,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo and Proietti, Guido},
  title =	{{Dual-Mode Greedy Algorithms Can Save Energy}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{64:1--64:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.64},
  URN =		{urn:nbn:de:0030-drops-115604},
  doi =		{10.4230/LIPIcs.ISAAC.2019.64},
  annote =	{Keywords: matroids, p-extendible systems, greedy algorithm, approximation algorithms, high-low energy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.49
Optimal Sorting with Persistent Comparison Errors

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated (Braverman and Mossel, SODA'08). Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Omega(log n) and Omega(n), respectively, regardless of its running time. In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds. In order to achieve this optimality result, we solve two sub-problems in the persistent error comparisons model, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Sorting with Persistent Comparison Errors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 49:1-49:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ESA.2019.49,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo},
  title =	{{Optimal Sorting with Persistent Comparison Errors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.49},
  URN =		{urn:nbn:de:0030-drops-111706},
  doi =		{10.4230/LIPIcs.ESA.2019.49},
  annote =	{Keywords: approximate sorting, comparison errors, persistent errors}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.70
Resilient Dictionaries for Randomly Unreliable Memory

Authors: Stefano Leucci, Chih-Hung Liu, and Simon Meierhans

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory word is randomly unreliable with a probability p < 1/2, and the locations of the unreliable words are unknown to the algorithm. An adversary observes the whole memory and can, at any time, arbitrarily corrupt (i.e., modify) the contents of one or more unreliable words. Our dictionary has capacity n, stores N<n keys in the optimal O(N) amount of space, supports insertions and deletions in O(log n) amortized time, and allows to search for a key in O(log n) worst-case time. With a global probability of at least 1-1/n, all possible search operations are guaranteed to return the correct answer w.r.t. the set of uncorrupted keys. The closest related results are the ones of Finocchi et al. [Irene Finocchi et al., 2009] and Brodal et al. [Brodal et al., 2007] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound delta on the number of corruptions is known in advance, all dictionary operations can be implemented in Theta(log n + delta) amortized time, thus trading resiliency for speed as soon as delta = omega(log n). Our construction does not need to know the value of delta in advance and remains fast and effective even when up to a constant fraction of the available memory is corrupted. Our techniques can be immediately extended to implement other data types (e.g., associative containers and priority queues), which can then be used as a building block in the design of other resilient algorithms. For example, we are able to solve the resilient sorting problem in our model using O(n log n) time.
Cite as

Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient Dictionaries for Randomly Unreliable Memory. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 70:1-70:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leucci_et_al:LIPIcs.ESA.2019.70,
  author =	{Leucci, Stefano and Liu, Chih-Hung and Meierhans, Simon},
  title =	{{Resilient Dictionaries for Randomly Unreliable Memory}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.70},
  URN =		{urn:nbn:de:0030-drops-111911},
  doi =		{10.4230/LIPIcs.ESA.2019.70},
  annote =	{Keywords: resilient dictionary, unreliable memory, faulty RAM}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.58
A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon

Authors: Chih-Hung Liu

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega(n+m log m), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O((n+m)log (n+m)) and O(n+m log m log^2n) time, which are optimal for m=Omega(n) and m=O(n/(log^3n)), respectively. In this paper, we give a construction algorithm with O(n+m(log m+log^2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O(log n) time, then the construction time will become the optimal O(n+m log m). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O(log n) time.
Cite as

Chih-Hung Liu. A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 58:1-58:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.SoCG.2018.58,
  author =	{Liu, Chih-Hung},
  title =	{{A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.58},
  URN =		{urn:nbn:de:0030-drops-87717},
  doi =		{10.4230/LIPIcs.SoCG.2018.58},
  annote =	{Keywords: Simple polygons, Voronoi diagrams, Geodesic distance}
}
Document
DOI: 10.4230/LITES-v005-i001-a002
Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions

Authors: Konstantinos Bletsas, Neil C. Audsley, Wen-Hung Huang, Jian-Jia Chen, and Geoffrey Nelissen

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
The purpose of this article is to (i) highlight the flaws in three previously published works [Audsley, 2004a; Audsley, 2004b; Bletsas, 2005] on the worst-case response time analysis for tasks with self-suspensions and (ii) provide straightforward fixes for those flaws, hence rendering the analysis safe.
Cite as

Konstantinos Bletsas, Neil C. Audsley, Wen-Hung Huang, Jian-Jia Chen, and Geoffrey Nelissen. Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 02:1-02:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bletsas_et_al:LITES-v005-i001-a002,
  author =	{Bletsas, Konstantinos and Audsley, Neil C. and Huang, Wen-Hung and Chen, Jian-Jia and Nelissen, Geoffrey},
  title =	{{Errata for Three Papers (2004-05) on Fixed-Priority Scheduling with Self-Suspensions}},
  booktitle =	{LITES, Volume 5, Issue 1 (2018)},
  pages =	{02:1--02:20},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  editor =	{Bletsas, Konstantinos and Audsley, Neil C. and Huang, Wen-Hung and Chen, Jian-Jia and Nelissen, Geoffrey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a002},
  doi =		{10.4230/LITES-v005-i001-a002},
  annote =	{Keywords: real-time, scheduling, self-suspension, worst-case response time analysis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.36
Optimal Dislocation with Persistent Errors in Subquadratic Time

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We study the problem of sorting N elements in presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability p, but repeating the same comparison gives always the same result. The best known algorithms for this problem have running time O(N^2) and achieve an optimal maximum dislocation of O(log N) for constant error probability. Note that no algorithm can achieve dislocation o(log N), regardless of its running time. In this work we present the first subquadratic time algorithm with optimal maximum dislocation: Our algorithm runs in tilde{O}(N^{3/2}) time and guarantees O(log N) maximum dislocation with high probability. Though the first version of our algorithm is randomized, it can be derandomized by extracting the necessary random bits from the results of the comparisons (errors).
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Dislocation with Persistent Errors in Subquadratic Time. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 36:1-36:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.STACS.2018.36,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo},
  title =	{{Optimal Dislocation with Persistent Errors in Subquadratic Time}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.36},
  URN =		{urn:nbn:de:0030-drops-85266},
  doi =		{10.4230/LIPIcs.STACS.2018.36},
  annote =	{Keywords: sorting, recurrent comparison errors, maximum dislocation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.38
Sorting with Recurrent Comparison Errors

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n^2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with Recurrent Comparison Errors. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 38:1-38:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ISAAC.2017.38,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo},
  title =	{{Sorting with Recurrent Comparison Errors}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{38:1--38:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.38},
  URN =		{urn:nbn:de:0030-drops-82652},
  doi =		{10.4230/LIPIcs.ISAAC.2017.38},
  annote =	{Keywords: sorting, recurrent comparison error, maximum and total dislocation}
}
Document
DOI: 10.4230/LITES-v004-i001-a001
A Note on the Period Enforcer Algorithm for Self-Suspending Tasks

Authors: Jian-Jia Chen and Björn B. Brandenburg

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
The period enforcer algorithm for self-suspending real-time tasks is a technique for suppressing the "back-to-back" scheduling penalty associated with deferred execution. Originally proposed in 1991, the algorithm has attracted renewed interest in recent years. This note revisits the algorithm in the light of recent developments in the analysis of self-suspending tasks, carefully re-examines and explains its underlying assumptions and limitations, and points out three observations that have not been made in the literature to date: (i) period enforcement is not strictly superior (compared to the base case without enforcement) as it can cause deadline misses in self-suspending task sets that are schedulable without enforcement; (ii) to match the assumptions underlying the analysis of the period enforcer, a schedulability analysis of self-suspending tasks subject to period enforcement requires a task set  transformation for which no solution is known  in the general case, and which is subject to exponential time complexity (with current techniques) in the limited case of a single self-suspending task; and (iii) the period enforcer algorithm is incompatible with all existing analyses of suspension-based locking protocols, and can in fact cause ever-increasing suspension times until a deadline is missed.
Cite as

Jian-Jia Chen and Björn B. Brandenburg. A Note on the Period Enforcer Algorithm for Self-Suspending Tasks. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 01:1-01:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{chen_et_al:LITES-v004-i001-a001,
  author =	{Chen, Jian-Jia and Brandenburg, Bj\"{o}rn B.},
  title =	{{A Note on the Period Enforcer Algorithm for Self-Suspending Tasks}},
  booktitle =	{LITES, Volume 4, Issue 1 (2017)},
  pages =	{01:1--01:22},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  editor =	{Chen, Jian-Jia and Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a001},
  doi =		{10.4230/LITES-v004-i001-a001},
  annote =	{Keywords: Period Enforcer, Deferred Execution, Self-suspension, Blocking}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.21
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

Authors: Cecilia Bohler, Rolf Klein, and Chih-Hung Liu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.
Cite as

Cecilia Bohler, Rolf Klein, and Chih-Hung Liu. An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohler_et_al:LIPIcs.SoCG.2016.21,
  author =	{Bohler, Cecilia and Klein, Rolf and Liu, Chih-Hung},
  title =	{{An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.21},
  URN =		{urn:nbn:de:0030-drops-59135},
  doi =		{10.4230/LIPIcs.SoCG.2016.21},
  annote =	{Keywords: Order-k Voronoi Diagrams, Abstract Voronoi Diagrams, Randomized Geometric Algorithms}
}
Document
DOI: 10.4230/LITES-v002-i002-a001
From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation

Authors: Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens

Published in: LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2

Abstract
Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.
Cite as

Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens. From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation. In LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2, pp. 01:1-01:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{carle_et_al:LITES-v002-i002-a001,
  author =	{Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David},
  title =	{{From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation}},
  booktitle =	{LITES, Volume 2, Issue 2 (2015)},
  pages =	{01:1--01:30},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{2},
  editor =	{Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i002-a001},
  doi =		{10.4230/LITES-v002-i002-a001},
  annote =	{Keywords: Time-triggered, Off-line real-time scheduling, Temporal partitioning}
}
  • Refine by Author
  • 8 Liu, Chih-Hung
  • 5 Leucci, Stefano
  • 4 Geissmann, Barbara
  • 4 Penna, Paolo
  • 2 Chen, Jian-Jia
  • Show More...

  • Refine by Classification
  • 3 Computer systems organization → Real-time systems
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Software and its engineering → Real-time schedulability
  • 1 Computer systems organization
  • 1 Computer systems organization → Embedded systems
  • Show More...

  • Refine by Keyword
  • 3 sorting
  • 1 Abstract Voronoi Diagrams
  • 1 Approximate Selection
  • 1 Blocking
  • 1 Deferred Execution
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 3 2018
  • 3 2019
  • 3 2022
  • 2 2017
  • 2 2023
  • Show More...

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