Boris Ryabko

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs

to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted

using information on the word $x_1, x_2, ...., x_t $ only. We use the game

theoretical interpretation which can be traced to Laplace where there ...
more >>>

Maria Lopez-Valdes

We define a new discrete version of scaled dimension and we find

connections between the scaled dimension of a string and its Kolmogorov

complexity and predictability. We give a new characterization

of constructive scaled dimension by Kolmogorov complexity, and prove

a new result about scaled dimension and prediction.

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Alexander Smal, Navid Talebanfard

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around $n/k$ ... more >>>

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>