9720635
Regular reals
Say that α is an n-strongly c. e. (n-strongly computably enumerable) real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n-strongly c. e. for some n. Let S be the set of all n-strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S ⊂ S ⊂ · · · ⊂ S ⊂ · · · ⊂ ⊂ Reg ⊂ CE. This gives a hierarchy of the c. e. reals. We also study the regularity of the d. c. e. reals.
1638130
Bounding computably enumerable degrees in the Ershov hierarchy
Nanyang Technol Univ, Sch Math & Phys Sci, Div Math Sci, Singapore 639798, Singapore. Chinese Acad Sci, Inst Software, Beijing 100080, Peoples R China. Natl Univ Singapore, Dept Math, Singapore 119260, Singapore.
7723209
1-Generic splittings of computably enumerable degrees
Say a set G⊆ω is 1-generic if for any e∈ω, there is a string σ⊂G such that {e}σ(e)↓ or ∀τ⊇σ({e}τ(e)↑). It is known that 0′ can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.
18609322
On the Quotient Structure of Computably Enumerable Degrees Modulo the Noncuppable Ideal
We show that minimal pairs exist in the quotient structure of $\mathcal{R}$ modulo the ideal of noncuppable degrees.
35293254
Quasi-complements of the cappable degrees
Say that a nonzero c. e. degree b is a quasi-complement of a c. e. degree a if a ∩ b = 0 and a ∪ b is high. It is well-known (due to Shore) that each cappable degree has a high quasi-complement. However, by the existence of the almost deep degrees, there are nonzero cappable degrees having no low quasi-complements. In this paper, we prove that any nonzero cappable degree has a low2 quasi-complement. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
1961392
Degrees of Weakly Computable Reals
This paper studies the degrees of weakly computable reals. It is shown that certain types of limit-recursive reals are Turing incomparable to all weakly computable reals except the recursive and complete ones. Furthermore, it is shown that an r.e. Turing degree is array-recursive iff every real in it is weakly computable.
5979296
A Lookahead Branch-and-Bound Algorithm for the Maximum Quartet Consistency Problem
A lookahead branch-and-bound algorithm (LBnB) is proposed for solving the Maximum Quartet Consistency (MQC) Problem where the input is a complete set of quartets on the taxa and the goal is to construct a phylogeny that satisfies the maximum number of given quartets. It integrates a number of previous efforts on exact algorithms, heuristics, and approximation algorithms for the NP-hard MQC problem, and a few improved search techniques, especially a lookahead scheme, to solve the problem optimally. The theoretical running time analysis of the LBnB algorithm is provided, and an extensive simulation study has been well designed to compare the algorithm to previous existing exact algorithms and a best heuristic Hypercleaning. The experimental results on both synthetic and real datasets show that LBnB outperformed other exact algorithms, and it was competitive to Hypercleaning on many datasets.
17031172
Predictive buffer control in delivering remotely stored video using proxy servers
We study the problem of using proxy servers to stream video stored at a geographically separate location. The separation of the server and the storage introduces a non-negligible delay in retrieving video frames in real time. We assume an additive-increase/multiplicative-decrease transport protocol to support the streaming process and develop an effective scheme to achieve consistent, high streaming quality. The heart of the scheme is the control of buffer occupancy at the proxy server. We model the buffer as a bilinear dynamical system disturbed by a point process with stochastic state-dependent intensity. We first develop a buffer controller that does not exploit this model. Then, using the buffer model, we construct a second controller based on an optimal-control analysis for the case without retrieval delay. Extending these two controllers, we subsequently synthesize two controllers based on prediction of future system states using the model, taking into account both the delay and the state-dependent disturbance intensity. Our empirical study illustrates the effectiveness of the streaming scheme. We further find that the controllers exploiting the buffer model demonstrate performance significantly superior to that of the model-free controller in overcoming the adverse impact of the retrieval delay. We also conduct limited experiments to study the impact of variable retrieval delays.
13757062
Faster solution to the maximum quartet consistency problem with constraint programming
Evolution is an important sub-area of study in biological science, whereby the evolutionary history, or phylogeny, would shed light on the genetic linkage and the functional correlation for the species under consideration. Many kinds of species data can be deployed for the task and many phylogeny reconstruction methods have been examined in the literature. A quartet approach is to build a local phylogeny for every 4 species, which is called a quartet for these 4 species, and then to assemble a phylogeny for the whole set of species satisfying the topological constraints imposed by these quartets built. In practice, those predicted quartets might not agree each other and the optimization problem, the well-known Maximum Quartet Consistency (MQC) problem, is to construct a phylogeny to satisfy a maximum number of the predicted quartets. An equivalent representation for the MQC problem through searching for a certain ultrametric matrix via Answer Set Programming has recently been proposed. This paper follows the approach and presents a number of optimization techniques to speed up the searching process. The experimental results on both the simulated and real datasets suggest that the new representation combined with Constraint Programming presents a unique perspective to the MQC problem.
7109499
Statistical learning for effective visual information retrieval
For effective retrieval of visual information, statistical learning plays a pivotal role. Statistical learning in such a context faces at least two major mathematical challenges: scarcity of training data, and imbalance of training classes. We present these challenges and outline our methods for addressing them: active learning, recursive subspace co-training, adaptive dimensionality reduction, class-boundary alignment, and quasi-bagging.
858614
Formulating context-dependent similarity functions
Tasks of information retrieval depend on a good distance function for measuring similarity between data instances. The most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. In this paper, we present a novel method, which learns a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. We show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. In addition to using the kernel trick, we propose two algorithms to further enhance efficiency and effectiveness of function learning. For efficiency, we propose a SMO-like solver to achieve O(N2) learning performance. For effectiveness, we propose using unsupervised learning in an innovative way to address the challenge of lack of labeled data (contextual information). Theoretically, we substantiate that our method is both sound and optimal. Empirically, we demonstrate that our method is effective and useful.