30972999
Perfect Power Testing
Bach and Sorenson present two algorithms for testing whether a number n is a perfect power, with average running time O(log2 n) under the assumption that n is chosen uniformly from an interval of length at least (log n)3 log log log n. We modify their algorithms to reduce the interval to polynomial size.
2899394
An Improved Fixed-Parameter Algorithm for Vertex Cover
The Vertex Cover problem asks, for input consisting of a graph G on n vertices, and a positive integer k, whether there is a set of k vertices such that every edge of G is incident with at least one of these vertices. We give an algorithm for this problem that runs in time O(kn + (1.324718)kk2). In particular, this gives an O((1.324718)nn2) algorithm to find the minimum vertex cover in the graph.
8028128
Maximal Sets of Integers with Distinct Divisors
A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every $c>1$, a largest subset of $[N,cN]$ with the distinct divisor property has cardinality $\sim \delta(c)N$, for some constant $\delta(c)>0$. They conjectured that $\delta(c)\sim c/2$ as $c \to \infty$. We prove their conjecture. In fact we show that there exist positive absolute constants $D_1,D_2$ such that $D_1\le c^{\beta}(c/2-\delta(c))\le D_2$ where $\beta = \log 2/\log (3/2)$.
1445498
Density of Carmichael numbers with three prime factors
We get an upper bound of O(x 5/14+o(1) ) on the number of Carmichael numbers ≤ x with exactly three prime factors.
38155628
Tight Bounds for Finding Degrees from the Adjacency Matrix
King and Smith-Thomas[5] have shown that to find a sink (a vertex with outdegree 0 and indegree n−1) in an n vertex directed graph, 3n-⌊log n⌋-3 probes to its adjacency matrix are necessary and sufficient in the worst case. We first generalize this result to show that for any integer k between 0 and n−1, 
 
 
to find a vertex of outdegree k in a simple n vertex directed graph, Θ(n(n−k)) probes to its adjacency matrix are necessary and sufficient in the worst case, and 
 
 
to find a vertex of degree k in an n vertex undirected graph, Θ(n2) probes to its adjacency matrix are necessary and sufficient in the worst case.
27625864
Path Balance Heuristic for Self-Adjusting Binary Search Trees
In (A. Subramanian, An Explanation of Splaying, Proceedings of the 14th Foundations of Software Technology and Theoretical Computer Science, LNCS Springer Verlag 880 354–365), D. Sleator suggested the following heuristic for self adjusting binary search trees: Every time an access is made, restructure the entire path from the root of the search tree to the accessed node into a balanced binary search tree on those nodes, and place all other subtrees rooted at the children of the nodes in the access path in their proper positions. We show that the method has an O(log n log log n/ log log log n) amortized complexity.
28520158
Blended Learning - A Trend in e-Learning
A method, apparatus, and article of manufacture for a computer-implemented random reliability engine for computer-implemented dimension reduction using association rules for data mining application. The data mining is performed by the computer to retrieve data from a data store stored on a data storage device coupled to the computer. The data store has records that have multiple attributes. The multiple attributes of a table are clustered to produce a plurality of sets of attributes. Each set of attributes is clustered to obtain data mining attributes.
9665741
Soft-output detection of CPM signals in frequency flat, Rayleigh fading channels
Symbol-by-symbol detection algorithms are useful in systems in which soft-decision metrics are important, e.g., systems with interleaved coded modulation. A soft-output algorithm for the detection of continuous phase modulated (CPM) signals transmitted over frequency flat, Rayleigh fading channels is developed. Since the optimum detector is computationally too complex for any practical implementation, some suboptimal detectors which give near optimal performance are proposed. Some theoretical approximations for the performance of the interleaved coded system are given. The performance of the soft-output algorithms is also extensively characterized by means of Monte-Carlo simulations.