Branching programs provide lower bounds on the area of VLSI circuits
Breaking the curse of dimensionality [Book]
Brève communication. Performance du gradient réduit généralisé avec une méthode quasi newtonienne pour la programmation non linéaire
Calculation des valeurs numcute{e}riques des polynomes au moyen des spectres mathematiques
Can Adaption Help on the Average.
Can Visibility Graphs Be Represented Compactly?.
Chance constrained bottleneck transportation problem with preference of routes
This paper considers a variant of the bottleneck transportation problem. For each supply-demand point pair, the transportation time is an independent random variable. Preference of each route is attached. Our model has two criteria, namely: minimize the transportation time target subject to a chance constraint and maximize the minimal preference among the used routes. Since usually a transportation pattern optimizing two objectives simultaneously does not exist, we define non-domination in this...
Chaos and complexity in a simple model of production dynamics.
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Checking positive definiteness or stability of symmetric interval matrices is NP-hard
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
Circuit lower bounds and linear codes.
Classes of Graphs Which Approximate the Complete Euclidean Graph.
Combinatorial analysis of quicksort algorithm
Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.
Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
Combined complexity classes for finite functions
Comparing notions of approximation.
In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired by some results...
Complexité algébrique
Complexité de l'arboricité linéaire d'un graphe II
Complexité de problèmes liés aux graphes sans circuit