Source author record

Martin Hils

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO Artificial Intelligence Computational Complexity Logic in Computer Science math.AG

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Definable Equivariant Retractions in Non-Archimedean Geometry

For $G$ an algebraic group definable over a model of $\operatorname{ACVF}$ , or more generally a definable subgroup of an algebraic group, we study the stable completion $\widehat{G}$ of $G$ , as introduced by Loeser and the second author. For $G$ connected and stably dominated, assuming $G$ commutative or that the valued field is of equicharacteristic 0, we construct a pro-definable $G$ -equivariant strong deformation retraction of $\widehat{G}$ onto the generic type of $G$ . For $G=S$ a semiabelian variety, we construct a pro-definable $S$ -equivariant strong deformation retraction of $\widehat{S}$ onto a definable group which is internal to the value group. We show that, in case $S$ is defined over a complete valued field $K$ with value group a subgroup of $\mathbb{R}$ , this map descends to an $S(K)$ -equivariant strong deformation retraction of the Berkovich analytification $S^{\mathrm{an}}$ of $S$ onto a piecewise linear group, namely onto the skeleton of $S^{\mathrm{an}}$ . This yields a construction of such a retraction without resorting to an analytic (non-algebraic) uniformization of $S$ . Furthermore, we prove a general result on abelian groups definable in an NIP theory: any such group $G$ is a directed union of $\infty$ -definable subgroups which all stabilize a generically stable Keisler measure on $G$ .

preprint2014arXiv

Bad fields with torsion

We extend the construction of bad fields of characteristic zero to the case of arbitrary prescribed divisible green torsion.

preprint2013arXiv

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

The universal-algebraic approach has proved a powerful tool in the study of the complexity of CSPs. This approach has previously been applied to the study of CSPs with finite or (infinite) omega-categorical templates, and relies on two facts. The first is that in finite or omega-categorical structures A, a relation is primitive positive definable if and only if it is preserved by the polymorphisms of A. The second is that every finite or omega-categorical structure is homomorphically equivalent to a core structure. In this paper, we present generalizations of these facts to infinite structures that are not necessarily omega-categorical. (This abstract has been severely curtailed by the space constraints of arXiv -- please read the full abstract in the article.) Finally, we present applications of our general results to the description and analysis of the complexity of CSPs. In particular, we give general hardness criteria based on the absence of polymorphisms that depend on more than one argument, and we present a polymorphism-based description of those CSPs that are first-order definable (and therefore can be solved in polynomial time).

preprint2013arXiv

Valued difference fields and NTP2

We show that the theory of the non-standard Frobenius automorphism, acting on an algebraically closed valued field of equal characteristic 0, is NTP2. More generally, in the contractive as well as in the isometric case, we prove that a sigma-henselian valued difference field of equicharacteristic 0 is NTP2, provided both the residue difference field and the value group (as an ordered difference group) are NTP2.

preprint2012arXiv

Tractable Set Constraints

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

preprint2011arXiv

Generic Automorphisms and Green Fields

We show that the generic automorphism is axiomatisable in the green field of Poizat (once Morleyised) as well as in the bad fields which are obtained by collapsing this green field to finite Morley rank. As a corollary, we obtain "bad pseudofinite fields" in characteristic 0. In both cases, we give geometric axioms. In fact, a general framework is presented allowing this kind of axiomatisation. We deduce from various constructibility results for algebraic varieties in characteristic 0 that the green and bad fields fall into this framework. Finally, we give similar results for other theories obtained by Hrushovski amalgamation, e.g. the free fusion of two strongly minimal theories having the definable multiplicity property. We also close a gap in the construction of the bad field, showing that the codes may be chosen to be families of strongly minimal sets.

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.