How to Recognize Zero

An elementary point is a point in complexnspace, which is an isolated, nonsingular solution ofnequations innvariables, each equation being either of the formp = 0, wherepis a polynomial in [x₁,…,x_n], or of the formx_j − e^x_i = 0. An elementary number is the polynomial image of an elementary point. In this article a semi algorithm is given to decide whether or not a given elementary number is zero. It is proved that this semi algorithm is an algorithm, i.e. that it always terminates, unless it is given a problem containing a counterexample to Schanuel’s conjecture.     

Function Field Sieve Method for Discrete Logarithms over Finite Fields

We present a function field sieve method for discrete logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields F_pⁿ, where p⁶n.     

Undecidable statements and random graphs

In this paper we will consider random graphsG _n,p ,p=n ^– a rational number between 0 and 1. We show that there is no decision procedure that separates those first order statements that hold almost always inG _n,p from those whose negation holds almost always.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Approximation Algorithms for Minimum K -Cut

Let G=(V,E) be a complete undirected graph, with node set V={v ₁ , . . ., v _n } and edge set E . The edges (v _i ,v _j ) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k _i } _i=1 ^p , the minimum K-cut problem is to compute disjoint subsets with sizes { k _i } _i=1 ^p , minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts. Received September 4, 1997; revised July 15, 1998.     

Efficient randomized generation of optimal algorithms for multiplication in certain finite fields

LetN _max(q) denote the maximum number of points of an elliptic curve over F _q . Given a prime powerq=p ^f and an integern satisfying 1/2q+1<n(N _max(q)–2)/2, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length 2n for multiplication in F _q ⁿ /F _q . The algorithm takes roughlyO(q ⁴+n ⁴logq) F _q -operations or equivalentlyO((q ⁴+n ⁴logq)f ²log² p) bit-operations to compute the output data.     

Visual space geometry derived from occlusion axioms

In our previous work [1] occlusion phenomena were considered as a foundation for development of geometrical structures in the visual field. The laws of occlusion were adapted to form the basis of an axiomatic system. Occlusion is formalized as a ternary relation and its properties include symmetry and transistivity. This leads to the definition of an abstract visual space (AVS). The geometry of an AVS is the subject of this research. Typical examples of an AVS are the convex open subsets of an n-dimensional real affine space for n2 or more generally, the convex open subsets of any n-dimensional affine space over some totally ordered field F, commutative or noncommutative. In an AVS we define such geometrical objects as lines, planes, convex bodies, closed and open subsets, etc. For any n-dimensional (n3) AVS X we construct an n-dimensional projective space P _F ⁿ over a totally ordered commutative or noncommutative field F and produce an embedding i: X xP _F ⁿ such that the image i(X) is open in P _F ⁿ and every line l in X is of the form l=i ^-1 (Li(X)) for some line L in P _F ⁿ. The mapping i and the field F depend on X and are unique up to isomorphism. We obtain a characterization of X via this embedding which is complete in the case of archimedean fields F. If F=R, the field of real numbers, i induces an embedding j: X ¶ A _R ⁿ and j(X) is a convex open subset of an affine space A _R ⁿ. If FR there can exist other types of AVS.     

Block Toeplitz matrices and preconditioning

We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT _n , withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T _n } are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L ², and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P _n ⁻¹ T_n}, where the sequence{P _n } is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP _n ⁻¹ T _n is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp ⁻¹ f. We also prove that the firstm eigenvalues ofP _n ⁻¹ T_n tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned matricesP _n ⁻¹ T_n are computed.     

A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

Lower bounds on space complexity for contextfree recognition

Summary Using methods from linear algebra and crossing-sequence arguments it is shown that logarithmic space is necessary for the recognition of all context-free nonregular subsets of {a₁}^* ... {a_n}^*, where {a₁,...,a_n} is some alphabet. It then follows that log n is a lower bound on the space complexity for the recognition of any bounded or deterministic non-regular context-free language.     

Energy-Efficient Paths in Radio Networks

We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p,q)=|pq| ^δ +C _p , for some constant δ>1 and nonnegative offset costs C _p . Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops.     

A decomposition scheme for single stage scheduling problems

This paper introduces a general decomposition scheme for single stage scheduling problems with jobs that have arbitrary release dates. We assume that the objective function is monotone in the completion time of each job. The decomposition scheme has significant theoretical and practical relevance. When assuming equal processing times, we can reduce the number of steps required to solve several well-known nonpreemptive single machine scheduling problems by O(n³)\mathcal{O}(n^{3}), provided the processing time p is constant. Specifically, we develop new approaches that solve the problems 1|r _i ,p _i =p|∑f _i (C _i ) and 1|r _i ,p _i =p|∑w _i U _i in O(n⁴)\mathcal{O}(n^{4}) time; the algorithms that have been described in the literature for these problems operate in O(n⁷)\mathcal{O}(n^{7}). Moreover, solution approaches for NP\mathcal{NP}-hard problems with unequal processing times may also benefit from our decomposition rule. This is particularly true if p _max/p _min is close to 1. Using the decomposition rule, either the problem size is reduced or additional information about the maximal schedule length is obtained.     

Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements

When we have n results x₁,...,x_n of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the intervals x_i of possible values of x₁ In such situations, for different possible values x_i∈ x_i, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some precise sense), it is known that we can compute the interval V in quadratic time O(n²). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n²)).     

Existence and Exponential Stability of Multiple Periodic Solutions for a Multidirectional Associative Memory Neural Network

The paper proposes several mathematical models of the multidirectional associative memory (MAM) neural network by analyzing its structure. A model of MAM with distributed delays is studied. Under some new assumptions on activation functions, 2^n₀[m/2]{2^{n_0[m/2]}} invariant subsets of MAM are constructed. Then the existence and the exponential stability of 2^n₀[m/2]{2^{n_0[m/2]}} periodic solutions located on invariant subsets are obtained by constructing a suitable Liapunov function and a Poincaré mapping. An estimating method of the exponential convergence rate is given. The obtained results are new to MAM neural networks. An example is given to illustrate the effectiveness of the results.     

Set multi-covering via inclusion–exclusion

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O^*((2t)ⁿ) time and O^*((t+1)ⁿ) space where t is the maximum value in the coverage requirement set (The O^*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)].     

Changing the diameter of the locally twisted cube

The hypercube network Q _n has been proved to be one of the most popular interconnection networks. The n-dimensional locally twisted cube LTQ _n is an important variant of Q _n . One of the critical performance factors of an interconnection network is the diameter which determines the maximum communication time between any pair of processors. In this paper, we investigate the diameter variability problems arising from the addition and deletion of edges in LTQ _n . We obtain three results in this paper: (1) for any integer n≥2, we find the least number of edges (denoted by ch ^?(LTQ _n )), whose deletion from LTQ _n causes the diameter to increase, (2) for any integer n≥2, when ch ^?(LTQ _n ) edges are deleted, the diameter will increase by 1 and (3) for any integer n≥4, the least number of edges whose addition to LTQ _n will decrease the diameter is at most 2 ^n?1.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

On the Sample Complexity of Weak Learning

In this paper, we study the sample complexity of weak learning. That is, we ask how many data must be collected from an unknown distribution in order to extract a small but significant advantage in prediction. We show that it is important to distinguish between those learning algorithms that output deterministic hypotheses and those that output randomized hypotheses. We prove that in the weak learning model, any algorithm using deterministic hypotheses to weakly learn a class of Vapnik-Chervonenkis dimension d(n) requires Ω ([formula]) examples. In contrast, when randomized hypotheses are allowed, we show that Θ (1) examples suffice in some cases. We then show that there exists an efficient algorithm using deterministic hypotheses that weakly learns against any distribution on a set of size d(n) with only O(d(n)^2/3) examples. Thus for the class of symmetric Boolean functions over n variables, where the strong learning sample complexity is Θ (n), the sample complexity for weak learning using deterministic hypotheses is Ω ([formula]) and O(n^2/3), and the sample complexity for weak learning using randomized hypotheses is Θ (1). Next we prove the existence of classes for which the distribution-free sample size required to obtain a slight advantage in prediction over random guessing is essentially equal to that required to obtain arbitrary accuracy. Finally, for a class of small circuits, namely all parity functions of subsets of n Boolean variables, we prove a weak learning sample complexity of Θ(n). This bound holds even if the weak learning algorithm is allowed to replace random sampling with membership queries, and the target distribution is uniform on {0, 1}ⁿ.