Dynamic Point Location in Arrangements of Hyperplanes.
Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling.
Efficient computation of addition chains
The aim of this paper is to present a unifying approach to the computation of short addition chains. Our method is based upon continued fraction expansions. Most of the popular methods for the generation of addition chains, such as the binary method, the factor method, etc..., fit in our framework. However, we present new and better algorithms. We give a general upper bound for the complexity of continued fraction methods, as a function of a chosen strategy, thus the total number of operations required...
Efficient distributed algorithms by using the archimedean time assumption
Efficient simulation of synchronous systems by multi-speed systems
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number...
Efficient simulation of synchronous systems by multi-speed systems
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the...
Einige Resultate über Berechnungskomplexität.
Elementariness of a finite set of words is co-NP-complete
Elliptic curves with j-invariant equals 0 or 1728 over a finite prime field.
Let p be a prime number, p ≠ 2,3 and Fp the finite field with p elements. An elliptic curve E over Fp is a projective nonsingular curve of genus 1 defined over Fp. Each one of these curves has an isomorphic model given by an (Weierstrass) equation E: y2 = x3 + Ax + B, A,B ∈ Fp with D = 4A3 + 27B2 ≠ 0. The j-invariant of E is defined by j(E) = 1728·4A3/D.The aim of this note is to establish some results concerning the cardinality of the group of points on elliptic curves over Fp with j-invariants...
Equations in words: An algorithmic contribution.
Establishing Order in Planar Subdivisions.
Estimation of the algorithmic complexity of classes of computable models.
Estudio de algunas secuencias pseudoaleatorias de aplicación criptográfica.
Pseudorandom binary sequences are required in stream ciphers and other applications of modern communication systems. In the first case it is essential that the sequences be unpredictable. The linear complexity of a sequence is the amount of it required to define the remainder. This work addresses the problem of the analysis and computation of the linear complexity of certain pseudorandom binary sequences. Finally we conclude some characteristics of the nonlinear function that produces the sequences...
Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.
Even kernels.
Exact bounds on the complexity of sequential string matching algorithms. (Des bornes exactes de la complexité des algorithmes séquentiels de recherche d'un motif.)
Experiments with the fixed-parameter approach for two-layer planarization.
Exploiting the structure of conflict graphs in high level synthesis
In this paper we analyze the computational complexity of a processor optimization problem. Given operations with interval times in a branching flow graph, the problem is to find an assignment of the operations to a minimum number of processors. We analyze the complexity of this assignment problem for flow graphs with a constant number of program traces and a constant number of processors.
Exponential tail bounds for max-recursive sequences.
Extremum-searching hierarchical parallel probabilistic algorithms