Local noncuppability in R/M

Given any [c], [a], [d] xxxxxxxxR/M such that [d] ≤ [a] ≤ [c], [a] is locally noncuppable between [c] and [d] if [d] < [a] ≤ [c] and [a] ∨ [b] < [c] for any [b] xxxxxxxxR/M such that [d] ≤ [b] < [c]. It will be shown that given any nonzero [c] xxxxxxxxR/M, there are [a], [d] xxxxxxxxR/M such that [d] < [a] ≤ [c] and [a] is locally noncuppable between [c] and [d].     

Evolutionary Trees and Ordinal Assertions

Sequence data for a group of species is often summarized by a distance matrix M where M[s,t] is the dissimilarity between the sequences of species s and t . An ordinal assertion is a statement of the form ``species a and b are as similar as species c and d ' and is supported by distance matrix M if M[a,b] ≤ M[c,d] . Recent preliminary research suggests that ordinal assertions can be used to reconstruct the evolutionary history of a group of species effectively. However, further research on the mathematical and algorithmic properties of ordinal assertions is needed to facilitate the development and assessment of inference methods that utilize ordinal assertions for reconstructing evolutionary histories. A (weighted ) ordinal representation of a distance matrix M is a (weighted) phylogeny T such that, for all species a , b , c , and d labeling T , d _T (a,b) ≤ d _T (c,d) if and only if M[a,b] ≤ M[c,d], where d _T is the weighted path length when T is weighted, otherwise d _T is the unweighted path length. Hence, an ordinal representation of M is a phylogeny that supports the same ordinal assertions supported by M , and so is the focus of our examination of the mathematical and algorithmic properties of ordinal assertions. As it turns out, ordinal representations are rich in structure. In this paper several results on weighted and unweighted ordinal representations are presented: — The unweighted ordinal representation of a distance matrix is unique. This generalizes the well-known result that no two phylogenies share the same distance matrix [10], [21]. — The unweighted ordinal representation of a distance matrix can be found in O(n ² log ² (n)) time. The algorithm presented improves upon an O(n ³ ) algorithm by Kannan and Warnow [13] that finds binary unweighted ordinal representations of distance matrices. — Under certain conditions, weighted ordinal representations can be found in polynomial time. Received May 11, 1997; revised March 13, 1998.     

Extending the cooper minimal pair theorem

In the study of cappable and noncappable properties of the recursively enumerable(r.e.)degrees.Lempp suggested a conjecture which asserts that for all r.e.degrees and b,if a ≮b then there exists an r.e.degree c such that c≤a and c≮b and c is cappable.We shall prove in this paper that this conjecture holds under the condition that a is high.Working below a high r.e.degree h,we show that for any r.e.degree b with h≮b,there exist r.e.degrees a0 and a1 and such that a0,a1≮b,a0,a1≤h,and a0 and a1 from a minimal pair.     

Approximability of Sparse Integer Programs

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d are nonnegative.) For any k≥2 and ε>0, if P≠NP this ratio cannot be improved to k−1−ε, and under the unique games conjecture this ratio cannot be improved to k−ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx:Ax≤b,0≤x≤d} where A has at most k nonzeroes per column, we give a (2k ²+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A _ij is small compared to b _i . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.     

Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

A Criterion for Extractability of Mutual Information for a Triple of Strings

We say that the mutual information of a triple of binary strings a, b, c can be extracted if there exists a string d such that a, b, and c are independent given d, and d is simple conditional to each of the strings a, b, and c. It is proved that the mutual information between a, b, and c can be extracted if and only if the values of the conditional mutual informations I(a : b|c), I(a : c|b), and I(b : c|a) are negligible. The proof employs a non-Shannon-type information inequality (a generalization of the recently discovered Zhang–Yeung inequality).     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

Improved Generation of Minimal Addition Chains

An addition chain for a natural number n is a sequence 1=a ₀<a ₁< . . . <a _r =n of numbers such that for each 0<i≤r, a _i =a _j +a _k for some 0≤k≤j<i. An improvement by a factor of 2 in the generation of all minimal (or one) addition chains is achieved by finding sufficient conditions for star steps, computing what we will call nonstar lower bound in a minimal addition and omitting the sorting step.     

Synthesis of space optimal systolic arrays for band matrix-vector multiplication

In this paper, we consider the implementation of a product c=A b, where A is N ₁×N ₃ band matrix with bandwidth ω and b is a vector of size N ₃×1, on bidirectional and unidirectional linear systolic arrays (BLSA and ULSA, respectively). We distinguish the cases when the matrix bandwidth ω is 1≤ω≤N ₃ and N ₃≤ω≤N ₁+N ₃−1. A modification of the systolic array synthesis procedure based on data dependencies and space-time transformations of data dependency graph is proposed. The modification enables obtaining both BLSA and ULSA with an optimal number of processing elements (PEs) regardless of the matrix bandwidth. The execution time of the synthesized arrays has been minimized. We derive explicit formulas for the synthesis of these arrays. The performances of the designed arrays are discussed and compared to the performances of the arrays obtained by the standard design procedure.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

The perception and measurement of contrast: the influence of gaps between display elements

Abstract

The influence of the luminance of the gap between display elements of flat panel displays (FPDs) on perceived contrast was investigated. Twelve black-on-white FPDs, differing systematically with respect to foreground, background, and gap luminance, were simulated in an experiment. Twelve subjects rated each simulation on u scale, measuring several aspects of image quality, and performed a search task with each simulated FPD. The aims of the research were (a) to validate and assess the reliability of the rating scale items concerning contrast; (b) to relate subjective to objective measures; (c) to find out if ratings improve if raters perform a task with the rated objects; and (d) to evaluate a metric for expressing FPD contrast that we recently proposed. It is concluded that (a) the scale items are reliable if the rated objects vary on the property under concern; several items consistently measured subjective contrast; (b) subjective and objective contrast were strongly related in a linear fashion; (c) without actually using the stimuli in a working task, raters were capable of producing reliable and valid ratings; and (d) the proposed effective luminance modulation (M_r ) metric did, but ordinary luminance modulation did not correspond to perceived contrast. Based on this latter finding we recommend that an alternative contrast measurement procedure based on the (M_r ) metric is further validated for wide gaps and negative polarity displays.     

Maintenance of a Piercing Set for Intervals with Applications

   Abstract. We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c( S) log |S|), where c (S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1+ɛ)c (S), for 0 < ɛ ≤ 1 , in

Approximation algorithms for DNF under distributions with limited independence

In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a Boolean formula with some restricted form of DNF under distributions with limited independence between random variables. LetF be a DNF formula onn variables withm clauses in which each literal appears at most once. We prove that ifD is [k logm]-wise independent, then |Pr _D [F]-Pr _U [F]| ≤ , whereU denotes the uniform distribution and Pr _D [F] denotes the probability thatF is satisfied by a truth assignment chosen according to distributionD (similarly for Pr _U [F]). Using the result, we also derive the following: For formulas satisfying the restriction described above and for any constantc, there exists a probability distributionD, with size polynomial in logn andm, such that |Pr _D [F] - Pr _U [F]| ≤c holds.     

Isolation, Infima and Diamond Embeddings

In (1993, Annals of Pure and Applied Logic, 62, 207–263),Kaddah pointed out that there are two d.c.e. degrees a,b forminga minimal pair in the d.c.e. degrees, but not in the degrees. Kaddah's; result shows thatLachlan's; theorem, stating that the infima of two c.e. degreesin the c.e. degrees and in the degrees coincide, cannot be generalized to the d.c.e. degrees. In this article, we apply Kaddah's; idea to show that thereare two d.c.e. degrees c,d such that c cups d to 0', and capsd to 0 in the d.c.e. degrees, but not in the degrees. As a consequence, the diamond embedding{0,c,d,0'} is different from the one first constructed by Downeyin 1989 in [5]. To obtain this, we will construct c.e. degreesa,b, d.c.e. degrees c > a,d > b and a non-zero -c.e. degreee c,d such that (i) a,b form a minimal pair, (ii) a isolatesc, and (iii) b isolates d. From this, we can have that c,d forma minimal pair in the d.c.e. degrees, and Kaddah's; result followsimmediately. In our construction, we apply Kaddah's; originalidea to make e below both c and d. Our construction allows usto separate the minimal pair argument (ab = 0), the splittingof 0' (cd = 0'), and the non-minimal pair of c,d (in the degrees), into several parts, to avoiddirect conflicts that could be involved if only c,d and e areconstructed. We also point out that our construction allowsus to make a,b above (and hence c,d) high.     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

A sufficient condition for a graph to be an (a,b, k)-critical graph

Let G be a graph, and let a, b, k be integers with 0≤a≤b, k≥0. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a≤d _F (x)≤b for each x∈V(G). Then a graph G is called an (a, b, k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a, b]-factor. In this article, a sufficient condition is given, which is a neighborhood condition for a graph G to be an (a, b, k)-critical graph.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.