Browsing by Author "Chiu, Well Y."

Now showing 1 - 2 of 2

A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
(2014-10-01)
Chiu, Well Y.
;
Chen, Chiuyuan
;
Tsai, Shih-Yu
;
應用數學系
;
Department of Applied Mathematics
A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. (C) 2014 Elsevier B.V. All rights reserved.
The Garden Hose Complexity for the Equality Function
(2014-01-01)
Chiu, Well Y.
;
Szegedy, Mario
;
Wang, Chengu
;
Xu, Yixin
;
應用數學系
The garden hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman [BFSS13] to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of O. Margalit and A. Matsliah [MM12] with the help of a new approach and of our handmade simulated annealing based solver. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of garden hose permutation groups. Then, exploiting this new concept, we get even further, although several interesting open problems remain.