BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We define the notion of a continuously differentiable perfect learning algorithm for multilayer neural network architectures and show that such algorithms don't exist provided that the length of the data set exceeds the number of involved parameters and the activation functions are logistic, tanh or sin.
We present a general computation model inspired in the notion of information hiding in software engineering. This model has the form of a game which we call quiz game. It allows in a uniform way to prove exponential lower bounds for several complexity problems of elimination theory.
It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using (sd)O(n) arithmetic operations, where n and s are the numbers of variables and constraints and d is the maximal degree of the polynomials involved.\spar \noindent We associate to each of these problems an intrinsic system degree which becomes in worst case of order (nd)O(n) and which measures the intrinsic complexity of the task under consideration.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers C and let F be a (p×s)-matrix of coordinate functions of C[V], where s≥p+r. The pair (V,F) determines a vector bundle E of rank s−p over W:={x∈V:rkF(x)=p}. We associate with (V,F) a descending chain of degeneracy loci of E (the generic polar varieties of V represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.
The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.
We introduce the notion of a robust parameterized arithmetic circuit for the evaluation of algebraic families of multivariate polynomials. Based on this notion, we present a computation model, adapted to Scientific Computing, which captures all known branching parsimonious symbolic algorithms in effective Algebraic Geometry. We justify this model by arguments from Software Engineering. Finally we exhibit a class of simple elimination problems of effective Algebraic Geometry which require exponential time to be solved by branching parsimonious algorithms of our computation model.
Let $\cp:=(P_1,...,P_s)$ be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1≤i≤s the polynomial Pi can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family $\cp$ is in a suitable sense \emph{generic}. We construct a database D, supported by an algebraic computation tree, such that for each x∈[0,1]n the query for the signs of P1(x),...,Ps(x) can be answered using $h d^{\cO(n^2)}$ comparisons and nL arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of D are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting however an exponential number of comparisons.
We model the algorithmic task of geometric elimination (e.g., quantifier elimination in the elementary field theories of real and complex numbers) by means of certain constraint database queries, called geometric queries. As a particular case of such a geometric elimination task, we consider sample point queries. We show exponential lower complexity bounds for evaluating geometric queries in the general and in the particular case of sample point queries. Although this paper is of theoretical nature, its aim is to explore the possibilities and (complexity-)limits of computer implemented query evaluation algorithms for Constraint Databases, based on the principles of the most advanced geometric elimination procedures and their implementations, like, e.g., the software package "Kronecker".
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.