Source author record

Peter Scheiblechner

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

ResearcherUnclaimed source record

Computational Complexity math.AG math.AC Symbolic Computation

Catalog footprint

What is connected

3works

4topics

2close 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.

preprint2012arXiv

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic p>0, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to a non-degeneracy condition on a lift of the Jacobian polynomial over (an unramified extension of) the ring of p-adic integers. Our proof builds on the de Rham-Witt complex, which was invented by Illusie (1979) for crystalline cohomology computations, and we deduce a natural generalization of the Jacobian. This new avatar we call the Witt-Jacobian. In essence, we show how to faithfully differentiate polynomials over F_p (i.e. somehow avoid dx^p/dx=0) and thus capture algebraic independence. We apply the new criterion to put the problem of testing algebraic independence in the complexity class NP^#P (previously best was PSPACE). Also, we give a modest application to the problem of identity testing in algebraic complexity theory.

preprint2012arXiv

Effective de Rham Cohomology - The Hypersurface Case

We prove an effective bound for the degrees of generators of the algebraic de Rham cohomology of smooth affine hypersurfaces. In particular, we show that the de Rham cohomology H_dR^p(X) of a smooth hypersurface X of degree d in C^n can be generated by differential forms of degree d^O(pn). This result is relevant for the algorithmic computation of the cohomology, but is also motivated by questions in the theory of ordinary differential equations related to the infinitesimal Hilbert 16th problem.

preprint2011arXiv

Castelnuovo-Mumford Regularity and Computing the de Rham Cohomology of Smooth Projective Varieties

We describe a parallel polynomial time algorithm for computing the topological Betti numbers of a smooth complex projective variety $X$. It is the first single exponential time algorithm for computing the Betti numbers of a significant class of complex varieties of arbitrary dimension. Our main theoretical result is that the Castelnuovo-Mumford regularity of the sheaf of differential $p$-forms on $X$ is bounded by $p(em+1)D$, where $e$, $m$, and $D$ are the maximal codimension, dimension, and degree, respectively, of all irreducible components of $X$. It follows that, for a union $V$ of generic hyperplane sections in $X$, the algebraic de Rham cohomology of $X\setminus V$ is described by differential forms with poles along $V$ of single exponential order. This yields a similar description of the de Rham cohomology of $X$, which allows its efficient computation. Furthermore, we give a parallel polynomial time algorithm for testing whether a projective variety is smooth.