Artem Chernikov
YOU?
Author Swipe
View article: Higher-arity PAC learning, VC dimension and packing lemma
Higher-arity PAC learning, VC dimension and packing lemma Open
The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise…
View article: Averages of hypergraphs and higher arity stability
Averages of hypergraphs and higher arity stability Open
We show that $k$-ary functions giving the measure of the intersection of multi-parametric families of sets in probability spaces, e.g. $(x,y,z) \in X \times Y \times Z \mapsto μ(P_{x,y} \cap Q_{x,z} \cap R_{y,z})$, satisfy a particularly s…
View article: Externally definable fsg groups in NIP theories
Externally definable fsg groups in NIP theories Open
We show that every fsg group externally definable in an NIP structure is definably isomorphic to a group interpretable in it. Our proof relies on honest definitions and a group chunk result reconstructing a hyper-definable group from its m…
View article: Quantum algorithm for reducing amplitudes in order to search and filter data
Quantum algorithm for reducing amplitudes in order to search and filter data Open
The method is introduced for fast data processing by reducing the probability amplitudes of undesirable elements. The algorithm has a mathematical description and circuit implementation on a quantum processor. The idea is to make a quick d…
View article: Optimized Amplitude Amplification for Quantum State Preparation
Optimized Amplitude Amplification for Quantum State Preparation Open
In this paper, we present an algorithm for preparing quantum states of the form $\sum_{i=0}^{n-1} α_i |i\rangle$, where the coefficients $α_i$ are specified by a quantum oracle. Our method achieves this task twice as fast as the best exist…
View article: On n-dependent groups and fields III. Multilinear forms and invariant connected components
On n-dependent groups and fields III. Multilinear forms and invariant connected components Open
We develop some model theory of multi-linear forms, generalizing Granger in the bi-linear case. In particular, after proving a quantifier elimination result, we show that for an NIP field K, the theory of infinite dimensional non-degenerat…
View article: Intersecting sets in probability spaces and Shelah's classification
Intersecting sets in probability spaces and Shelah's classification Open
For $n \in \mathbb{N}$ and $\varepsilon > 0$, given a sufficiently long sequence of events in a probability space all of measure at least $\varepsilon$, some $n$ of them will have a common intersection. A more subtle pattern: for any $0 < …
View article: Definable convolution and idempotent Keisler measures III. Generic stability, generic transitivity, and revised Newelski's conjecture
Definable convolution and idempotent Keisler measures III. Generic stability, generic transitivity, and revised Newelski's conjecture Open
We study idempotent measures and the structure of the convolution semigroups of measures over definable groups. We isolate the property of generic transitivity and demonstrate that it is sufficient (and necessary) to develop stable group t…
View article: Perfect stable regularity lemma and slice-wise stable hypergraphs
Perfect stable regularity lemma and slice-wise stable hypergraphs Open
We investigate various forms of (model-theoretic) stability for hypergraphs and their corresponding strengthenings of the hypergraph regularity lemma with respect to partitions of vertices. On the one hand, we provide a complete classifica…
View article: Definable convolution and idempotent Keisler measures, II
Definable convolution and idempotent Keisler measures, II Open
With gratitude to Ehud Hrushovski, whose beautiful ideas have deeply influenced the
TRANSITIVITY, LOWNESS, AND RANKS IN NSOP THEORIES Open
We develop the theory of Kim-independence in the context of NSOP $_{1}$ theories satisfying the existence axiom. We show that, in such theories, Kim-independence is transitive and that -Morley sequences witness Kim-dividing. As application…
View article: Combinatorial properties of nonarchimedean convex sets
Combinatorial properties of nonarchimedean convex sets Open
We study combinatorial properties of convex sets over arbitrary valued fields. We demonstrate analogs of some classical results for convex sets over the reals (e.g. the fractional Helly theorem and Bárány's theorem on points in many simpli…
View article: SEMI-EQUATIONAL THEORIES
SEMI-EQUATIONAL THEORIES Open
We introduce and study (weakly) semi-equational theories, generalizing equationality in stable theories (in the sense of Srour) to the NIP context. In particular, we establish a connection to distality via one-sided strong honest definitio…
View article: Semi-equational theories
Semi-equational theories Open
We introduce and study semi-equational and weakly semi-equational theories, generalizing equationality in stable theories (in the sense of Srour) to the NIP context. In particular, we establish a connection to distality via one-sided stron…
View article: Definable convolution and idempotent Keisler measures II
Definable convolution and idempotent Keisler measures II Open
We study convolution semigroups of invariant/finitely satisfiable Keisler measures in NIP groups. We show that the ideal (Ellis) subgroups are always trivial and describe minimal left ideals in the definably amenable case, demonstrating th…
View article: Distality in valued fields and related structures
Distality in valued fields and related structures Open
We investigate distality and existence of distal expansions in valued fields and related structures. In particular, we characterize distality in a large class of ordered abelian groups, provide an Ax-Kochen-Eršov-style characterization for…
View article: Invariant measures in simple and in small theories
Invariant measures in simple and in small theories Open
We give examples of (i) a simple theory with a formula (with parameters) which does not fork over the empty set but has mu measure 0 for every automorphism invariant Keisler measure mu, and (ii) a definable group G in a simple theory such …
View article: Model-theoretic Elekes-Szabó for stable and o-minimal hypergraphs
Model-theoretic Elekes-Szabó for stable and o-minimal hypergraphs Open
A theorem of Elekes and Szabó recognizes algebraic groups among certain complex algebraic varieties with maximal size intersections with finite grids. We establish a generalization to relations of any arity and dimension, definable in: 1) …
View article: Definable Regularity Lemmas for Nip Hypergraphs
Definable Regularity Lemmas for Nip Hypergraphs Open
We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and …
View article: Zarankiewicz’s problem for semilinear hypergraphs
Zarankiewicz’s problem for semilinear hypergraphs Open
A bipartite graph $H = \left (V_1, V_2; E \right )$ with $\lvert V_1\rvert + \lvert V_2\rvert = n$ is semilinear if $V_i \subseteq \mathbb {R}^{d_i}$ for some $d_i$ and the edge relation E consists of the pairs of points $(x_1, x_2) \in V_…
View article: On<i>n</i>-dependent groups and fields II
On<i>n</i>-dependent groups and fields II Open
We continue the study of n -dependent groups, fields and related structures, largely motivated by the conjecture that every n -dependent field is dependent. We provide evidence toward this conjecture by showing that every infinite n -depen…
View article: Hypergraph regularity and higher arity VC-dimension
Hypergraph regularity and higher arity VC-dimension Open
We generalize the fact that graphs with small VC-dimension can be approximated by rectangles, showing that hypergraphs with small VC_k-dimension (equivalently, omitting a fixed finite (k+1)-partite (k+1)-uniform hypergraph) can be approxim…
View article: Transitivity, lowness, and ranks in NSOP$_1$ theories
Transitivity, lowness, and ranks in NSOP$_1$ theories Open
We develop the theory of Kim-independence in the context of NSOP$_{1}$ theories satsifying the existence axiom. We show that, in such theories, Kim-independence is transitive and that $\ind^{K}$-Morley sequences witness Kim-dividing. As ap…
View article: Definable convolution and idempotent Keisler measures
Definable convolution and idempotent Keisler measures Open
We initiate a systematic study of the convolution operation on Keisler measures, generalizing the work of Newelski in the case of types. Adapting results of Glicksberg, we show that the supports of generically stable (or just definable, as…
View article: RAMSEY GROWTH IN SOME NIP STRUCTURES
RAMSEY GROWTH IN SOME NIP STRUCTURES Open
We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek ( Duke Mathematical Journal 163 (12) (2014), 2243…
View article: Ostashkov. The Possibility of Rebirth
Ostashkov. The Possibility of Rebirth Open
The project is focused on revitalization of the cultural resource of the central part of Ostashkov. It is proposed to make a detailed analysis of the information concerning mapping and traffic situation. The authors offer a brief developme…
Model theory, Keisler measures, and groups - Ehud Hrushovski, Ya’acov Peterzil and Anand Pillay, Groups, measures, and the NIP. Journal of the American Mathematical Society, vol. 21 (2008), no. 2, pp. 563–596. - Ehud Hrushovski and Anand Pillay, On NIP and invariant measures. Journal of the European Mathematical Society, vol.13 (2011), no. 4, pp. 1005–1061. - Ehud Hrushovski, Anand Pillay, and Pierre Simon, Generically stable and smooth measures in NIP theories. Transactions of the American Mathematical Society, vol. 365 (2013), no. 5, pp. 2341–2366. Open
An abstract is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.