-
Sorting by Transpositions is Difficult
International audience -
Analytical properties of resource-bounded real functionals
International audience -
COMBINATORIAL PROBLEMS IN PRODUCTION LINES CONFIGURATION : COMPUTATIONAL ANAL...
The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the... -
Complexity of Existential Positive First-Order Logic
International audience -
Complexity of Buffer Capacity Allocation Problems for Production Lines with U...
International audience -
Algorithmic Aspects of Genome Rearrangements
In this thesis, we explore the algorithmical complexity of several problems stemming from comparative genomics, and we provide solutions for some of these problems in... -
Canonical decomposition of semi-symmetric semi-nonnegative three-way arrays .
International audience -
Achieving Low-Complexity Maximum-Likelihood Detection for the 3D MIMO Code
International audience -
Geometrical model of computation: fractals and complexity gaps
Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its... -
Projection onto the Cosparse Set is NP-Hard
to appear in ICASSP 2014 -
Obsessional cliques: a semantic characterization of bounded time complexity
We give a semantic characterization of bounded complexity proofs. We introduce the notion of obsessional clique in the relational model of linear logic and show that... -
Exclusive Graph Searching vs. Pathwidth
In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a... -
Dual discrete geometric methods in terms of scalar potential on unstructured ...
International audience -
The complexity of some complementation problems
Article dans revue scientifique avec comité de lecture. -
On the complexity of recognizing the Hilbert basis of a linear Diophantine sy...
Colloque avec actes et comité de lecture. -
Computational Complexity of Simultaneous Elementary Matching Problems
Article dans revue scientifique avec comité de lecture. -
Grammatical compression: compressed equivalence and other problems
special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications -
Ramified Recurrence and Computational Complexity IV : Predicative Functionals...
to appear. Article dans revue scientifique avec comité de lecture. -
Euclidean lattice basis reduction: algorithms and experiments for disclosing ...
We review polynomial time approaches for computing simultaneous integer relations among real numbers. A variant of the LLL lattice reduction algorithm (A. Lenstra, H.... -
Some numerical considerations for lattice basis reduction
Fastest algorithms and implementations for LLL basis reduction are highly hybrid symbolic-numeric. A "numerical engine" computes, via a orthogonalization process, the...
