Bernd Bank
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Bernd Bank has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Joos Heintz
Departamento de Computación Universidad de Buenos Aires and CONICET Ciudad Univ., Pab.I 1428 Buenos Aires Argentina
8 shared publications - Marc Giusti
Laboratoire STIX, Ecole Polytechnique, 91128 Palaiseau
7 shared publications - G. M. Mbakop
Institut für Mathematik, Humboldt-Universität zu Berlin, Germany , DE
4 shared publications - Guillermo Matera
National Council of Science and Technology (CONICET), Buenos Aires, Argentina
4 shared publications - Luis Miguel Pardo
Santander, Spain
3 shared publications - Mohab Safey El Din
Sorbonne Université, CNRS, LIP6, Paris, France
3 shared publications
Latest Publications
- 1 June 2016
- Published by Elsevier in Journal of Complexity
- Vol. 34, 1-29
Quiz games as a model for information hiding
- 1 June 2016
- Published by Elsevier in Journal of Complexity
- Vol. 34, 1-29
Quiz games as a model for information hiding
- Open Access
Quiz Games as a model for Information Hiding
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.
Open AccessQuiz Games as a model for Information Hiding
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.
- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 159-184
Degeneracy Loci and Polynomial Equation Solving
- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 159-184
Degeneracy Loci and Polynomial Equation Solving
- Open Access
Intrinsic complexity estimates in polynomial optimization
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 $(s\,d)^{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 $(n\,d)^{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.Open AccessIntrinsic complexity estimates in polynomial optimization
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 $(s\,d)^{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 $(n\,d)^{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. - Open Access
Degeneracy loci and polynomial equation solving
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(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.Open AccessDegeneracy loci and polynomial equation solving
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(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. - Open Access
- 31 October 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (286) , 873-897
Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
Let <!-- MATH $X_1,\ldots ,X_n$ --> be indeterminates over <!-- MATH $\mathbb{Q}$ --> and let <!-- MATH $X:=(X_1,\ldots ,$ --> . Let <!-- MATH $F_1,\ldots ,F_p$ --> be a regular sequence of polynomials in <!-- MATH $\mathbb{Q}[X]$ --> of degree at most such that for each <!-- MATH $1\le k \le p$ --> the ideal <!-- MATH $(F_1,\ldots , F_k)$ --> is radical. Suppose that the variables <!-- MATH $X_1,\ldots ,X_n$ --> are in generic position with respect to <!-- MATH $F_1,\ldots ,F_p$ --> . Further, suppose that the polynomials are given by an essentially division-free circuit in <!-- MATH $\mathbb{Q}[X]$ --> of size and non-scalar depth .- 31 October 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (286) , 873-897
Open AccessPoint searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
Let <!-- MATH $X_1,\ldots ,X_n$ --> be indeterminates over <!-- MATH $\mathbb{Q}$ --> and let <!-- MATH $X:=(X_1,\ldots ,$ --> . Let <!-- MATH $F_1,\ldots ,F_p$ --> be a regular sequence of polynomials in <!-- MATH $\mathbb{Q}[X]$ --> of degree at most such that for each <!-- MATH $1\le k \le p$ --> the ideal <!-- MATH $(F_1,\ldots , F_k)$ --> is radical. Suppose that the variables <!-- MATH $X_1,\ldots ,X_n$ --> are in generic position with respect to <!-- MATH $F_1,\ldots ,F_p$ --> . Further, suppose that the polynomials are given by an essentially division-free circuit in <!-- MATH $\mathbb{Q}[X]$ --> of size and non-scalar depth . - 4 January 2012
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 12 (1) , 75-122
Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
- 4 January 2012
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 12 (1) , 75-122
Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces
- 12 January 2010
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 21 (1) , 33-83
On the geometry of polar varieties
- 12 January 2010
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 21 (1) , 33-83
On the geometry of polar varieties
- Open Access
On the geometry of polar varieties
We have developed in the past several algorithms with intrinsic complexity bounds for the problem of point finding in real algebraic varieties. Our aim here is to give a comprehensive presentation of the geometrical tools which are necessary to prove the correctness and complexity estimates of these algorithms. Our results form also the geometrical main ingredients for the computational treatment of singular hypersurfaces. In particular, we show the non--emptiness of suitable generic dual polar varieties of (possibly singular) real varieties, show that generic polar varieties may become singular at smooth points of the original variety and exhibit a sufficient criterion when this is not the case. Further, we introduce the new concept of meagerly generic polar varieties and give a degree estimate for them in terms of the degrees of generic polar varieties. The statements are illustrated by examples and a computer experiment.
Open AccessOn the geometry of polar varieties
We have developed in the past several algorithms with intrinsic complexity bounds for the problem of point finding in real algebraic varieties. Our aim here is to give a comprehensive presentation of the geometrical tools which are necessary to prove the correctness and complexity estimates of these algorithms. Our results form also the geometrical main ingredients for the computational treatment of singular hypersurfaces. In particular, we show the non--emptiness of suitable generic dual polar varieties of (possibly singular) real varieties, show that generic polar varieties may become singular at smooth points of the original variety and exhibit a sufficient criterion when this is not the case. Further, we introduce the new concept of meagerly generic polar varieties and give a degree estimate for them in terms of the degrees of generic polar varieties. The statements are illustrated by examples and a computer experiment.
- 1 September 2001
- Published by Springer Nature in Mathematische Zeitschrift
- Vol. 238 (1) , 115-144
Polar varieties and efficient real elimination
- 1 September 2001
- Published by Springer Nature in Mathematische Zeitschrift
- Vol. 238 (1) , 115-144
Polar varieties and efficient real elimination