Source author record

Alexander Shen

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

ResearcherUnclaimed source record

Catalog footprint

What is connected

35works
20topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

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.

Published work

35 published item(s)

preprint2026arXiv

Keeping Score: Efficiency Improvements in Neural Likelihood Surrogate Training via Score-Augmented Loss Functions

For stochastic process models, parameter inference is often severely bottlenecked by computationally expensive likelihood functions. Simulation-based inference (SBI) bypasses this restriction by constructing amortized surrogate likelihoods, but most SBI methods assume a black-box data generating process. While these surrogates are exact in the limit of infinite training data, practical scenarios force a strict tradeoff between model quality and simulation cost. In this work, we loosen the black-box assumption of SBI to improve this tradeoff for structured stochastic process models. Specifically, for neural network likelihood surrogates trained via probabilistic classification, we propose to augment the standard binary cross-entropy loss with exact score information $\nabla_θ\log p(x \mid θ)$ and adaptive weighting based on loss gradients. We evaluate our approach on case studies involving network dynamics and spatial processes, demonstrating that our method improves surrogate quality at a drastically lower computational cost than generating more training data. Notably, in some cases, our approach achieves downstream inference performance equivalent to a 10x increase in training data with less than a 1.1x increase in training time.

preprint2022arXiv

Inequalities for space-bounded Kolmogorov complexity

There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (Hammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998--2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpré (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpré's result with a tighter space bound, using Sipser's trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead.

preprint2020arXiv

Automatic Kolmogorov complexity, normality and finite state dimension revisited

It is well known that normality can be described as incompressibility via finite automata. Still the statement and the proof of this result as given by Becher and Heiber (2013) in terms of "lossless finite-state compressors" do not follow the standard scheme of Kolmogorov complexity definition (an automaton is used for compression, not decompression). We modify this approach to make it more similar to the traditional Kolmogorov complexity theory (and simpler) by explicitly defining the notion of automatic Kolmogorov complexity and using its simple properties. Using this characterization and a sufficient condition for normality in terms of Kolmogorov complexity derived from it, we provide easy proofs for classical results about normal sequences (Champernown, Wall, Piatetski-Shapiro, Besicovitch, Copeland, Erdos et al.) Then we extend this approach to finite state dimension. We show that the block entropy definition of the finite state dimension remains the same if non-aligned blocks are used. Then we provide equivalent definitions in terms of automatic complexity, superadditive bounds for Kolmogorov complexity, calibrated superadditive functions and finite state a priori probability and use them to give simple proofs for known results about finite state dimension, and for Agafonov's result saying that normality is preserved by automatic selection rules as well as the results of Schnorr and Stimm that relate normality to finite state martingales. Some results of this paper were presented at the Fundamentals in Computing Theory conferences in 2017 and 2019. Preliminary version of this paper (that does not mention the finite state dimension) was published in arxiv in~2017 (see the previous version of this submission).

preprint2020arXiv

Elections and statistics: the case of "United Russia", 2009-2020

This survey contains statistics on elections in Russia published in different places and available online. This data is discussed from the viewpoint of statistical model selection. The current version is updated including the materials up to July, 2020 voting on constitutional changes, Belarus 2020 elections and papers that appeared in 2020; most of the data are not consistent with the assumption of fair elections.

preprint2016arXiv

Conditional probabilities and van Lambalgen theorem revisited

The definition of conditional probability in case of continuous distributions was an important step in the development of mathematical theory of probabilities. How can we define this notion in algorithmic probability theory? In this survey we discuss the developments in this direction trying to explain what are the difficulties and what can be done to avoid them. Almost all the results discussed in this paper have been published (and we provide the references), but we tried to put them into perspective and to explain the proofs in a more intuitive way. We assume that the reader is familiar with basic notions of measure theory and algorithmic randomness.

preprint2016arXiv

Layerwise computability and image randomness

Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.

preprint2015arXiv

Algorithmic statistics revisited

The mission of statistics is to provide adequate statistical hypotheses (models) for observed data. But what is an "adequate" model? To answer this question, one needs to use the notions of algorithmic information theory. It turns out that for every data string $x$ one can naturally define "stochasticity profile", a curve that represents a trade-off between complexity of a model and its adequacy. This curve has four different equivalent definitions in terms of (1)~randomness deficiency, (2)~minimal description length, (3)~position in the lists of simple strings and (4)~Kolmogorov complexity with decompression time bounded by busy beaver function. We present a survey of the corresponding definitions and results relating them to each other.

preprint2015arXiv

Around Kolmogorov complexity: basic notions and results

Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. There are several textbooks and monographs devoted to this theory where one can find the detailed exposition of many difficult results as well as historical references. However, it seems that a short survey of its basic notions and main results relating these notions to each other, is missing. This report attempts to fill this gap and covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness (Martin-Löf randomness, Mises--Church randomness), effective Hausdorff dimension. We prove their basic properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity, complexity characterization for effective dimension) and show some applications (incompressibility method in computational complexity theory, incompleteness theorems). It is based on the lecture notes of a course at Uppsala University given by the author.

preprint2015arXiv

K-trivial, K-low and MLR-low sequences: a tutorial

A remarkable achievement in algorithmic randomness and algorithmic information theory was the discovery of the notions of K-trivial, K-low and Martin-Lof-random-low sets: three different definitions turns out to be equivalent for very non-trivial reasons. This paper, based on the course taught by one of the authors (L.B.) in Poncelet laboratory (CNRS, Moscow) in 2014, provides an exposition of the proof of this equivalence and some related results. We assume that the reader is familiar with basic notions of algorithmic information theory.

preprint2014arXiv

Fixed-point tile sets and their applications

An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals). We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. This construction it rather flexible, so it can be used in many ways: we show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, characterize effectively closed 1D subshift it terms of 2D shifts of finite type (improvement of a result by M. Hochman), to construct a tile set which has only complex tilings, and to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. For the latter we develop a hierarchical classification of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: there exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed.

preprint2013arXiv

Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity

Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., C(C(x)|x) > log n - log^(2) n - O(1). (Here log^(2) i = log log i.) Following Elena Kalinina (Kalinina 2011), we provide a simple game-based proof of this result; modifying her argument, we get a better (and tight) bound log n - O(1). We also show the same bound for prefix-free complexity. Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that |x| - C(x) < c and |x| + K(|x|) - K(x) > log^(2) |x| - c log^(3) |x|. In fact, the results of Solovay and Gacs are closely related. Using the result above, we provide a short proof for Solovay's result. We also generalize it by showing that for some c and for all n there are strings x of length n with n - C (x) < c and n + K(n) - K(x) > K(K(n)|n) - 3 K(K(K(n)|n)|n) - c. We also prove a close upper bound K(K(n)|n) + O(1). Finally, we provide a direct game proof for Joseph Miller's generalization (Miller 2006) of the same Solovay's theorem: if a co-enumerable set (a set with c.e. complement) contains for every length a string of this length, then it contains infinitely many strings x such that |x| + K(|x|) - K(x) > log^(2) |x| + O(log^(3) |x|).

preprint2013arXiv

Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma

A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovász local lemma. (A survey of Moser-Tardos proof is included to make the paper self-contained.)

preprint2013arXiv

The axiomatic power of Kolmogorov complexity

The famous Gödel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T. In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us to prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter, unless NP=PSPACE. We then study the axiomatic power of the statements of type "the Kolmogorov complexity of x exceeds n" in general. They are Π_1 (universally quantified) statements of Peano arithmetic. We show that by adding all true statements of this type, we obtain a theory that proves all true Π_1-statements, and also provide a more detailed classification. In particular, to derive all true Π_1-statements it is sufficient to add one statement of this type for each n (or even for infinitely many n) if strings are chosen in a special way. On the other hand, one may add statements of this type for most x of length n (for every n) and still obtain a weak theory. We also study other logical questions related to "random axioms". Finally, we consider a theory that claims Martin-Löf randomness of a given infinite binary sequence. This claim can be formalized in different ways. We show that different formalizations are closely related but not equivalent, and study their properties.

preprint2012arXiv

Limit complexities revisited [once more]

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that $\limsup_n C(x|n)$ equals $C^{0'}(x)$. Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary tree, to prove Conidis' theorem about limits of effectively open sets, and also to improve the results of Muchnik about limit frequencies. As a by-product, we get a criterion of 2-randomness proved by Miller: a sequence $X$ is 2-random if and only if there exists $c$ such that any prefix $x$ of $X$ is a prefix of some string $y$ such that $C(y)\ge |y|-c$. (In the 1960ies this property was suggested in Kolmogorov as one of possible randomness definitions.) We also get another 2-randomness criterion by Miller and Nies: $X$ is 2-random if and only if $C(x)\ge |x|-c$ for some $c$ and infinitely many prefixes $x$ of $X$. This is a modified version of our old paper that contained a weaker (and cumbersome) version of Conidis' result, and the proof used low basis theorem (in quite a strange way). The full version was formulated there as a conjecture. This conjecture was later proved by Conidis. Bruno Bauwens (personal communication) noted that the proof can be obtained also by a simple modification of our original argument, and we reproduce Bauwens' argument with his permission.

preprint2011arXiv

A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points

A theorem of Kučera states that given a Martin-Löf random infinite binary sequence ω and an effectively open set A of measure less than 1, some tail of ω is not in A. We first prove several results in the same spirit and generalize them via an effective version of a weak form of Birkhoff's ergodic theorem. We then use this result to get a stronger form of it, namely a very general effective version of Birkhoff's ergodic theorem, which improves all the results previously obtained in this direction, in particular those of V'Yugin, Nandakumar and Hoyrup, Rojas.

preprint2011arXiv

Algorithmic tests and randomness with respect to a class of measures

The paper considers quantitative versions of different randomness notions: algorithmic test measures the amount of non-randomness (and is infinite for non-random sequences). We start with computable measures on Cantor space (and Martin-Lof randomness), then consider uniform randomness (test is a function of a sequence and a measure, not necessarily computable) and arbitrary constructive metric spaces. We also consider tests for classes of measures, in particular Bernoulli measures on Cantor space, and show how they are related to uniform tests and original Martin-Lof definition. We show that Hyppocratic (blind, oracle-free) randomness is equivalent to uniform randomness for measures in an effectively orthogonal effectively compact class. We also consider the notions of sparse set and on-line randomness and show how they can be expressed in our framework.

preprint2011arXiv

Are random axioms useful?

The famous Gödel incompleteness theorem says that for every sufficiently rich formal theory (containing formal arithmetic in some natural sense) there exist true unprovable statements. Such statements would be natural candidates for being added as axioms, but where can we obtain them? One classical (and well studied) approach is to add (to some theory T) an axiom that claims the consistency of T. In this note we discuss the other one (motivated by Chaitin's version of the Gödel theorem) and show that it is not really useful (in the sense that it does not help us to prove new interesting theorems), at least if we are not limiting the proof complexity. We discuss also some related questions.

preprint2011arXiv

Kolmogorov complexity as a language

The notion of Kolmogorov complexity (=the minimal length of a program that generates some object) is often useful as a kind of language that allows us to reformulate some notions and therefore provide new intuition. In this survey we provide (with minimal comments) many different examples where notions and statements that involve Kolmogorov complexity are compared with their counterparts not involving complexity.

preprint2011arXiv

Probability-free pricing of adjusted American lookbacks

Consider an American option that pays G(X^*_t) when exercised at time t, where G is a positive increasing function, X^*_t := \sup_{s\le t}X_s, and X_s is the price of the underlying security at time s. Assuming zero interest rates, we show that the seller of this option can hedge his position by trading in the underlying security if he begins with initial capital X_0\int_{X_0}^{\infty}G(x)x^{-2}dx (and this is the smallest initial capital that allows him to hedge his position). This leads to strategies for trading that are always competitive both with a given strategy's current performance and, to a somewhat lesser degree, with its best performance so far. It also leads to methods of statistical testing that avoid sacrificing too much of the maximum statistical significance that they achieve in the course of accumulating data.

preprint2011arXiv

Random semicomputable reals revisited

The aim of this expository paper is to present a nice series of results, obtained in the papers of Chaitin (1976), Solovay (1975), Calude et al. (1998), Kucera and Slaman (2001). This joint effort led to a full characterization of lower semicomputable random reals, both as those that can be expressed as a "Chaitin Omega" and those that are maximal for the Solovay reducibility. The original proofs were somewhat involved; in this paper, we present these results in an elementary way, in particular requiring only basic knowledge of algorithmic randomness. We add also several simple observations relating lower semicomputable random reals and busy beaver functions.

preprint2011arXiv

Test Martingales, Bayes Factors and $p$-Values

A nonnegative martingale with initial value equal to one measures evidence against a probabilistic hypothesis. The inverse of its value at some stopping time can be interpreted as a Bayes factor. If we exaggerate the evidence by considering the largest value attained so far by such a martingale, the exaggeration will be limited, and there are systematic ways to eliminate it. The inverse of the exaggerated value at some stopping time can be interpreted as a $p$-value. We give a simple characterization of all increasing functions that eliminate the exaggeration.

preprint2011arXiv

Variations on Muchnik's Conditional Complexity Theorem

Muchnik's theorem about simple conditional descriptions states that for all strings $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. In this paper we present two new proofs of this theorem. The first one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik's theorem for space-bounded Kolmogorov complexity.

preprint2010arXiv

1D Effectively Closed Subshifts and 2D Tilings

Michael Hochman showed that every 1D effectively closed subshift can be simulated by a 3D subshift of finite type and asked whether the same can be done in 2D. It turned out that the answer is positive and necessary tools were already developed in tilings theory. We discuss two alternative approaches: first, developed by N. Aubrun and M. Sablik, goes back to Leonid Levin; the second one, developed by the authors, goes back to Peter Gacs.

preprint2010arXiv

Fixed Point and Aperiodic Tilings

An aperiodic tile set was first constructed by R.Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals) We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. The flexibility of this construction allows us to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.

preprint2010arXiv

Fixed point theorem and aperiodic tilings

We propose a new simple construction of an aperiodic tile set based on self-referential (fixed point) argument. People often say about some discovery that it appeared "ahead of time", meaning that it could be fully understood only in the context of ideas developed later. For the topic of this note, the construction of an aperiodic tile set based on the fixed-point (self-referential) approach, the situation is exactly the opposite. It should have been found in 1960s when the question about aperiodic tile sets was first asked: all the tools were quite standard and widely used at that time. However, the history had chosen a different path and many nice geometric ad hoc constructions were developed instead (by Berger, Robinson, Penrose, Ammann and many others. In this note we try to correct this error and present a construction that should have been discovered first but seemed to be unnoticed for more that forty years.

preprint2010arXiv

Game interpretation of Kolmogorov complexity

The Kolmogorov complexity function K can be relativized using any oracle A, and most properties of K remain true for relativized versions. In section 1 we provide an explanation for this observation by giving a game-theoretic interpretation and showing that all "natural" properties are either true for all sufficiently powerful oracles or false for all sufficiently powerful oracles. This result is a simple consequence of Martin's determinacy theorem, but its proof is instructive: it shows how one can prove statements about Kolmogorov complexity by constructing a special game and a winning strategy in this game. This technique is illustrated by several examples (total conditional complexity, bijection complexity, randomness extraction, contrasting plain and prefix complexities).

preprint2010arXiv

Insuring against loss of evidence in game-theoretic probability

We consider the game-theoretic scenario of testing the performance of Forecaster by Sceptic who gambles against the forecasts. Sceptic's current capital is interpreted as the amount of evidence he has found against Forecaster. Reporting the maximum of Sceptic's capital so far exaggerates the evidence. We characterize the set of all increasing functions that remove the exaggeration. This result can be used for insuring against loss of evidence.

preprint2010arXiv

Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One

C.Calude, A.Nies, L.Staiger, and F.Stephan posed the following question about the relation between plain and prefix Kolmogorov complexities (see their paper in DLT 2008 conference proceedings): does the domain of every optimal decompressor contain the domain of some optimal prefix-free decompressor? In this paper we provide a negative answer to this question.