Source author record

Peter Franek

Peter Franek appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Computational Geometry math.AT math.DG Computer Science and Game Theory Logic in Computer Science math.AG math.CO math.GR

Catalog footprint

What is connected

7works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Quasi-decidability of a Fragment of the First-order Theory of Real Numbers

In this paper we consider a fragment of the first-order theory of the real numbers that includes systems of equations of continuous functions in bounded domains, and for which all functions are computable in the sense that it is possible to compute arbitrarily close piece-wise interval approximations. Even though this fragment is undecidable, we prove that there is a (possibly non-terminating) algorithm for checking satisfiability such that (1) whenever it terminates, it computes a correct answer, and (2) it always terminates when the input is robust. A formula is robust, if its satisfiability does not change under small perturbations. As a basic tool for our algorithm we use the notion of degree from the field of (differential) topology.

preprint2015arXiv

On Computability and Triviality of Well Groups

The concept of well group in a special but important case captures homological properties of the zero set of a continuous map $f:K\to R^n$ on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within $L_\infty$ distance r from f for a given r>0. The main drawback of the approach is that the computability of well groups was shown only when dim K=n or n=1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K<2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps $f,f': K\to R^n$ with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

preprint2014arXiv

Effective Topological Degree Computation Based on Interval Arithmetic

We describe a new algorithm for calculating the topological degree deg (f, B, 0) where B \subseteq Rn is a product of closed real intervals and f : B \rightarrow Rn is a real-valued continuous function given in the form of arithmetical expressions. The algorithm cleanly separates numerical from combinatorial computation. Based on this, the numerical part provably computes only the information that is strictly necessary for the following combinatorial part, and the combinatorial part may optimize its computation based on the numerical information computed before. We also present computational experiments based on an implementation of the algorithm. Also, in contrast to previous work, the algorithm does not assume knowledge of a Lipschitz constant of the function f, and works for arbitrary continuous functions for which some notion of interval arithmetic can be defined.

preprint2014arXiv

Robust Satisfiability of Systems of Equations

We study the problem of \emph{robust satisfiability} of systems of nonlinear equations, namely, whether for a given continuous function $f:\,K\to\mathbb{R}^n$ on a~finite simplicial complex $K$ and $α>0$, it holds that each function $g:\,K\to\mathbb{R}^n$ such that $\|g-f\|_\infty \leq α$, has a root in $K$. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed $n$, assuming $\dim K \le 2n-3$. This is a substantial extension of previous computational applications of \emph{topological degree} and related concepts in numerical and interval analysis. Via a reverse reduction we prove that the problem is undecidable when $\dim K\ge 2n-2$, where the threshold comes from the \emph{stable range} in homotopy theory. For the lucidity of our exposition, we focus on the setting when $f$ is piecewise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.

preprint2013arXiv

Symmetries of Quasi-Values

According to Shapley's game-theoretical result, there exists a unique game value of finite cooperative games that satisfies axioms on additivity, efficiency, null-player property and symmetry. The original setting requires symmetry with respect to arbitrary permutations of players. We analyze the consequences of weakening the symmetry axioms and study quasi-values that are symmetric with respect to permutations from a group $G\leq S_n$. We classify all the permutation groups $G$ that are large enough to assure a unique $G$-symmetric quasi-value, as well as the structure and dimension of the space of all such quasi-values for a general permutation group $G$. We show how to construct $G$-symmetric quasi-values algorithmically by averaging certain basic quasi-values (marginal operators).

preprint2011arXiv

Hyperplane section $\mathbb{OP}^2_0$ of the complex Cayley plane as the homogeneous space $\mathrm{F_4/P_4}$

We prove that the exceptional complex Lie group $F_4$ has a transitive action on the hyperplane section of the complex Cayley plane $\mathbb{OP}^2$. Our proof is direct and constructive. We use an explicit realization of the vector and spin actions of $\Spin(9,\C) \leq F_4$. Moreover, we identify the stabilizer of the $F_4$-action as a parabolic subgroup $P_4$ (with Levi factor $B_3T_1$) of the complex Lie group $F_4$. In the real case we obtain an analogous realization of $F_4^{(-20)}/P_4$.

preprint2007arXiv

Generalized Dolbeault sequences in parabolic geometry

In this paper, we show the existence of a sequence of invariant differential operators on a particular homogeneous model $G/P$ of a Cartan geometry. The first operator in this sequence can be locally identified with the Dirac operator in $k$ Clifford variables, $D=(D_1,..., D_k)$, where $D_i=\sum_j e_j\cdot \partial_{ij}: C^\infty((\R^n)^k,§)\to C^\infty((\R^n)^k,§)$. We describe the structure of these sequences in case the dimension $n$ is odd. It follows from the construction that all these operators are invariant with respect to the action of the group $G$. These results are obtained by constructing homomorphisms of generalized Verma modules, what are purely algebraic objects.