Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Prediction:
TR02-011 | 14th October 2001
Boris Ryabko

The nonprobabilistic approach to learning the best prediction.

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 >>>

TR06-047 | 11th February 2006
Maria Lopez-Valdes

Scaled Dimension of Individual Strings

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.

more >>>

TR16-154 | 21st September 2016
Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor

Logical Induction

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 >>>

TR17-149 | 7th October 2017
Or Meir, Avi Wigderson

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 5

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 >>>

TR17-191 | 15th December 2017
Alexander Smal, Navid Talebanfard

Prediction from Partial Information and Hindsight, an Alternative Proof

Revisions: 2

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 >>>

TR20-176 | 26th November 2020
Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Outcome Indistinguishability

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 >>>

ISSN 1433-8092 | Imprint