Thesis (M. Phil.)--University of Hong Kong, 2002. / Includes bibliographical references (leaves 53-56).

published_or_final_version / Physics / Master / Master of Philosophy

Many computational problems involve massive data. A reasonable solution to those problems should be able to store and process the data in a effective manner. In this thesis, we study sparse representation of data streams and metric spaces, which allows for fast and private computation of heavy hitters from distributed streams, and approximate distance queries between points in a metric space. Specifically, we consider application scenarios where an untrusted aggregator wishes to continually monitor the heavy-hitters across a set of distributed streams. Since each stream can contain sensitive data, such as the purchase history of customers, we wish to guarantee the privacy of each stream, while allowing the untrusted aggregator to accurately detect the heavy hitters and their approximate frequencies. Our protocols are scalable in settings where the volume of streaming data is large, since we guarantee low memory usage and processing overhead by each data source, and low communication overhead between the data sources and the aggregator. We also study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k; t)-VFTS or simply k-VFTS), if for any subset S _ X with |Sj|≤k, it holds that dHnS(x; y) ≤ t ∙d(x; y), for any pair of x, y ∈ X \ S. For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. We also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m ≥2n, we can reduce the hop-diameter of the above k-VFTS to O(α(m; n)) by adding O(km) edges, where α is a functional inverse of the Ackermann's function. In addition, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k^2n) edges and maximum degree O(k^2). / published_or_final_version / Computer Science / Master / Master of Philosophy

As the social networking applications become popular and have attracted more and more attention, it becomes possible (or easier) to mine information networks of a large group of people, for instance the spread of viruses, products and innovations. Researchers are also benefited from these sources, as they help to study further about the human behaviors in a social networking environment. In this thesis, we study how the opinions cascade via social links and also the sparse representation of large data sets caused by the fast growing information networks. Consider an instance of advertising products on an information network, where the objective for an advertiser is to choose a set of initially active nodes, subject to some budget constraints such that the expected number of active nodes over time is maximized. In this work, the non-progressive case where active nodes could become inactive in subsequent time steps, was considered. This setting is interesting, for people have no reason to keep using a product forever, especially when a majority of his neighbors have given it up. Another setting is the users' susceptibilities to the new behavior won't change once they are chosen initially. This is di_erent from the previous works, and we think it is also interesting. Our main result is that with a specified budget, an advertiser can achieve 1/2 -approximation on maximizing the number of active nodes over a certain period of time, and (1 - 1/e)-approximation in expectation with a randomized algorithm. In our model, users' opinions are updated according to a weighted averaging scheme, which usually leads to the consensus. When this happens, the expected influence over a long time period is dominated by the consensus value. Hence, it is interesting to study when and how the consensus will be achieved. We study the convergence time required to achieve consensus. In particular, we considered the case when the underlying network is dynamic, and gave conclusions for different averaging models. Both our analysis and experiments show that dynamic networks exhibit fast convergence behavior, even under very mild connectivity assumptions. In this work, we also studied how to maintain the pairwise distances for a large group of users, when the distances form a doubling metric space. Motivated by Elkin and Solomon's construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n) ． w(MST)), we offer a simple alternative construction that is very intuitive and is based on the standard technique of net tree with cross edges. Indeed, our approach can be readily applied to our previous construction of k-fault tolerant spanners (ICALP 2012) to achieve k-fault tolerance, maximum degree O(K^2), hop-diameter O(log n) and lightness O(K^3 log n). / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Let B(H) denote the C^*-algebra of all bounded linear operators on a complex Hilbert space H. For A ∈ B(H) and c = 〖(c1, . . . , cn)〗^t ∈ C^n with n being a positive integer such that n ≤ dim H, the c-numerical range and c-numerical radius of A are defined by W_e (A)= {∑_(i=1)^n▒c_i 〈〖Ax〗_i, x_i 〉 : {x_1, …, x_n } is an orthonormal set in H} and W_C (A)={|z| :z ∈W_(c ) (A)} respectively. When c = 〖(1, 0, . . . , 0)〗^t, Wc(A) reduces to the classical numerical range W(A). Preserver problems concern the characterization of maps between spaces of bounded linear operators that leave invariant certain functions, subsets, or relations etc. In this thesis, several preserver problems related to the numerical range or its generalizations were studied. For A ∈ B(H), the diameter of its numerical range is d_w(A) = sup{|a - b| : a, b ∈ W(A)}. The first result in this thesis was a characterization of linear surjections on B(H) preserving the diameter of the numerical range, i.e., linear surjections T : B(H) → B(H) satisfying d_w(T(A)) =d_w(A) for all A ∈ B(H) were characterized. Let Mn be the set of n × n complex matrices and Tn the set of upper triangular matrices in Mn. Suppose c = 〖(c1, . . . , cn)〗^t ∈ R^n. When wc(·) is a norm on Mn, mappings T on Mn (or Tn) satisfying wc(T(A) - T(B)) = wc(A - B) for all A,B were characterized. Let V be either B(H) or the set of all self-adjoint operators in B(H). Suppose V^n is the set of n-tuples of bounded operators  = (A1, . . . ,An), with each Ai ∈ V. The joint numerical radius of  is defined by w(Â) = sup{||(⟨A1x, x⟩, . . . , ⟨Anx, x⟩)∥ : x ∈ H, ∥x∥ = 1}, where ∥ · ∥ is the usual Euclidean norm on F^n with F = C or R. When H is infinite-dimensional, surjective linear maps T : V^n→V^n satisfying w(T(Â)) = w(Â) for all  ∈ V^n were characterized. Another generalization of the numerical range is the Davis-Wielandt shell. For A ∈ B(H), its Davis-Wielandt shell is DW(A) = {(⟨Ax, x⟩, ⟨Ax, Ax⟩): x ∈ H and∥x∥= 1}. Define the Davis-Wielandt radius of A by dw(A) = sup{(√(|⟨Ax, x⟩ |^2 + |⟨Ax, Ax⟩ |^2) : x ∈ H and ∥x∥= 1}. Its properties and relations with normaloid matrices were investigated. Surjective mappings T on B(H) satisfying dw(T(A) - T(B))= dw(A - B) for all A,B ∈ B(H) were also characterized. A characterization of real linear surjective isometries on B(H) by Dang was used to prove the preserver result about the Davis-Wielandt radius. The result of Dang is proved by advanced techniques and is applicable on a more general setting than B(H). In this thesis, the characterization of surjective real linear isometries on B(H) was re-proved using elementary operator theory techniques. / published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

Not available / text

Not available / text

published_or_final_version / abstract / toc / Mathematics / Master / Master of Philosophy

published_or_final_version / abstract / toc / Mathematics / Master / Master of Philosophy

published_or_final_version / Mathematics / Master / Master of Philosophy