Samuel Epstein Kolmogorov

Derandomization 2023 Hal

Samuel Epstein

Kolmogorov Derandomization

Chapter 1

Introduction

In mathematics, the probabilistic method is a constructive method of proving the existence of a certain type of mathematical object. This method, pioneered by Paul Erdös, involves choosing objects from a certain class randomly, and showing objects of a certain type occur with non-zero probability. Thus objects of a certain type are guaranteed to exist. For more information about the probabilistic method, we refer readers to [START_REF] Alon | The Probabilistic Method[END_REF]. Recent results have shown that there is a strong connection between probabilistic method and the compression sizes of encodings of mathematical objects, i.e. their Kolmogorov complexity, K:

If the probabilistic method can be used to prove the existence of an object, then bounds on its Kolmogorov complexity can be proven as well.

If there is a simple probability such that objects of a certain mathematical type occur with large probability, then there exists an object of that type that is simple, i.e. has low Kolmogorov complexity. More formally, if object x has P -probability of at least p of randomally occuring, then K(x) < log K(P ) -log p + .

The term is the amount of information that an encoding of the entire mathematical construct has with the halting sequence, which can obviously considered to be a negligible amount, except for exotic cases.

This inequality occurs through the application of the EL Theorem [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF]. Producing bounds of the Kolmogorov complexity of an object through probabilistic means is called Kolmogorov derandomization.

I'd recommend derandomization as an area of research for masters students or researchers who are interested in moving into algorithmic information theory. This is because the majority of the technical effort resides in the domain to which derandomization is applied.

Three Eggs from the Chicken

Future work involves finding instances of the probabilistic method and applying derandomization to them. In particular, the Lovász Local Lemma, [EL], has been particularly compatible with derandomization. We present the first proved consequence of LLL and show how it is compatible with three versions of derandomization, one that involves Kolmogorov complexity, one that involves resource bounded Kolmogorov complexity, and one involving games.

A hypergraph is a pair J = (V, E) of vertices V and edges E ⊆ P(V ). Thus each edge can connect ≥ 2 vertices. A hypergraph is k-regular of the size |e| = k for all edges e ∈ E. A 2regular hypergraph is just a simple graph. A valid C-coloring of a hypergraph (V, E) is a mapping f : V → {1, . . . , C} where every edge e ∈ E is not monochromatic |{f (v) : v ∈ e}| > 1. The following classic result is proven using LLL.

Theorem. (Probabilistic Method) Let G = (V, E) be a k-regular hypergraph. If for each edge f , there are at most 2 k-1 /e-1 edges h ∈ E such that h∩f = ∅, then there exists a valid 2-coloring of G.

We can now use derandomization, to produce bounds on the Kolmogorov complexity of the simpliest such 2-coloring of G.

Theorem A. (Kolmogorov Derandomization) Let J = (V, E) be a k-regular hypergraph with |E| = m. If, for each edge f , there are at most 2 k-1 /e -1 edges h ∈ E such that h ∩ f = ∅, then there exists a valid 2-coloring x of J with K(x) < log K(n) + 4me/2 k + I(J; H).

The term I(J; H) = K(J) -K(J|H) is the amount of mutual information that J has with the halting sequence H. We can now use resource derandomization to achieve bounds for the smallest time-bounded Kolmogorov complexity K t (x) = min{p : U (p) = x in t( x ) steps} of a 2-coloring of J.

Assumption. Crypto is the assumption that there exists a language in DTIME(2 O(n) ) that does not have size 2 o(n) circuits with Σ p 2 gates.

Theorem B. (Resource Bounded Derandomization) Assume Crypto. Let J n = (V, E) be a k(n)-regular hypergraph where |V | = n and |E| = m(n), uniformly polynomial time computable in n. Furthermore, for each edge f in J n there are at most 2 k(n)-1 /e -1 edges h ∈ E such that h ∩ f = ∅. Then there is a polynomial p, and a valid 2-coloring x of J n with K p (x) < 4m(n)e/2 k(n) + O(log n).

We define the following game involving hypergraphs. The player has access to a list of vertices and the goal of the player is to produce a valid 2-coloring of the hypergraph. We assume that for each edge f of the graph, there are at most 2 k-1 /e -1 edges h such that f ∩ h = ∅.

The game proceeds as follows. For the first round, environment gives the number of vertices to the player. The player has n vertices, each with starting color 1. At each subsequent turn, the environment sends to the player the edges which are monochromatic. The player can change the color of up to k vertices and sends these changes to the environment. The game ends when the player has a valid 2-coloring of the graph.

Theorem C. (Game Derandomization) For k ≥ 6, there exists a player p that can beat the environment q in (1 + )n/k turns, with Kolmogorov complextiy K(p) < log I(q; H) -log , where ∈ (0, 1).

Chapter 2

Conventions

As noted in the introduction, K(x|y) is the conditional prefix free Kolmogorov complexity. m(x) is the algorithmic probability. The function m is universal, in that for any computable probability P over {0, 1} * , O(1)m(x) > 2 -K(P ) P (x). Thus for set D ⊆ {0, 1} * , computable probability P , O(1)m(D) > 2 -K(P ) P (D). I(x; H) = K(x)-K(x|H) is the amount of information that the halting sequence H ∈ {0, 1} ∞ has about x. For some function t : N → N, the t-time bounded Kolmogorov complexity is K t (x) = min{ p : U (p) = x in time t( x )}. A probability is elementary, if it has finite support and rational values. The deficiency of randomness of x relative to a elementary probability measure Q is d(x|Q) = -log Q(x) -K(x|Q). We recall for a set D ⊆ {0, 1} * , m(D) = x∈D m(x). For the nonnegative real function f , we use < + f , > + f , and = + f to denote < f +O(1), > f -O(1), and = f ±O(1). We also use < log f and > log f to denote < f +O(log(f +1)) and > f -O(log(f + 1)), respectively. The following lemma is conservation of mutual information information with the halting sequence over deterministic processing.

Lemma 1 ( [START_REF] Epstein | The outlier theorem revisited[END_REF]) For partial computable f : {0, 1} * → {0, 1} * , I(f (a); H) < + I(a; H) + K(f ).

The following result is the EL Theorem [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF]. It was originally formulated as a statement about learning. However since that time, there has been several unexpected applications. In this paper, the EL Theorem is used for derandomization.

Theorem 1 (EL Theorem [Lev16,[START_REF] Epstein | On the algorithmic probability of sets[END_REF]) For finite D ⊂ {0, 1} * , -log max x∈D m(x) < log -log m(D) + I(D; H).

Lemma 2 (Symmetric Lovász Local Lemma) Let E 1 , . . . , E n be a collection of events such that ∀i : Pr[E i ] ≤ p. Suppose further that each event is dependent on at most d other events, and that ep(d + 1) ≤ 1. Then,

Pr i E i > 1 -1 d+1 n .
Chapter 3 15 Instances of Kolmogorov Derandomization

Continuous Measures

A continuous semi-measure Q is a function Q : {0, 1} * → R ≥0 , such that Q(∅) = 1 and for all x ∈ {0, 1} * , Q(x) ≥ Q(x0) + Q(x1). For prefix free set D, Q(D) = x∈D Q(x).
Let M be a largest, up to a multiplicative factor, lower semi-computable continuous semi-measure. That is, for all lower computable continuous semi-measures Q there is a constant c ∈ N where for all x ∈ {0, 1} * , cM(x) > Q(x). Thus for any lower computable continuous semi-measure W and prefix-free set S ⊂ {0, 1} * , -log M(S) < + K(W ) -log W (S), where K(W ) is the size of the smallest program that lower computes W . The monotone complexity of a finite prefix-free set G of finite strings is Km(G) def = min{ p : U (p) ∈ x y ∈ G}. Note that this differs from the usual definition of Km, in that our definition requires U to halt.

Theorem 2 ([Eps22]) For finite prefix-free set G ⊂ {0, 1} * , we have Km(G) < log -log M(G) + I(G; H).

Examples

In this section 22 examples of derandomization are given. Some use the Lovász Local Lemma, which is particularly suited for derandomization. There are 4 instances of games.

k-Sat

For a set of n Boolean variables x 1 , . . . , x n , a CNF formula φ is a conjunction

C 1 ∩ • • • ∩ C m of clauses. Each clause C j is a disjunction of k literals,
where each literal is a variable x i or its negation x i . Clauses C j and C l are said to intersect if there is some x i such that both clauses contain either

(x 1 ∨ x 3 ∨ x 5 ) ∧ (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 2 ∨ x 4 ∨ x 5 )
Figure 3.1: An example 3-Sat instance. Each clause contains 3 literals consisting of variables x i or their negations x i . An example satisfying assignment is x 1 = True, x 2 = True, x 3 = False, x 4 = False, x 5 = True.

x i or x i . A satisfying assignment is a setting of each x i to true or false that makes φ evaluate to true. An example of k-Sat can be seen in Figure 6.2.

Theorem 3 Let φ be a k-Sat instance of n variables and m clauses, with k ≥ 3. If each clause intersects at most (2 k /e) -1 other clauses, then there exists a satisfying assignment ψ of φ of complexity K(ψ) < log K(n) + 2em/2 k + I(φ; H).

Proof. The sample space is the set of all 2 n assigments, and for each clause C J , E j is the bad event "C j is not satisfied". Let p = 2 -k and d = (2 k /e) -1. Thus ∀j, Pr[E j ] ≤ p as each clause has size k and each E j is dependent on at most d other events by the intersection property. Thus since ep(d + 1), by the Lovász Local Lemma 6, we have that,

Pr   j E j   > 1 - 1 d + 1 m = 1 - e 2 k m . (3.1)
Let D ⊂ {0, 1} n be the set of all assignments that satisfy φ. K(D|φ) = O(1). Let P be the uniform measure over sequences of size n. By Equation 7.2, assuming k ≥ 3,

-log P (D) < -m log(1 -e/2 k ) < 2em/2 k .
Thus by Theorem 1 and Lemma 6, for k ≥ 3, there exists an assignment ψ ∈ D that satisfies φ with complexity

K(ψ) < log K(P ) -log P (D) + I(D; H) < log K(n) + 2em/2 k + I(φ; H).

Hypergraph-Coloring

In this section we show how to compress colorings of k-uniform hypergraph. A hypergraph is a pair J = (V, E) of vertices V and edges E ⊆ P(V ). Thus each edge can connect ≥ 2 vertices. A hypergraph is k-uniform of the size |e| = k for all edges e ∈ E. A 2-uniform hypergraph is just a simple graph. A valid C-coloring of a hypergraph (V, E) is a mapping f : V → {1, . . . , C} where every edge e ∈ E is not monochromatic |{f (v) : v ∈ e}| > 1. The goal of Hypergraph-Coloring with parameter k, is given a k uniform hypergraph, produce a coloring using the smallest amount of colors. Theorem 4 uses the union bound whereas Theorem 5 uses the Lovász Local Lemma.

Theorem 4 Every k-uniform hypergraph J = (V, E), |E| = n, |V | = m has a k-1 √ 2m coloring g where K(g) < log K(k, n, m) + I(J; H).
Proof. We randomly color every vertex v ∈ V using C = k-1 √ 2m colors. Let A e be the bad event that edge e is monochromatic. This event has probability:

Pr[A e ] = C • (1/C) k = (1/C) k-1 < 1/2m,
because there are C possible colors and each vertex has a 1/C chance of getting a particular color. We can get a union-bound over all m edges to find the bad probability.

Pr e∈E A e < e∈E Pr[A e ] < m • (1/2m) = 1/2. (3.2)
We let D ⊂ {0, 1} n log C be the set of all encodings of C colorings (so no edge in monochromatic. K(D|J) = O(1). Let P : {0, 1} * → R ≥0 be a probability measure over {0, 1} * , uniformly distributed over all x ∈ {0, 1} n log C that encode a C color assignment. P (D) > .5. By Theorem 1 and Lemma 1, there is a graph coloring g ∈ D where

K(g) < log K(P ) -log P (D) + I(D; H) < log K(k, m, n) + I(J; H).
The second result on k-hypergraph coloring uses Lovász Local Lemma.

Theorem 5 Let J = (V, E), |V | = n, |E| = m be a hypergraph and k = min f ∈E |f |, with k ≥ 3.
Assume for each edge f , there are at most

2 k-1 /e edges h ∈ E such that h ∩ f = ∅. Then for k ≥ 4, there is a 2-coloring g of G such that K(g) < log K(n)4me/2 k + I(J; H).
Proof. The case is degenerate for k = 1. Assume k ≥ 3. We will use the Lovász Local Lemma to get a lower bound on the probability that a random assignment of colors is a 2 coloring. We assume each vertex is colored black or white with equal probability. For each edge f ∈ E, we define E f to be the bad event "f is monochromatic". A valid 2-coloring exists iff Pr f E f > 0.

Let p = 1/2 k-1 and d = (2 k-1 /e) -1. For each f , Pr[E f ] ≤ p by the fact that f contains at least k vertices. Furthermore since f intersects at most d edges besides itself, E f is dependent on at most d of the other events. Therefore since ep(d + 1) = 1 we can apply the Lovász Local Lemma 6,

Pr   f E f   > 1 - 1 1 + d m = 1 - e 2 k-1 m . (3.3)
Let D = {0, 1} n be the set of all encoded 2 colorings of J. K(D|J) = O(1). Let P (x) = [ x = n]2 -n is the uniform distribution over sequences of length n. By Equation 3.3, assuming k ≥ 4

-log P (D) < -m log(1 -2e/2 k ) < 4me/2 k .
By Theorem 1 and Lemma 6, there exist a 2-coloring g of J such that for k ≥ 4, K(g) < log K(P ) -log P (D) + I(D; H) < log K(n) + 4me/2 k + I(J; H).

Vertex-Disjoint-Cycles

Proposition 1 (Mutual Independence Principle) Suppose that Z 1 , . . . Z m is an underlying sequence of independent events and suppose that each event A i is completely determined by some subset

S i ⊂ {Z 1 , . . . , Z m }. If S i ∩ S j = ∅ for j = j 1 , . . . , j k then A i is mutually independent of {A j 1 , . . . , A j k }.
This section deals with partitioning graphs into subgraphs such that each subgraph contains an independent cycle. An example partition can be seen in Figure 3 Proof. We partition the vertices of G into c = k/3 ln k components by assigning each vertex to a component chosen independently and uniformly at random. With positive probability, we show that every component contains a cycle. It is sufficient to prove that every vertex has an edge leading to another vertex in the same component. This implies that starting at any vertex there exists a path of arbitrary length that does not leave the component of the vertex, so a sufficiently long path must include a cycle. A bad event A v = {vertex v has no neighbor in the same component}. Thus

Pr[A v ] = (u,v)∈E Pr[u and v are in different components] = 1 - 1 c k < e -k/c ≤ e -3 ln k = k -3 .
x A v is determined by the component choices of itself and of its out neighbors N out (v) and these choices are independent. Thus by the Mutual Independence Principle, (Proposition 3) the dependency set of A v consist of those u that share a neighor with v, i.e., those u for which ({v} ∪ N (v)) ∩ ({u} ∪ N (u)) = 0. Thus the size of this dependency is at most d = (k + 1) 2 . Take d = (k + 1) 2 and p = k -3 , so ep(d + 1) = e(1 + (k + 1) 2 )/k 3 ≤ 1, holds for k ≥ 5. One can trivially find a partition of a k-regular graph when k < 5 because c = 1. Thus, noting that k ≥ 5,

Pr v∈G A v > 1 - 1 d + 1 n = 1 - 1 (k + 1) 2 + 1 n > 1 - 1 k 2 n .
(3.4)

-log P (D) < -n log(1 -1/k 2 ) < 2n/k 2 .
By Theorem 1 and Lemma 1, for large enough k, there exist a partitioning ∈ D of vertices into c = k/3 ln k components each containing a cycle that is vertex disjoint from the other cycles with complexity K( ) < log K(P ) -log P (D) + I(D; H) < log K(n, k) + 2n/k 2 + I(G; H).

Weakly-Frugal-Graph-Coloring

For an undirected graph G = (V, E), a k-coloring assignment f : V → {1, . . . , k} is a β-weakly frugal if for all neighbors of vertices v ∈ V contain at most β vertices with the same assignment. Note that a weakly frugal coloring assignment differs from a frugal coloring assignment, introduced in [START_REF] Hind | Colouring a graph frugally[END_REF], by the fact that the former can have two adjacent vertices with the same color.

Theorem 7 For graph G = (V, E), with |V | = n, with max degree ∆ > 2e there is a β-weakly frugal coloring assignment f , with β < ∆, using Q ≥ ∆ 1+4/β /2 colors with complexity K(f

) < log K(n, Q) + 2n/β + I((G, β, Q); H).
Proof. This proof is a modification of the proof in [START_REF] Hind | Colouring a graph frugally[END_REF], except the restriction is relaxed to weakly-frugal coloring. Let us say each vertex is assigned one of Q colors with uniform randomness. For vertices {u 1 , . . . , u β+1 } that are in the neighborhood of a vertex v ∈ V , let B u 1 ,...,u β+1 be the bad event that the vertices are the same color. Pr[B u 1 ,...,u β+1 ] = p = 1/Q β . Each such bad event is dependent on at most d = (β + 1)∆ ∆ β other events. There are at most m = n ∆ β+1 such events. The requirement that ep(d + 1) ≤ 1 of the Lovász Local Lemma is fulfilled, because Let D ⊂ {0, 1} n log Q be encodings of all β-weakly frugal coloring of G using Q colors. K(D|G, Q, β) = O(1). Let P be uniform distribution over all Q-color assignments to n vertices. -log P (D) < + 2n/β. By Theorem 1 and Lemma 6, we have a β-weakly frugal color assignment f ∈ D of G using Q colors such that

ep(d + 1) =e 1 Q β 1 + (β + 1)∆ ∆ β ≤e 1 Q β 1 + (β + 1)(∆ β+2 /β!) ≤e 1 Q β (1 + (∆ β+3 /β!)) ≤ 1 Q β (∆ β+4 /β!)) ≤ 1 Q β ∆ β+4 2 -β ≤1. By Lovász Local Lemma 6, -log Pr   u 1 ,...,u β+1 B u 1 ,...,u β+1   < -m log 1 - 1 d + 1 <2m 1 - 1 d + 1 <2n ∆ β + 1 / 1 + (β + 1)∆ ∆ β <2n ∆ β + 1 / (β + 1)∆ ∆ β <2n/(β + 1).
K(f ) < log K(P ) -log P (D) + I(D; H) < log K(n, Q) + 2n/β + I((G, Q, β); H).

Graph-Coloring

For graph G = (V, E), with undirected edges, a k-coloring is a function f : V → {1, . . . , k} such that if (v, u) ∈ E, then f (v) = f (u). An example graph coloring can be seen in Figure 3.3 Theorem 8 For graph G = (V, E), |V | = n with max degree d, there is a k coloring f with 2d ≤ k, and K(f

) < log K(n, k) + 2nd/k + I((G, k); H).
Proof. Let us say we randomly assign a color to each vertex. The probability that the color of the ith vertex does not conflict with the previous coloring is at least (k -d)/k. Thus the probability of a proper coloring is ≥ ((k -d)/k) n . Let D ⊆ {0, 1} n log k be all encoded proper k colorings of G. K(D|G, k) = O(1). Let P : {0, 1} * → R ≥0 be a probability measure that is the uniform distribution over all possible color assignments. Thus, assuming d/k ≤ .5,

-log P (D) ≤ -n log(1 -d/k) ≤ 2nd/k.
Thus by Theorem 1 and Lemma 1, there is a coloring f ∈ D with

K(f ) < log -log m(D) + I(D; H) < log K(P ) -log P (D) + I(D; H) < log K(n, k) + 2nd/k + I((G, k); H).

Max-Cut

Imagine a graph G = (E, V ), |V | = n, consisting of vertices V and undirected edges E, and a weight ω e for each edge e ∈ E. Let ω = e∈E ω e be the combined weight of all edges. The goal is to find a partition (A, B) of the vertices into two groups that maximizes the total weight of the edges between them.

Theorem 9 There is a cut f of G that is 1/3th optimal and K(f ) < log K(n) + I(G; H).

Proof. Imagine the algorithm that on receipt of a vertex, randomly places it into A or B with equal probability. Then the expected weight of the cut is

E   e∈E(A,B) ω e   = e∈E ω e Pr(e ∈ E(A, B)) = 1 2 ω.
This means the expected weight of the cut is at least half the weight of the maximum cut. Some simple math results in the fact that Pr e∈E(A,B) ω e > ω/3 ≥ 1/4. We can encode a cut into a binary string of x length n, where x[i] = 1, if the ith vertex is in A. Let P be the uniform distribution over strings of size n. Let D ⊂ {0, 1} n consist of all encoded cuts that are at least 1/3 optimal. K(D|G) = O(1) and P (D) ≥ .25. By Theorem 1 and Lemma 1,

min f ∈D K(f ) < log K(P ) -log P (D) + I(D; H) < log K(n) + I(G; H).

Max-3Sat

This problem consists of a boolean formula f in conjunctive normal form, comprised of m clauses, each consisting of a disjunction of 3 literals. Each literal is either a variable or the negation of a variable. We assume that no literal (including its negation) appears more than once in the same clause. There are n variables. The goal is to find an assignment of variables that satisfies as many clauses as possible.

Theorem 10 There is an assignment x that is 6/7th optimal and has complexity K(x) < log K(m)+ I(f ; H).

Proof. The randomized approximation algorithm is as follows. The variables are assigned true or false with equal probability. Let Y i be the random variable that clause i is satisfied. Thus the probability that clause Y i is satisfied is 7/8. So the total expected number of satisfied clauses is 7m/8, which is 7/8 of optimal. Some simple math shows the probability that number of satified clauses is > 6m/7 is at least 1/8. Let x ∈ {0, 1} n encode an assignment of n variables, where

x[i] = 1 if variable i is true. Let D ⊂ {0, 1} n
encode all assignments that are 6/7th optimal. Let P be the uniform distribution over strings of length n. K(D|f ) = O(1) and P (D) ≥ 1/8. By Theorem 1 and Lemma 1,

min x∈D K(x) < log K(P ) -log P (D) + I(D; H) < log K(n) + I(f ; H). For a vector v = (v 1 , . . . , v n ) ∈ R n , v ∞ = max i |V i |. Binary matrix M is a matrix whose values are either 0 or 1. The goal of Binary Matrix, is given M , to find a vector b ∈ {-1, +1} n that minimizes M b ∞ . Theorem 11 Given n × n binary matrix M , there is a vector b = {-1, +1} n such that M b ∞ ≤ 4 √ n ln n and K(b) < log K(n) + I(M ; H). Proof. Let v = (v 1 , . . . , v n ) be a row of M . Choose a random b = (b 1 , . . . , b n ) ∈ {-1, +1} n . Let i 1 , . . . , i m be the indices such that v i j = 1. Thus Y = v, b = n i=1 v i b i = m j=1 v i j b i j = m j=1 b i j . E[Y ] = E[ v, b ] = E i v i b i = i E[v i b i ] = v i E[b i ] = 0.
By the Chernoff inequality and the symmetry Y , for τ = 4 √ n ln n,

Pr[|Y | ≥ τ ] = 2 Pr[v • b ≥ τ ] = 2 Pr   m j=1 b i j ≥ τ   ≤ 2 exp - τ 2 2m = 2 exp -8 n ln n m ≤ 2n -8 .
Thus, the probability that any entry in M b exceeds 4 √ n ln n is smaller than 2n -7 . Thus, with probability 1 -2n -7 , all the entries of M b have value smaller than 4 √ n ln n. Let P : {0, 1} * → R ≥0 , be the uniform measure over string of length n, with

P (x) = [ x = n]2 -n . Let D consist of all strings that encode vectors b x ∈ {-1, +1} n in the natural way such that M b x ∞ ≤ 4 √ n ln n. K(D|M ) = O(1)
. Thus by the above reasoning P (D) ≥ 1 -2n -7 > 0.5. By Theorem 1 and Lemma 1, there exists an x ∈ D, such that

K(x) < log K(P ) -log P (D) + I(D; H) < log K(n) + I(M ; H).
Thus there exists a b x ∈ {-1, +1} n that satisfies the theorem statement. We provide another derandomization example using balancing vectors.

Theorem 12 Let v = v 1 , . . . , v n ∈ R n , all |v i | = 1, Then there exist = 1 , . . . , n = ±1 such that | 1 v 1 + • • • + n v n | ≤ √ 2n and K({ }) < log K(n) + I(v; H).
Proof. Let 1 , . . . , n be selected uniformly and independently from {-1, +1}. Set

X = | v 1 + • • • + n v n | 2 . Then X = i=1 n j=1 i j v i • v j . So E[X] = n i=1 n j=1 v i • v j E[ i j ]
When i = j, E[ i j ] = E[ i ]E[ j ] = 0. When i = j, E[ 2 i ] = 1, so E[X] = n i=1 v i • v i = n So Pr[X ≤ 2n] ≥ 0.5. Let D ⊆ {0, 1}
n consist of sequences of length n, each encoding an assignment of 1 to n in the natural way, such that the assignment of results in an X ≤ 2n. K(D|v) = O(1).

Let P be the uniform measure over sequences of length n. By the above reasoning P (D) ≥ 0.5. By Theorem 1 and Lemma 1, there is an assignment ∈ D, such that K( )

< log K(P ) -log P (D) + I(D; H) < log K(n)+I(v; H). This assignment has X ≤ 2n. Thus | 1 v 1 +. . . n v n | ≤ √ 2n
, satisfying the theorem.

Parallel-Routing

The Parallel-Routing problem consists of (G, d), a directed graph G = (N, V ) and a set of destinations d : N → N . Each node represents a processor i in a network containing a packet v i destined for another processor d(i) in the network. The packet moves along a route represented by a path in G. During its transmission, a packet may have to wait at an intermediate node because the node is busy transmitting another packet. Each node contains a separate queue for each of its links and follows a FIFO queuing disciple to route packets, with ties handled arbitrarily. The goal of Parallel-Routing is to provide N routes from i ∈ N to d(i) that minimize lag time.

We restrict graphs to Boolean Hypercube networks, which is popular for parallel processing. The cube network contains N = 2 n processing elements/nodes and is connected in the following manner. if (i 0 , . . . , i n-1 ) and (j 0 , . . . , j n-1 ) are binary representation of node i and node j, then there exist directed edges (i, j) and (j, i) between the nodes if and only if the binary representation differ in exactly one position. An example Boolean Hypercube can be found in Figure 3.4.

One set of solutions, called oblivious algrithms satisfies the following property: a route followed by v i depends on d(i) alone, and not on d(j) for any j = i. We focus our attention on a 2 phase oblivious routing algorithm, Two-Phase. Under this scheme, packet v i executes the following two phases independently of all the other packets. The method that the routes use for each phase is the bit-fixing routing strategy. Its description is as follows. To go from i to σ(i): one scans the bits of σ(i) from left to right, and compares them with i. One sends v i out of the current node along the edge corresponding to the left-most bit in which the current position and σ(i) differ. Thus going from (1011) to (0000), the packet would pass through (0011) and then (0001).

Theorem 13 Given a Parallel-Routing instance (G, d), there is a set of intermediate destinations σ : N → {0, 1} n for each i such that every packet i using σ(i) and the Two-Phase algorithm reaches its destination in at most 14n steps and K(σ) < log I(G, d; H).

Proof. By Theorem 47 in [START_REF] Motwani | Randomized Algorithms[END_REF], if the intermediate destinations are chosen randomly, with probability least 1 -(1/N ), every packet reaches its destination in 14n or fewer steps. Let D ⊂ {0, 1} nN be the set of all intermediate destinations σ ∈ D such that the lag time of instance (G, d)

using σ is ≤ 14n. Let µ : {0, 1} * → R ≥0 be the uniform continuous semi-measure, with µ(∅) = 1, µ(x) = 2 -x . Thus µ(D) ≥ 0.5. K(D|(G, d)) = O(1). Theorem 2 and Lemma 1 results in Km(D) < log -log M(D) + I(D; H) < log -log µ(D) + I((G, d); H) < log I((G, d); H).
Thus using y x ∈ D that realizes Km(D), one can construct a function σ : N → {0, 1} n which produces the desired intermediate destinations, and K(σ) < + K(y) < log I((G, d); H).

Independent-Set

An independent set in a graph G is a set of vertices with no edges between then, as shown in Figure 3.5. The Independent-Set problem consists of an undirected graph G and the goal is to find the largest independent set of that G.

Theorem 14 For a graph G on n vertices with m edges, there exists an independent set S of size 0.75 √ n -2m/n and complexity

< log K(n, m) + 4(log n)(m/n) + I(G; H).
Proof. We use a modification of the algorithm in the proof of Theorem 6.5 in [START_REF] Mitzenmacher | Probability and Computing: Randomized Algorithms and Probabilistic Analysis[END_REF]. The randomized algorithm A is as follows.

1. Delete each vertex (along with its incident edges) independently with probability 1 -p.

2. For each remaining edge, remove it and one of its adjacent vertices.

For X, the number of vertices that survive the first round E[X] = np. Let Y be the number of edges that survive the first step, E[Y ] = mp 2 . The second steps removes at most Y vertices. The output is an independent set of size at least

E[X -Y ] = np -mp 2 . Let p = 1/ √ n. Thus E[X] = √ n, E[Y ] = m/n, and E[X -Y ] = √ n -m/n. By the Markov inequality, Pr[Y < 2m/n] > 1/2. By the Hoeffding's inequality, Pr[X ≤ 0.75 √ n] ≤ e -2 * (0.75) 2 (np) 2 /n ≤ e -2(.75 2 )(n * n -.5 ) 2 /n ≤ e -2 * 0.5 = e -1 . For a sequence x ∈ {0, 1} * , x [1] = |{i : x[i] = 1}| and x [0] = x -x 1 . Let P : {0, 1} * → R ≥0 be a computable probability, where for a string x ∈ {0, 1} n , P (x) = (1/ √ n) x [1] (1 -1/ √ n) x [0]
. Thus each x represents a selection of vertices selected according to the randomized algorithm A. Let D ⊆ {0, 1} n be the set consists of all sequences x such that the X variable resultant from x is

|X x | > 0.75 √ n and the Y variable resultant from algorithm A is |Y x | ≤ 2m/n. Thus P (D) ≥ (1 -e -1 ) + 1/2 -1 > 1/10. Furthermore D can be constructed from G, with K(D|G) = O(1)
. By Theorem 1 and Lemma 1, there exists an x ∈ D, with

K(x) < log K(P ) -log P (D) + I(D; H) < log K(n) + I(G; H).
In order for x to represent an independent set, the second step of algorithm A needs to be applied. In this case there are < 2m/n vertices that needs to be removed. Thus a modification x that has these vertices deleted represents an independent set.

K(x ) < log K(x, n, m) + (2 log n)(2m/n) < log K(n, m) + (4 log n)(m/n) + I(D; H) < log K(n, m) + (4 log n)(m/n) + I(G; H). This independent set has X x > 0.75 √ n and Y x < 2m/n, it size is ≥ 0.75 √ n -2m/n.

Dominating-Set

A dominating-set of an undirected graph G = (E, V ) on n vertices is a set U ⊆ V such that every vertex v ∈ V -U has at least one neighbor in U . An example of a dominating set can be seen in Figure 3.6.

Theorem 15 Every graph G = (V, E), |V | = n with min degree δ > 1 has a dominating set U of size ≤ 3n 1+ln(δ+1) δ+1 and complexity K(U ) < log K(n, δ) + 6(n log n)/(δ + 1) + I(G; H). Proof. Let p ∈ [0, 1].
Let the vertices of V be picked randomly and independently, each with probability p. Let X be the random set of all vertices picked. δ+1) . We set p = ln(δ + 1)/(δ + 1). Pr[X ≤ 3n ln(δ + 1)/(δ + 1)] ≥ 2/3. Pr[Y X ≤ 3n/(δ + 1)] ≥ 2/3. Thus the probability of the previous two events is ≥ 1/3. Let D ⊆ {0, 1} n be the set consisting of all sequences x ∈ {0, 1} n where x[i] = 1 indicates vertex i was selected, such that the X variable resultant from x is |X x | ≤ 3n ln(δ + 1)/(δ + 1)] and the Y x resultant variable is |Y x | ≤ 3n/(δ + 1). Furthermore D can be constructed from G, with K(D|G) = O(1). Let P : {0, 1} * → R ≥0 be a probability measure over x ∈ {0, 1} n , where

E[|X|] = np. Let Y = Y X be the random set of all vertices V -X that do not have a neighbor in X. Pr(v ∈ Y X ) ≤ (1 -p) δ+1 . Thus E[|Y X | ≤ n(1 -p) δ+1 ≤ ne -p(
P (x) = n i=1 (px[i] + (1 -p)(1 -x[i]))
. By definition of D, P (D) ≥ 1/3. Furthermore by Theorem 1 and Lemma 1, there is a subset of vertices x ∈ D, x ⊆ V , with

K(x) < log K(P ) -log P (D) + I(D; H) < log K(n, δ) + I(G; H).
The sequence x represent the first step, however the set Y x needs to be added to make x a dominating steps. Thus 3n/(δ + 1) vertices needs to be added, each can be encoded by (2 log n) bits. Thus a dominating set x of G exists of size ≤ 3n 1+ln(δ+1) δ+1 such that

K(x ) < log K(n, δ) + 6(n log n)/(δ + 1) + I(G; H).

Set-Membership

For a set G ⊆ {0, 1} , a function f : {0, 1} * → {0, 1} is a partial checker for G, if f (x) = 1 if x ∈ G. We use U to denote the uniform distribution over {0, 1} . Error(G, f ) = Pr x∼U [f (x) = 1, x ∈ G]. The goal of Set-Membership, is given a set G ⊆ {0, 1} , what is the simplest partial checker f for G that reduces Error(G, f ). Theorem 16 For large enough n, given G ⊆ {0, 1} , |G| = m, there is a partial checker f such that Error(f, G) ≤ 0.878 n/m and K(f ) < log K(n, k, ) + n + I((G, n, k); H).
Proof. We derandomize the Bloom filter algorithm [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF]. Let there be k random functions h i : {0, 1} → {1, . . . , n}, where each h i maps each input x ∈ {0, 1} to its range with uniform probability. We start with a string v = 0 n . For each member x ∈ G, and i ∈ {1, . . . , k}, v[h i (x)] is set to 1. Thus the functions h i serve as a way to test membership of G. An example of the Bloom filter can be seen in Figure 3.7. If x ∈ G, then all the indicator functions h i would be one. The probability that a specific bit is 0 is

p = 1 - 1 n km .
Let X be the number of bins that are 0. Due to [START_REF] Mitzenmacher | Probability and Computing: Randomized Algorithms and Probabilistic Analysis[END_REF], Thus for proper choice of k determined later, for large enough n, the right hand side of the above inequality is less than 0.5. Thus with probability > .5, the expected false positive rate, r, that is

Pr(|X -np | ≥ n) ≤ 2e √ ne -n 2 /3p .
x ∈ {0, 1} , x ∈ G, h i (x) = 1, for all i ∈ {1, . . . , k} is less than r ≤(1 -.9p ) k = 1 -.9 1 - 1 n km k ≤ 1 -.9e -km/n k .
Setting k = n/m , with probability ≥ 1/2, r ≤ (1 -.5e -2 ) m/n ≤ 0.878 m/n . Furthermore, for large enough n, p > .5e -n/m (m/n) ≥ .5e -2 , which can be plugged back into Equation 3.5.

Let F ⊂ {0, 1} * consist of all encodings of k hash functions h i : {0, 1} → {1, . . . , n}. Let F ⊆ F consist of all hash functions such that the false positive rate r is ≤ 0.878 m/n . Let P be the uniform distribution over F . By the above reasoning, for large enough n, P

(F ) > 1/2. K(F |G, k, n) = O(1)
. By Theorem 1 and Lemma 1, there is an h ∈ F such that

K(h) < log K(P ) -log P (F ) + I(F ; H) < log K(n, k, ) + I((G, n, k); H).
Thus h represents a set of k deterministic hash functions. Let x be the Bloom filter using h on G. Using x and h, one can define a partial checker f that is a Bloom filter such that Error(f, G) ≤ 0.878 n/m . Furthermore,

K(f ) < log K(x, h) < log K(n, k, ) + n + I((G, n, k); H).

Latin-Transversal

Let A = (a i ) be an n × n matrix with integer entries. A permutation π is called a Latin Transversal if the entries a iπ(i) (1 ≤ i ≤ n) are all distinct. An example Latin Transversal, where each integer occurs exactly 4 times, can be seen in Figure 3.8 Lemma 3 (Lopsided Lovász Local Lemma [START_REF] Erdös | Lopsided lovász local lemma and latin transversals[END_REF]) Let E 1 , . . . , E n be a collection of events with dependency graph G = (V, E). Suppose Pr E i j∈S E j ≤ Pr(E i ), for all i, S ⊂ V with no j ∈ S adjacent to i. Suppose all events have probability at most p, G has degree at most d, and

4dp ≤ 1. Then Pr( i E i ) ≥ (1 -2p) n .
Theorem 17 Suppose k ≤ (n -1)/16 and suppose integers appears in exactly k entries of n × n matrix A. Then for n ≥ 3, A has a Latin Traversal τ of complexity K(τ ) < log K(n) + 4(k -1) + I(A; H).

Proof. Let π be a random permutation {1, 2, . . . , n}, chosen according to a uniform distribution P among all possible n! permutations. Define T by the set of all ordered fourtuples (i, j, i , j ) with i < i , j = j , and a ij = a i j . For each (i, j, i , j ) ∈ T , let A iji j denote the bad event that π(i) = j and π(i ) = (j ). Thus A iji j is the bad event that the random permutation has a conflict at (i, j) and (i , j ).

Clearly P (A iji j ) = 1/n(n -1). The existence of a Latin Transversal is equivalent to the statement that with positive probability, none of these events hold. We define a symmetric digraph G on the vertex set T by making (i, j, i , j ) adjacent to (p, q, p , q ) if {i, i } ∩ {p, p } = ∅ or {j, j } ∩ {q, q } = ∅. Thus these two fourtuples are not adjacent iff the four cells (i, j), (i , j ), (p, q) and (p , q ) occupy four distinct rows and columns of A.

The maximum degree of G is less than 4nk ≤ d because for a given (i, j, i , j ) ∈ T there are at most 4n choices of (s, t) with either s ∈ {i, i } or t ∈ {j, j } and for each of these choices of (s, t) there are less than k choices for (s , t ) = (s, t) with a st = a s t . Each fourtuple (s, t, s , t ) can be uniquely represented as (p, q, p , q ) with p < p . Since 4dp ≤ 16nk/(n(n -1) ≤ 1, by the Lopsided Lovász Local Lemma, 3, the desired bounds can be achieved if we can show that Pr A iji j S A pqp q ≤ 1/n(n -1), for any (i, j, i , j ) ∈ T and any subset S of T which are not-adjacent in G to (i, j, i , j ). By symmetry we can assume i = j = 1, i = j = 2. A permutation π is good if it satisfies S A pqp q and let S ij denote the set of all good permutations π satisfying π(1) = i and π(2

) = j. |S 12 | ≤ |S ij | for all i ≤ j.
Indeed suppose first that i, j > 2. For each good π ∈ S 12 define a permutation π * as follows. Suppose π(x) = i and π(y) = j. Then define π * (1) = i, π * (2) = j, π * (x) = 1, π * (y) = 2 and π * (t) = π(t) for all t = 1, 2, x, y. One can easily check that π * is good, since the cells (1, i), (2, j), (x, 1), (y, 2) are not part of any (p, q, p , q ) ∈ S. Thus π * ∈ S ij and since the mapping π → π * is injective |S 12 | ≤ |S ij |. One can define an injection mappings showing that |S 12 | ≤ |S ij | even when {i, j} ∩ {1, 2} = ∅. If follows that Pr A 1122 ∩ S A pqp q ≤ Pr A 1i2j ∩ S A pqp q and hence Pr A 1122 S A pqp q ≤ 1/n(n -1).

The number of bad events A iji j is n 2 k k 2 , as there are n 2 /k distinct numbers, and each number appears k times. Thus by the Lopsided Lovász Local Lemma 3, for n ≥ 3,

Pr i A iji j ≥ (1 -2/n(n -1)) n 2 k ( k 2 ) -log Pr i A iji j < n 2 k k 2 log(1 -2/n(n -1)) < 2 2n 2 kn(n -1) k 2 < 8 k k 2 ≤ 4(k -1).
(3.6)

Let D ⊂ {0, 1} * be all encodings of permutations of A that are Latin Transversals. K(D|A) = O(1).

We recall that P is the uniform distribution over all permutation of A. By the Equation 3.6, -log P (D) < 4(k -1). Thus by Theorem 1 and Lemma 1, for n ≥ 3, there exists a permutation τ ∈ D that is a Latin Transversal and has complexity K(τ ) < log K(P ) -log P (D) + I(D; H) < log K(n) + 4(k -1) + I(A; H).

Function-Minimization

Given computable functions {f i } n i=1 , where each f i : N → N∪∞, the goal of Function-Minimization is to find numbers {x i } n i=1 , that minimizes n i=1 f i (x i ). Let p : N → R ≥0 be a computable probability measure where E p [f i ] ∈ R for all i = 1, . . . , n. We define a computable probability

P : {0, 1} * → R ≥0 where P ( a 1 a 2 . . . a n ) = n i=1 p(a i ). K(P ) < + K(p, n).
Let D be a (potentially infinite) set of strings where x ∈ D iff x = a 1 a 2 . . . a n and

n i=1 f i (a i ) ≤     2 {b i } n i=1 p(b i ) n i=1 f i (b i )     = 2 n i=1 E p [f i ] . Let τ = 2 n i=1 E p [f i ] .
< log K(p, n) + I((p, {f i }, τ ); H).
Thus given any computable probability p and functions {f i } n i=1 , there are numbers

{x i } n i=1 such that n i=1 f (x i ) ≤ 2 n i=1 E p [f i ] = τ and K({x i } n i=1 ) < log K(n, P ) + I((p, {f i }, τ ); H).
Note that there is a version of these results when the functions are uncomputable, but this is out of the scope of the paper.

An instance of this formulation is as follows. Let n = 1 and

f 1 (a) = [a > 2 m ]∞ + [a ≤ 2 m ]2 m-K(a|m) . Let p(a) = [a ≤ 2 m ]2 -m . Thus this example proves there exists a number x such that f 1 (x) ≤ 2E p [f 1 ] ≤ 2. Furthermore K(x) < log K(p) + I((p, f 1 ); H) < log K(m) + I((m, f 1 ); H). But if f 1 (x) ≤ 2,
by the definition of f 1 , this means K(x) ≥ m -1. This means m < log I((m, f 1 ); H) < log I(f 1 ; H). This makes sense because f 1 is a deficiency of randomness function and therefore m < log K(f 1 ) and K(f 1 |H) < + K(m).

Super-Set

Given a finite set S ⊆ {0, 1} n , the goal of Super-Set is to find a set T ⊇ S, T ⊆ {0, 1} n that minimizes |T |.

Theorem 18 Given m ≤ n, S ⊆ {0, 1} n , |S| < 2 n-m-1 there exists a T ⊇ S, T ⊆ {0, 1} n |T | = 2 n-m , K(T ) < log K(n, m) + (m + 1)|S| + I((S, m); H).

Proof. Let P : {0, 1} * → R ≥0 be the the uniform distribution over all sequences of size 2 n that have exactly 2 n-m 1s. Let D ⊂ {0, 1} 2 n consist of all sequences x R ∈ {0, 1} 2 n that encode sets R ⊆ {0, 1} n in the natural way such that R ⊇ S and |R| = 2 m-n . Thus if x ∈ D then x has 2 n-m 1s.

P (D) = 2 n-m 2 n 2 n-m-1 2 n -1 . . . 2 n-m -|S| 2 n -|S| ≥ 2 n-m -|S| 2 n -|S| |S| ≥ 2 n-m-1 2 n |S| = 2 -(m+1)|S| . K(D|(S, m)) = O(1).
Thus by Theorem 1 and Lemma 1, there exists a t ∈ D, such that K(t)

< log K(P ) -log P (D) + I(D; H) < log K(n, m) + (m + 1)|S| + I((S, m); H). This t encodes a set T ⊇ S, T ⊆ {0, 1} n such that |T | = 2 n-m .
Chapter 4

Classical Channels

There are deep connections between classical information theory and algorithmic information theory, with many theorems of the former appearing in an algorithmic form in the latter. In this section we revisit this connection. In particular we prove properties about the compression size of shared codebooks using Kolmogorov derandomization. A standard setup in information theory is two parties Alice and Bob who want to communicate over a noisy channel and share a codebook over a noiseless channel. However one might ask is how many bits did it take to communicate the codebook? By using derandomization, the tradeoff between codebook complexity and communication capacity can be proven.

Definition 1 (Discrete Memoryless Channel) The input and output alphabets X and Y are finite. The channel (X , p(y|x), Y) is represented by a conditional probability distribution p(y|x). To send multiple symbols, we have p(y n |x n ) = n i=1 p(y i |x i ). The capacity of channel with respect to a distribution Q over X is C Q = I(X : Y ) where random variables (X, Y ) are distributed according to Q(x)p(y|x).

The term I is the mutual information between random variables.

Definition 2 (Codebook) A (M, n) codebook for channel (X , p(y|x), Y) contains the following:

1. An encoder Enc n : {1, . . . , M } → X n .

A decoder Dec

n : Y n → {1, . . . , M }.
The rate of the codebook is R = log M n . The conditional probability of error is

λ i = yn p(y n |x n = Enc(i))[Dec(y n ) = i],
where [•] is the indicator function. The average error rate of the codebook with respect to a fixed channel p is P

(n) e = 1 M M i=1 λ i .
It is the probability that, given the uniform distribution over {1, . . . , M } for the sending symbols, the receiver decodes a symbol different from the encoded one.

This section shows the following high level description of a communication scheme is possible: there is a sender Alice and a receiver Bob that communicate through a noisy memoryless discrete channel and Alice can send a codebook to Bob once on a side noiseless channel. Bob has oracle acess to the channel function p(y|x) but Alice does not. Given a computable distribution Q over the input alphabet, and assuming the channel is non-exotic, Alice can hypothetically send ∼K(Q) bits plus some encoded parameters describing a codebook to Bob on the side channel. Then Alice and Bob can communicate with any rate R less than the capacity C Q over the noisy channel. This setup is formalized with Theorem 20. To prove this theorem, some results are needed from classical information theory.

Jointly Typical Sequences

We need the following definition and theorem, which can be found in [START_REF] Cover | Elements of Information Theory[END_REF], in the proof of Theorem 20. H(X) is the entropy of random variable X, and I(X : Y ) is the mutual information between random variables X and Y .

Definition 3 The set A

(n) of jointly typical sequences {(x n , y n )} with respect to the distribution p(x, y) is the set of n-sequences with empirical entropies -close to the true entropies. X and Y are the finite discrete alphabet of random variables X and Y . Let p(x n , y n ) = n i=1 p(x i , y i ).

A (n) ={(x n , y n ) ∈ X n × Y n : - 1 n log p(x n ) -H(X) < , - 1 n log p(y n ) -H(Y ) < , - 1 n log p(x n , y n ) -H(X, Y ) < .
The following theorem details properties about the set A (n) . A proof for it can be found in [START_REF] Cover | Elements of Information Theory[END_REF].

Theorem 19 (Joint AEP) Let (X n , Y n ) be sequences of length n drawn i.i.d. according to p(x n , y n ) = n i=1 p(x i , y i ). Then 1. Pr (X n , Y n ) ∈ A (n) → 1 -o(1).
2. If ( Xn , Ỹ n ) ∼ p(x n )p(y n )( Xn and Ỹ n are independent with the same marginals as p(x n , y n )), then Pr ( Xn , Ỹ n ) ∈ A (n) ≤ 2 -nI(X:Y )-3 .

Naive Sender Paradigm

Theorem 20 For channel C = (X , p(y|x), Y) and every computable distribution Q over X , for every rate R < C Q , there is a (2 nR , n) codebook (Enc n , Dec n ) with rate R and average error rate o(1) such that there is a program p with p < log K(n, R, Q) + I((n, R, Q, C); H) and

U (p, x) = Enc n (x), U (p, C, x) = Dec n (x).
Proof. We start by generating a (2 nR , n) code randomly according to distribution Q. We generate 2 nR codewords x ∈ X independently according to the distribution

Q(x n ) = n i=1 p(x i ).
The codewords can be represented as rows of a matrix

C =    x 1 (1)
x 2 (1) . . .

x n (1) . . . . . . . . . . . .

x 1 (2 nR ) x 2 (2 nR ) . . . x n (2 nR )   
Each entry is generated i.i.d according to Q(x), with

Pr(C) = 2 nR w=1 n i=1 p(x i (w)).
Consider the following algorithm for encoding and decoding a message.

1. A random code C is generated according to Q(x).

2. The code C is sent to both the sender and the receiver. Only the receiver is assumed to know the channel transition matrix p(y|x) for the channel. This differs from the standard literature, which assumes knowledge of p by the sender.

3. A message W is chosen according to the uniform distribution.

Pr(W = w) = 2 -nR , w = 1, 2, . . . , 2 nR .

4. The wth codeword X n (w) corresponding to the wth row of C is sent over the channel.

5. The receiver receives a sequence Y n according to the distribution

P (y n |x n (w)) = n i=1 p(y i |x i (w)).
6. The receiver decares that the index Ŵ was sent if the following conditions are satisfied:

• (X n ( Ŵ ), Y n ) is jointly typical, i.e. (X n ( Ŵ ), Y n ) ∈ A (n) .
• There is no other index W = Ŵ such that (X n (W ), Y n ) ∈ A (n) .

If no such Ŵ exists or if there are more than one, an error is declared, and the decoder outputs 0.

7. There is a decoding error if Ŵ = W . Let E be this event.

We now analyze the probability of the error with respect to the random codebook C.

Pr(E) = C Pr(C)P (n) e (C) = C Pr(C) 1 2 nR 2 nR w=1 λ w (C) = 1 2 nR 2 nR w=1 C Pr(C)λ w (C) = C Pr(C)λ 1 (C) (4.1)
= Pr(E|W = 1), where Equation 4.1 is due to symmetry of the code construction. We define

E i = {(X n (i), Y n ) ∈ A (n) }, i ∈ {1, 2, . . . , 2 nR }.
So E i is the event that the ith code and Y n are jointly typical, noting that Y n is the result of sending the first codeword X n (1) over the channel. So

Pr(E|W = 1) = P (E c 1 ∪ E 2 ∪ E 3 . . . E 2 nR |W = 1) ≤ P (E c 1 |W = 1) + 2 nR i=2 P (E i |W = 1).
Due to the code generation procedure, X n (1) and X n (i) are independent for i = 1, and therefore, so are Y n and X n (i). Due to Theorem 19 (2), the probability that X n (i) and Y n are jointly typical is ≤ 2 -n(I(X;Y )-3 ) , where random variables X and Y are distributed acording to Q(x)p(y|x). So by Theorem 19 (1), for sufficiently large n,

Pr(E) = Pr(E|W = 1) ≤ P (E c 1 |W = 1) + 2 nR i=2 P (E i |W = 1) ≤ + 2 nR i=2 2 -n(I(X:Y )-3 ) = + 2 nR-1 2 -n(I(X:Y )-3 ) ≤ + 2 3n 2 -n(I(X:Y )-R) ≤ 2 , under the condition R < I(X : Y )-3 = C Q -3 . Hence if R < C Q we can
choose an and n so the average probability of error, averaged over codebooks is less than 2 . We now remove the average over codebooks. Since the average error rate P e (C) is small, there exists at least one codebook C * with a small average probability of error, with

Pr(E|C * ) = 1 2 nR 2 Rn i=1 λ i (C * ) ≤ 2 .
Connection with Algorithmic Information Theory. We now derive the statements of the theorem. Define P to be the probability over codebooks used in earlier in this proof that uses the distribution Q to generate the codewords. Thus K(P ) < + K(Q, n, R). Let D be the set of encoded codebooks that achieve an error rate less than or equal to 2 . By the arguments above, P (D) ≥ 0.5. This set D is computable from Q, n, R, and C, with K(D|(Q, n, R, C)) = O(1). Thus by Theorem 1 and Lemma 1, there is a codebook C * ∈ D that has an error rate ≤ 2 , with

K(C * ) < log K(P ) -log P (D) + I(D; H) < log K(Q, n, R) + I((Q, r, n, C); H). (4.2)
Thus the sender can use solely C * to send messages to the receiver. The receiver needs to determine if sequences are jointly typical, and thus uses (C * , Q, C) to decode the messages. Note that with careful analysis of the proof of Theorem 1 for computable probabilities, one can construct a short program for C * (with size less than that of Equation 4.2) that can also compute Q. Thus, we can construct a program p with the properties described in the theorem statement.

set of all Borel probability measures over N N is P. A probability P ∈ P is computable if given an encoding of a cylinder set C ∈ C, P (C) is computable. We use the following helper proposition and lemma throughout the paper.

Proposition 2

For every c, n ∈ N, if x < y + c for some x, y ∈ Nm then x + nK(x) < y + nK(y) + O(n log n) + 2c.

Proof. K(x) < + K(y) + K(y -x) as x can be computed from y and (y -x). Therefore nK(x) -nK(y) < nK(y -x) + dn, for some d ∈ N dependent on U . We assume that this equation is not true; then, there exists x, y, c ∈ N where x < y + c, and g ≤ O(n log n) + 2c where y -x + g < nK(x)-nK(y) < nK(y -x)+dn, which is a contradiction for g = + dn+2c+max a {2n log a-a} = + dn + 2c + 2n log n.

Theorem 21 For F ∈ F, S ∈ S, if s = -log Pr[F (S)] and h = I( S ; H), then min G∈G,G(S) K(G) < K(F ) + s + h + O(K(s, h) + log K(F )).
Proof. Each sample S ∈ S where S = {(i, v i )} i∈I can be identified by a cylinder set C S ∈ C where

C S = ∩ i∈I C i [v i ]. For every α ∈ N N there is a deterministic function G α : N → N, where G α (i) = α[i]. Furthermore if α ∈ C S , then for all (i, v i ) ∈ S, G α (i) = v i .
For each random function F ∈ F, we can identify a Borel probability P F ∈ P over N N such that for each sample

S = {(i, v i )} i∈I ∈ S, Pr[F (S)] = P F (C S )
. This is because random functions and Borel probability measures over N N have the same form. Furthermore, if F is computable, then P F is computable, with Proof. We put (s, P ) on an auxiliary tape to the universal Turing machine U . Thus, all algorithms have access to (s, P ), and all complexities implicitly have (s, P ) as conditional terms.

K(P F |F ) = O(1) (
F ) + s + h C + O(K(s) + log K(P F )) + O(K(h C )) min G∈G:G(S) K(G) <K(P F ) + s + h C + O(K(s) + log K(P F )) + O(K(h C )) (5.2) min G∈G:G(S) K(G) <K(F ) + s + h C + O(K(s) + log K(F )) + O(K(h C )) (5.3) min G∈G:G(S) K(G) <K(F ) + s + h S + O(K(s) + log K(F )) + O(K(h S )) (5.4) min G∈G,G(S) K(G) <K(F ) -log
Let Q be an elementary probability measure that realizes Ks( C ). Let d = max{d( C |Q), 1} and c ∈ N be a constant to be chosen later. Let n = max{m : m ∈ Dom(W ), W ∈ C, W ∈ Supp(Q)}. For a list L of a list of numbers and cylinder set W ∈ C, we say L W is the set of all x ∈ L with xN N ⊆ W . We define a measure κ over cd2 s lists of lists of n numbers L, where κ(L) = cd2 s i=1 P (L[i]N N ). Given a list of lists of n numbers L, κ(L) is computable (as a program for P is on an auxiliary tape). We use the indicator function i(L,

W ) = [W ∈ C, P (W ) ≥ 2 -s , L W = ∅].
The function i is computable, because P (W ) and L W are computable for all W ∈ C.

E L∼κ E W ∼Q [i(L, W )] ≤ W Q(W ) Pr L∼κ (W ∈ C, P (W ) ≥ 2 -s , L W = ∅) ≤ W Q(W ) cd2 s i=1 (1 -2 -s ) ≤ W Q(W )(1 -2 -s ) cd2 s < e -cd .
Thus there exists a list L of cd2 s sequences of numbers of length n such that

E W ∼Q [i(W, L )] = e -cd . Thus t(W ) = i(W, L )e cd is a Q-test, with t : {0, 1} * → R ≥0 and W Q(W )t(W ) ≤ 1. It must be that L C = ∅. Otherwise t(C) = e cd , and
K(C|c, d, Q) < + -log t(C)Q(C) < + -log Q(C) -(lg e)cd (lg e)cd < + -log Q(C) -K(C|P ) + K(d, c) (lg e)cd < d + K(d, c) + O(1).
This is a contradiction for c large enough solely dependent on the universal Turing machine. We roll c into the additive constants of the rest of the proof. Thus there exists x ∈ L C where Theorem 34 can be readily extended to sets of samples S = {S 1 , . . . , S n }, where for deterministic function G : N → N, G(S) if n i=1 G(S i ). For random function F ∈ F, F (S) is the union of events F (S i ), i = 1, . . . , n. The proof of the following corollary follows almost identically to the proofs of Theorem 34 and Lemma 5, noting that P (S) is computable given a computable probability P ∈ P and a finite description of a set of samples S.

K(x) < + log |L| + K(L) < + log |L| + K(d, Q) < + log d + s + K(d) + K(Q) < + s + 3 log d + K(Q) < + s + Ks(C) (5.6) min α∈C K(α) < + K(x) < + s + Ks(C), (
Corollary 1 For F ∈ F, if s = -log Pr[F (S)] and h = I( S ; H), then min G∈G,G(S) K(G) < log K(F ) + s + h + O(K(s, h) + log K(F )).

Games

Function derandomization has applications to the cybernetic agent model. In this section, we describe two simplified cybernetic agent models. For the first model, the agent p and environment q are defined as follows. The agent is a function p : (N × N) * → N, where if p(w) = a, w ∈ (N × N) * is a list of the previous actions of the agent and the environment, and a ∈ N is the action to be performed. The environment is of the form q : (N × N) * × N → N ∪ {W}, where if q(w, a) = b ∈ N, then b is q's response to the agent's action a, given history w, and the game continues. If q responds W then the agents wins and the game halts. The agent can be randomized. The game can continue forever, given certain agents and environments. This is called a win/no-halt game.

The following theorem is a game-theoretic interpretation of Lemma 6 in [START_REF] Vereshchagin | Rate Distortion and Denoising of Individual Data using Kolmogorov Complexity[END_REF].

Theorem 22 If 2 r deterministic agents of complexity < k win against environment q, then there is a deterministic agent p of complexity < log k -r + I( r, k, q ; H) that wins against q.

Proof. Given r, k, q , one can construct a finite set D of encoded agents that win against q and D contains at least 2 r agents of complexity < k. Furthermore x∈D m(x) * > 2 r 2 -k , so using Theorem 1, there is an agent p ∈ D, where, using Lemma 1, K(p) < log k -r + I(D; H) < log k -r + I( r, k, q ; H).

Theorem 23 If probabilistic agent p wins against environment q with at least probability p, then there is a deterministic agent p of complexity < log K(p ) -log p + I( p, p , q ; H) that wins against q.

Proof. Let I be a set of interactions between an arbitrary agent and the environment q such that each interaction ends in W and with probability > p/2, p will act according to an interaction in I.

K(G) < log K(F ) -log[F (C)] + I( C ; H) < log K(p ) -log[F (C)] + I( C ; H) < log K(p ) -log p + I( C ; H) < log K(p ) -log p + I( I ; H)
(5.9)

< log K(p ) -log p + I( p, p , q ; H), (5.10)
where Equations 5.9 and 5.10 are due to Lemma 1. The deterministic function G is an encoding of an agent, p, proving the theorem. The second game derandomization theorem is modified such that the environment gives a nonnegative rational penalty term to the agent at each round. Furthermore the environment specifies an end to the game without specifying a winner or loser. This is called a penalty game.

Corollary 2 If given probabilistic agent p, environment q halts with probability 1, and p has expected penalty less than n ∈ N, then there is a deterministic agent of complexity < log K(p) + I( p, n, q ; H) that receives penalty < 2n against q.

Proof. We create a win/no-halt game from q where an agent wins if it gets a penalty less than 2n. Thus p is a probabilistic agent that wins this new game with probability > .5. Theorem 23 then can be used to prove the corollary.

Chapter 6

Game Derandomization

For a given win/no-halt game if there is a good simple randomized player but no simple winning deterministic player, then that game is exotic, in that it has high mutual information with the halting sequence.

This mirrors derandomization, where if a solution to a problem can be produced easily with a simple probability, but has no simple solutions, then it is exotic. A game instance that has a simple winning probabilistic agent but no simple winning deterministic agent can be found in Example 1.

Even-Odds

We define the following win/no-halt game, entitled Even-Odds. There are N rounds. At round 1, the environment q secretly records bit e 1 ∈ {0, 1}. It sends an empty message to the agent who responds with bit a 1 ∈ {0, 1}. The agent gets a point if e 1 ⊕ b 1 = 1. Otherwise the agent loses a point. For round i, the environment secretly selects a bit e i that is a function of the previous agent's actions {a j } i-1 j=1 and sends an empty message to the agent, which responds with a i and the agent gets a point if e i ⊕ a i = 1, otherwise it loses a point. The agent wins after N rounds if it has a score of at least √ N .

Theorem 24 For large enough N , there is a deterministic agent p that can win Even-Odds with N rounds, with complexity K(p) < log I(q; H).

Proof. We describe a probabilistic agent p . At round i, p submits 0 with probability 1/2. Otherwise it submits 1. By the central limit theorem, for large enough N , the score of the probabilistic agent divided by

√ N is S ∼ N (0, 1). Let Φ(x) = Pr[S > x]. A common bound for Φ(x) is Φ(x) > 1 2π x x 2 + 1 e -x 2 /2 Φ(1) > 1 4π e -1/2 > 1 8π .
Thus when S ≥ 1, the score is at least √ N . Thus p wins with probability at least p = 1 8π . Thus by Theorem 23, there exists a deterministic agent p that can beat q with complexity K(p) < log K(p ) -log p + I((p, p , q); H) < log I(q; H).

Graph-Navigation

The win/no-halt game is as follows. The environment q consists of (G, s, r). G = (E, V ) is a nonbipartite graph with undirected edges, s ∈ V is the starting vertex, and r ∈ V is the goal vertex. Let t G be the time it takes for any random walk starting anywhere to converge to the stationary distribution π(v), for all v ∈ V , up to a factor of 2.

There are t G rounds and the agent starts at s ∈ V . At round 1, the environment gives the agent the degree s ∈ V , Deg(s). The agent picks an number between 1 and Deg(s) and sends it to q. The agent moves along the edge the number is mapped to and is given the degree of the next vertex it is on. Each round's mapping of numbers to edges to be a function of the agent's past actions. This process is repeated t G times. The agent wins if it is on r ∈ V at the end of round t G . A graphical depiction of this can be seen in Figure 6.1.

Theorem 25 There is a deterministic agent p that can win the Graph-Navigation game with complexity K(p) < log log |E| + I((G, s, r); H).

Proof. It is well known if G is non-bipartite, a random walk starting from any vertex will converge to a stationary distribution π

(v) = deg(v)/2|E|, for each v ∈ V .
A probabilistic agent p is defined as selecting each edge with equal probability. After t G rounds, the probability that p is on the goal r is close to the stationary distribution π. More specifically the probability is * > |E| -1 . Thus by Theorem 23, there is a deterministic agent p that can find r in t G turns and has complexity K(p ) < log log |E| + I((G, s, t); H).

Interactive-k-Sat

The penalty game Interactive-k-Sat is as follows. The environment q has access to a hidden k-Sat formula, with n variables and some number of clauses, each containing k literals, which are a variable instance or its negation. Each variable appears in at most 2 k /ke clauses. The environment's first action is to send the number of variables to the agent. After this step, the agent, p has n variables, each initially set to true. At each subsequent round, the environment gives to the agent the clauses which are not satisfied. The player can change up to k variables, and sends these changes to the environment. If the k-Sat formula is satisfied, the game stops. Otherwise the game continues. When the game ends, the penalty is the number of terms. A graphical representation of this game can be seen in Figure 6.2. Obviously there is a deterministic player of complexity O(1) that can try every possible assignment of variables. This is a winning strategy of at most 2 n turns. However, the following theorem shows that a much more successful player exists without much more complexity bounds.

Theorem 26 There exists a deterministic player p that can achieve a penalty of (1 + )(n/2k + n/(2 k /e -k)) with complexity K(p) < log I(q; H) -log , for ∈ (0, 1).

Proof. We use the Algorithmic Lovász Local Lemma, from [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF]. The randomized algorithm, when applied to k-Sat is as follows.

1. Given is a random assignment of n variables.

Return the variable assignment.

It was proved in [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF] that this algorithm has n/D expected steps, where D is the size of the dependency between events. So D = (2 k /e -k). Thus the goal of this proof is to construct a randomized player p that simulates the above randomized algorithm. The player p first starts out by randomizing its variables. Thus at each turn in this phase, it selects up to k untouched variables and gives them random assignments. This takes at most n/k steps. However, noting that player p only needs to update the variables that are set to true, this task takes n/2k expected steps. Once this is complete, whenever the environment sends back unsatsified clauses, the randomized agent chooses one at random and randomly resamples its k variables. Thus, by [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF], this has n/(2 k /e -k) expected steps before a satisfying assignment is found and the game halts. So the randomized player runs in (n/2k + n/(2 k /e -k)) expected steps. Thus by Corollary 2, there is a deterministic player that can find a satisfying assignment in less than (1 + )(n/2k + n/(2 k /e -k)) turns with complexity K(p) < log I(q; H) -log .

Note that as the game proceeds, the environment reveals more and more information about its hidden k-Sat formula to the player. This leaves open the possibility of a deterministic player of Kolmogorov complexity O(1) that coerces the environment to reveal all the clauses and then manually set the corresponding satisfying assignment. Whether or not this will take less steps than that proved in the above theorem is unknown.

Penalty-Tests

An example penalty game is as follows. The environment q plays a game for N rounds, for some very large N ∈ N, with each round starting with an action by q. At round i, the environment gives, to the agent, an encoding of a program to compute a probability P i over N. The choice of P i can be a computable function of i and the agent's previous turns. The agent responds with a number a i ∈ N. The environment gives the agent a penalty of size T i (a i ), where T i : N → Q ≥0 is a computable test, with a∈N P i (a)T i (a) < 1. After N rounds, q halts. A graphical representation of this game can be found in Figure 6.3.

Theorem 27 There is a deterministic agent p that can receive a penalty < (1 + )N and has complexity K(p) < log I(q; H) -log , for ∈ (0, 1).

Proof. A very successful probabilistic agent p can be defined. Its algorithm is simple. On receipt of a program to compute P i , the agent randomly samples a number N according to P i . At each round the expected penalty is a P i (a)T i (a) < 1, so the expected penalty of p for the entire game is < N . Thus by Corollary 2, there is a deterministic agent p such that 1. The agent p receives a penalty of < (1 + )N , 2. K(p) < log I(q; H) -log .

Example 1 Let q be defined so that a|i) , where [A] = 1 if A is true, and 0 otherwwise. Thus each T i is a randomness deficiency function (to the power of 2). The probabilistic algorithm p will receive an expected penalty < N . However any deterministic agent p that receives a penalty < 2N must be very complex, as it must select many numbers with low randomness deficiency. Thus, by the bounds above, I(q; H) must be very high. This makes sense because q encodes N randomness deficiency functions. At each round i the probability, P i , that the environment gives to the player is a uniform measure over a unique interval. The environment has three tests {T 1 , T 2 , T 3 }, which is not shared with the player, that represent the penalties. In this depiction, the player's moves are numbers in the interval (represented by the arrows) and result in low total penalty.

P i (a) = [a ≤ 2 i ]2 -i and T i = [a ≤ 2 i ]2 i-K(

Set-Subset

We define the following win/no-halt game, entitled Set-Subset. There are k rounds. At round i = {1, . . . , k}, the environment q gives n numbers A i ⊂ N to the agent p. The environment secretly selects m ≤ n numbers B i ⊆ A i . The player selects a number a i ∈ A i . Each A i and B i are a function of the player's previous actions. The player wins if for every round, his selection a i is in the secret set B i . So for all i ∈ {1, . . . , k}, a i ∈ B i . A graphical depiction of this game can be seen in Figure 6.4.

Theorem 28 There is a deterministic agent p that win against Set-Subset environment q, where K(p) < log k log(n/m) + I(q; H).

Proof. Let p be the randomized the player that selects a member of the given set with A i with uniform probability. The probability that p picks a member of B i is |B i |/|A i | = m/n. The probability that p picks a member of B i for all i ∈ {1, . . . , k} is (m/n) k , which is the probability that p wins. K(p ) = O(1). Thus by Theorem 23, there exists a deterministic player p that wins against q with complexity bounded by the theorem statement.

Interactive-Hypergraph

We define the following penalty game, entitled Interactive-Hypergraph. The environment has access to a hidden k-regular -hypergraph. A hypergraph is a pair J = (V, E) of vertices V and edges E ⊆ P(V ). Thus each edge can connect ≥ 2 vertices. A hypergraph is k-regular of the size |e| = k for all edges e ∈ E. A 2-regular hypergraph is just a simple graph. The player has access to a list of vertices and the goal of the player is to produce a valid 2-coloring of the hypergraph. A valid 2-coloring of a hypergraph (V, E) is a mapping f : V → {1, 2} where every edge e ∈ E is not monochromatic |{f (v) : v ∈ e}| = 2. We assume that for each edge f of the graph, there are at most 2 k-1 /e -1 edges h such that f ∩ h = ∅.

The game proceeds as follows. For the first round, environment gives the number of vertices to the player. The player has n vertices, each with starting color 1. At each subsequent turn, the environment sends to the player the edges which are monochromatic. The player can change the color of up to k vertices and sends these changes to the environment. The game ends when the player has a valid 2-coloring of the graph.

Theorem 29 There exists a deterministic player p that can beat the environment q in (1 + )(n/2k + n/(2 k-1 /e -1)) turns of complextiy K(p) < log I(q; H) -log .

Proof. We use the Algorithmic Lovász Local Lemma, from [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF]. The randomized algorithm, when applied to hypergraphs is as follows.

1. Given is a random 2-color assignment of n vertices. It was proved in [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF] that this algorithm has n/D expected steps, where D is the size of dependency between the events. So D = 2 k-1 /e -1. Thus the goal of this proof is to construct a randomized player p that simulates the above randomized algorithm. The player p first starts out by randomizing the color assignments of each vertex. Thus at each turn in this phase, it selects up to k untouched vertices and gives them random assignments. This takes at most n/k steps. However, noting that player p only needs to update the colors that are set to 2, this task takes n/2k expected steps. Once this is complete, whenever the environment sends back unsatsified Figure 6.5: A graphical depiction of a random two dimensional walk. The radius r is the length of the line between the starting and ending points. edges, the randomized agent chooses one edge at random and randomly recolors its k vertices. Thus, by [START_REF] Moser | A Constructive Proof of the General LováSz Local Lemma[END_REF], this has n/D = n/(2 k-1 /e -1) expected steps before a valid two-coloring is found and the game halts. So the randomized player runs in (n/2k + n/(2 k-1 /e -1)) expected steps. Thus by Corollary 2, there is a deterministic player that can find a valid 2-coloring in less than (1 + )(n/2k + n/(2 k-1 /e -1)) turns with complexity K(p) < log I(q; H) -log .

Grid-Walk

We define the following win/no-halt game, entitled Grid-Walk. The player starts at the origin of a two dimension grid with integer coordinates. At the start of the turn, the player chooses a number from {1, . . . , 4} and the the environment maps this number to a direction (North, South, East, West) based on a function of the player's previous actions. The enviroment moves the player in the choseen direction and the next round begins. No messages are sent from the environment to the player. The radius of the player is its Euclidean distance to the origin. The player wins if after N rounds, it has a radius at least √ N . An example random walk can be seen in figure 6.5.

Theorem 30 For large enough N , there is a deterministic agent p that can win against Grid-Walk environment q such that K(p) < log I((q, N ); H).

Proof. We define a probabilistic player p that randomly chooses a number from {1, 2, 3, 4} with uniform probability. Thus p performs a random walk on the two dimensional grid. For large enough N , the probability density function for the radius r of random walker p is the Rayleigh density function P (r) = 2r N e -r 2 /N . The culmulative distribution function is

F (r) = 1 -e -r 2 /N . Thus c = 1 -F ( √ N ) = 1 -e -1
. Thus with at least constant probability c the radius of p is at least √ N , and p wins. So by Theorem 23, there exists a deterministic player p that wins against q where K(p) < log K(p ) -log c + I((p , N, q); H) < log I((N, q); H).

Min-Cut

We define the following win/no-halt game, entitled Min-Cut. The game is defined by an undirected graph G and a mapping from numbers to edges. At round i, the environment q sends the number of edges of G. The player responds with a number. The environment maps the number to an edge, and this mapping can be dependent on the player's previous actions. The environment then contracts the graph G along the edge. The game halts when the graph G has contracted into two vertices. The player wins if the cut represented by the contractions is a min cut. A minimum cut of a graph is the minimum number of edges, that when removed from the graph, produces two components. A graphical depiction of a min cut can be seen in Figure 6.6.

Theorem 31 There is a deterministic agent p that can win against Min-Cut instance (G, S, ), |G| = n, such that K(p) < log 2 log n + I((G, ); H).

Proof. We define the following randomized agent p . At each round, p chooses an edge at random. Thus the interactions of p and q represent an implementation of Karger's algorithm. Karger's algorithm has an Ω(1/n 2 ) probability of returning a min-cut. Thus p has an Ω(1/n 2 ) chance of winning. By Theorem 23, there exist a deterministic agent p and c where p can beat q and has complexity K(p) < log K(p ) -log c/n 2 + I(q; H) < log 2 log n + I((G, ); H).

Cover-Time

We define the following interactive penalty game. Let G = (E, V ) be a graph consisting of n vertices V and undirected edges E. The environment q consists of (G, s, ). G = (E, V ) is a non-bipartite graph with undirected edges, s ∈ V is the starting vertex. is a mapping from numbers to edges to be described later.

The agent starts at s ∈ V . At round 1, the environment gives the agent the degree s ∈ V , Deg(s). The agent picks a number between 1 and Deg(s) and sends it to q. The agent moves along the edge the number is mapped to and is given the degree of the next vertex it is on. Each round's mapping of numbers to edges, , is a computable function of the agent's past actions. The game stops if the agent has visited all vertices and the penalty is the number of turns the agents takes.

Theorem 32 There is a deterministic agent p that can play against Cover-Time instance (G, S, ), |G| = n, and achieve penalty 8 27 n 3 + o(n 3 ) and K(p) < log I((G, s, ); H).

Proof. A probabilistic agent p is defined as selecting each edge with equal probability. Thus the agent performs a random walk. The game halts with probability 1. Due to [START_REF] Feige | A tight upper bound on the cover time for random walks on graphs[END_REF], the expected time (i.e. expected penalty) it takes to reach all vertices is 4 27 n 3 + o(n 3 ). Thus by Corollary 2 there is a deterministic agent p that can reach each vertex with a penalty of 8 27 n 3 + o(n 3 ) and has complexity K(p) < log K(p ) + I((G, s, ); H) < log I((G, s, ); H).

Vertex-Transitive-Graph

We describe the following graph based game. The environment q = (G, , u, 2k) consists of an undirected vertex-transitive graph G = (V, E), a start vertex u ∈ V , the number of rounds 2k, and a mapping from numbers to vertices. A vertex-transitive graph G = (V, E) has the property that for any vertices u, v ∈ V , there is an automorphism of G that maps u into v. An example of a vertex transitive graph can be seen in Figure 6.7. At round 1, the agent starts at vertex u ∈ V and the environment send to the agent the degree of u. The agent picks a number from 1 to Deg(u) and the environment moves the agent along the edge specified by the mapping from numbers to edges. The mapping can be a function of the agents previous actions. The agent wins if after 2k rounds, the agent is back at u.

Theorem 33 There is a deterministic agent p that can win at the Vertex-Transitive-Graph game (G = (V, E), , u, k), |V | = n with complexity K(p) < log log n + I((G, , u, k); H).

Proof. We define the following randomized agent p . At each round, after being given the degree d of the current vertex, p chooses a number randomly from 1 to d. K(p ) = O(1). This is equivalent to a random walk on G. Let P l (u, v) denote the probability that a random walk of length l starting at u ends at v. Then due to [START_REF] Alon | The Probabilistic Method[END_REF], for vertex-transitive graph G, P 2k (u, u) ≥ P 2k (u, v).

So after 2k rounds the randomized agent is back at u with probability P 2k (u, u) ≥ 1/n, which lower bounds the winning probability of p against q. By Theorem 23, there exists a deterministic agent p that can beat q with complexity K(p) < log K(p ) + n + I((n, p , q); H) < log n + I((G, , u, k); H).

Proof. Follows directly from Theorem 34.

Corollary 4 (Resource EL) Assume Crypto. Let L ∈ P, A ∈ FP , and assume A samples L n with probability δ n . Then for some polynomial p, min x∈Ln K p (x) < -log δ n + O(log n).

Proof. Let F ∈ FP where F ({0, 1} n ) ⊆ {0, 1} n and for x ∈ {0, 1} n , F (x) = 1 n if A(x) ∈ L n and F (x) = 0 n otherwise. Let k ∈ N be maximal such that δ n ≥ 2 k-n . Let = n -k + O(c log n). By Theorem 34, there exists a function G : {0, 1} → {0, 1} n running in polynomial time such that there exists x ∈ , with G(x) = 1 n . This is because 1 n ∈ T k , using the definition in Theorem 34, because A produces a member of L n with probability at least δ n and all of L n is mapped to 1 n . We define a program P that uses G to map x to a string y, then use A to map y to a string z ∈ L n . This program P is of size and runs in polynomial time.

A verifier V : {0, 1} * ×{0, 1} * → {0, 1} is a function computable in polynomial time with respect to the first argument. For a given x, Proofs(x) = {y : V (x, y) = 1}.

Corollary 5 Assume Crypto. Let {x n } be uniformly computable in polynomial time. For a verifier V (x, y), let A ∈ FP sample Proofs(x n ) with probability γ n . Thus there is a polynomial p and y ∈ Proofs(x n ) with K p (y) < -log γ n + O(log n).

Resource Bounded Derandomization

In this section, we use Corollary 5 to produce three examples of resource bounded derandomization.

Lemma 6 (Lovasz Local Lemma) Let E 1 , . . . , E n be a collection of events such that ∀i : Pr[E i ] ≤ p. Suppose further that each event is dependent on at most d other events, and that ep(d + 1) ≤ 1.

Then, Pr i E i > 1 -1 d+1 n .
Proposition 3 (Mutual Independence Principle) Suppose that Z 1 , . . . Z m is an underlying sequence of independent events and suppose that each event A i is completely determined by some subset S i ⊂ {Z 1 , . . . , Z m }. If S i ∩ S j = ∅ for j = j 1 , . . . , j k then A i is mutually independent of {A j 1 , . . . , A j k }.

Balancing-Vectors

Corollary 6 Assume Crypto. For vector v, v ∞ = max i |v i |. A binary matrix M has entries of 0s or 1s. Let {M n } be a uniformly polynomial time computable sequence of n × n binary matrices.

There is a polynomial p where for each M n there is a

k-Sat

Corollary 7 Assume Crypto. Let Φ n be a k(n)-SAT formula, using n variables, m(n) clauses, uniformly polynomial time computable in n. Furthermore, each variable occurs in at most 2 k(n) /k(n)e-1 clauses. There is a polynomial p and a satisfying assignment x of Φ n where

K p (x) < 2m(n)e2 -k(n) + O(log n).
Proof. The sample space is the set of all 2 n assigments. We choose a random assignment, where each variable is independently equally likely to have a true or false assignment. For each clause C J , E j is the bad event "C j is not satisfied". Let p = 2 -k(n) and d = (2 k(n) /e) -1. Thus ∀j, Pr[E j ] ≤ p as each clause has size k(n) and each E j is dependent on at most d other events since each variable

  .2.Theorem 6 There is a partition of vertices of a k-regular graph G = (V, E), with vertices |V | = n, into c = k 3 ln k components each containing a cycle that is vertex disjoint from the other cycles with complexity K( ) < log K(n, k) + 2n/k 2 + I(G; H).

Figure 3 . 2 :

 32 Figure 3.2: An example graph partitioned into 3 groups such that each group contains a cycle.

  <2n/β.

Figure 3 . 3 :

 33 Figure 3.3: An example graph coloring. Nodes that share an edge are assigned different colors.

Figure 3

 3 Figure 3.4: A Boolean Hypercube network, for n = 3.

Figure 3

 3 Figure 3.5: A graphical depiction of an independent set, represented by the green vertices. They do not share any edges.

Figure 3

 3 Figure 3.6: A graphical depiction of a dominating set. The two highlighted vertices are adjacent to all other vertices in the graph.

Figure 3

 3 Figure 3.7: A graphical depiction of Bloom filter with k = 3 hash functions. The first element x is in G and is thus mapped to ones in the Bloom filter. Thus the Bloom filter would indicate that x ∈ G. The second element y is not in G and has some of the hash functions map to 0. Thus the Bloom filter would indicate that y ∈ G.

Figure 3

 3 Figure 3.8: A graphical depiction of a Latin Transversal. Each number appears exactly 4 times in the matrix. The transversal is a permutation of the matrix such that all its entries have different values.

  By the Markov inequality, let the finite set D ⊆ D be constructed from (p, {f i }, τ ), such that P (D) > 1/2 and K(D|(p, {f i }, τ )) = O(1). By Theorem 1 and Lemma 1, 20 there a string x ∈ D such that K(x) < log -log m(D) + I(D; H) < log K(P ) -log P (D) + I((p, {f i }, τ ); H)

  5.1) This is because given an encoding F and an encoded cylinder set C , one can compute Pr[F (C)], which is equal to P F (C). Thus given a random function F ∈ F and sample S ∈ S, by Lemma 5 applied to P F ∈ P and C S ∈ C, we get the following result, with h C = I( C S ; H), h S = I( S ; H), and s = -log P F (C S ) , min α∈C S K(a) <K(P

  Pr [F (S)] + I( S ; H) (5.5) + O(K( -log Pr [F (S)] , I( S ; H)) + log K(F )). Equation 5.2 is because for the α ∈ N N that minimizes the leftmost term, G α ∈ G, with G α (S) and K(G α ) < + K(α). Equation 5.3 is because P F can be constructed from F , i.e. Equation 5.1. Equation 5.4 is due to Proposition 2, Lemma 1 and the fact that K( C S | S ) = O(1). Equation 5.5 is due to the definition of s, where s = -log P F (C S ) = -log Pr[F (S)] . Lemma 5 For cylinder set C ∈ C, computable probability P ∈ P, if s = -log P (C) and h = I( C ; H), then min α∈C K(α) < K(P ) + s + h + O(K(s, h) + log K(P )).

  5.7) where Equation 5.6 is due to the definition of stochasticity. Equation 5.7 is because xN N ⊆ C. Thus making the relativization of (s, P ) explicit, min α∈C K(α| s, P ) < + s + Ks( C | s, P ) min α∈C K(α) < K(P ) + s + Ks( C ) + O(K(s) + log K(P )) min α∈C K(α) < K(P ) + s + I( C ; H) + O(K(s, I( C ; H)) + log K(P )).(5.8) Equation 5.8 follows from Lemma 4, which states Ks(x) < I(x; H) + O(K(I(x; H))).

  Thus K(I|p, p , q) = O(1). p can be encoded into a random function F , where the domain (N × N) * of p can be encoded into a single number N. K(F |p ) = O(1). Similarly, I can be encoded into a set of samples C, where Pr[F (C)] > p/2 and K( C | I ) = O(1). Using Corollary 1, there is a deterministic function G : N → N, such that

Figure 6

 6 Figure 6.1: A graphical depiction of a winning deterministic player to the Graph-Navigation game. The player starts at s and chooses a path to reach the goal state r, (assuming t G = 8).

Figure 6

 6 Figure 6.2: A graphical depiction of a turn in the Interactive-k-Sat game. The player's current assignment of variables has resulted in two unsatisfied clauses, which the environment sends to the player. The environment has a complete picture of the variables and clauses, which are hidden to the player.

2.

  While there exists an unsatisfied clause. (a) Pick an unsatisfied clause at random. (b) Reassign the variables of this clause randomly.

Figure 6

 6 Figure 6.3: Three rounds of the Penalty-Test game.At each round i the probability, P i , that the environment gives to the player is a uniform measure over a unique interval. The environment has three tests {T 1 , T 2 , T 3 }, which is not shared with the player, that represent the penalties. In this depiction, the player's moves are numbers in the interval (represented by the arrows) and result in low total penalty.

Figure 6

 6 Figure 6.4: A graphical depiction of the Set-Subset game. Each line represents a round of the game. The boxes of the ith line represent A i , and the filled boxes represent the secret set B i ⊂ A i . A winning player is shown, by placing a circle in B i for each round i.

2.

  While there exists a monochromatic edge. (a) Pick a monochromatic edge random. (b) Reassign the colors of the vertices of this edge randomly. 3. Return the valid 2-coloring.

Figure 6

 6 Figure 6.6: A graphical depiction of a minimum cut. By removing the edges along the dotted line, two components are created.

Figure 6 . 7 :

 67 Figure 6.7: An example vertex-transitive graph.

v i b i = m j=1 v i j b i j = m j=1 b

 j=1 vector b ∈ {-1, 1} n such that M n b ∞ ≤ 4 √ n ln n and K p (b) = O(log n).Proof.Let v = (v 1 , . . . , v n ) be a row of M . Choose a random b = (b 1 , . . . , b n ) ∈ {-1, +1} n . Let i 1 , . . . , i m be the indices such that v i j = 1. Thus Y = v, b = n i=1 i j . E[Y ] = E[ v, b ] = E i v i b i = i E[v i b i ] = v i E[b i ] = 0.By the Chernoff inequality and the symmetry Y , for τ = 4 √ n ln n,Pr[|Y | ≥ τ ] = 2 Pr[v • b ≥ τ ] probability thatany entry in M b exceeds 4 √ n ln n is smaller than 2n -8 . Thus, with probability 1 -2n -7 , all the entries of M b have value smaller than 4 √ n ln n. Let A(x) = x be the uniform sampling function. The verifier V takes in a matrix M and a vector b and returns 1 iff M b ∞ ≤ 4 √ n ln n. Let D ⊂ {0, 1} n consist of all strings that encode vectors b x ∈ {-1, +1} n in the natural way such that M b x ∞ ≤ 4 √ n ln n. By the above reasoning, A samples D with probability ≥ 1 -2n -7 > 0.5. So by Corollary 5, there is a polynomial p, where for each n × n matrix M n there is a binary vector b ∈ {-1, 1} n with M b ∞ ≤ 4 √ n ln n and K p (b) = O(log n).

Pick a intermediate destination σ(i). Packet v i travels to node σ(i).

Chapter 5

Deriving Game Derandomization

In this chapter, we prove the two Kolmogorov game derandomization theorems. It involves first derandomizing functions N → N between natural numbers. This chapter uses notions of stochasticity in the field of algorithmic statistics [START_REF] Nikolay | Algorithmic statistics: Forty years later[END_REF]. A string x is stochastic, i.e. has a low Ks(x) score, if it is typical of a simple probability distribution. The deficiency of randomness function of a string x with respect to an elementary probability measure P conditional to y ∈ {0, 1} * , is d(x|P, y) = -log P (x) -K(x| P , y).

Function Derandomization

In this section we show how to construct deterministic functions from random ones. The main results of this section are not (directly) implied by the main theorem in [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF], because Theorem 5 is a statement about probabilities over the Baire space, whereas the result in [START_REF] Levin | Occam bound on lowest complexity of elements[END_REF][START_REF] Epstein | On the algorithmic probability of sets[END_REF] is a statement about lower computable semi measures over N.

We recall the definitions from the introduction. Random functions F over natural numbers are modeled by discrete stochastic processes indexed by N, where each F (t), t ∈ N, is a random variable over N. F is the set of all random functions. A random function

To prove function derandomization, we leverage properties about the Baire space N N . Individual cylinders are C n [v] = {(a 1 , a 2 , . . . ) ∈ N N : a n = v}. Cylinders are generators for cylinder sets. The cylinder sets C ∈ C consists of all intersections of a finite number of cylinders.

then for all i ∈ I, we say i ∈ Dom(C). The set of all such cylinder sets provides a basis for the product topology of N N . The encoding of a cylinder set

Resource Bounded Derandomization

Resource Bounded EL Theorem

In this section we derive the resource bounded EL theorem. We also derive an interesting corollary to Theorem 4.1 in [START_REF] Antunes | Worst-Case Running Times for Average-Case Algorithms[END_REF] which states to invert a hash function f -1 (x), one can find a secret key π of size approximiately equal to x that will efficiently decompress to a pre-image of x with respect to f . The results in this section are not unconditional, they require the existence of the pseudorandom generator, introduced in [START_REF]Hardness vs randomness[END_REF].

Assumption 1 Crypto is the assumption that there exists a language in DTIME(2 O(n) ) that does not have size 2 o(n) circuits with Σ p 2 gates. This asssumption is need in the proof of Theorem 34 in [START_REF] Antunes | Worst-Case Running Times for Average-Case Algorithms[END_REF] to assume the existence of a pseudorandom generator g : {0, 1} k log n → {0, 1} n , computable in time polynomial in n.

Remark 1 In the previous theorem, the running time of G is a polynomial function of the running time of F . This was noted in [START_REF] Lu | Optimal coding theorems in time-bounded kolmogorov complexity[END_REF]. In addition, in subsequent theorems and corollaries of this section, the polynomial time function p in the resource bounded complexity K p is a polynomial function of the running times of the algorithms of the theorem/corollary statements. Furthermore, due to [START_REF] Antunes | Worst-Case Running Times for Average-Case Algorithms[END_REF], G can be encoded in O(1) bits.

The following corollary implies that to invert x with a hash function f , one can find a secret key π of size approximately equal to x that efficiently expands to an element in f -1 (x).

Corollary 3 Assume Crypto. Let f ∈ FP , where f ({0, 1} n ) ⊆ {0, 1} n-k . Then for some polynomial p where for {0,

Vertex-Disjoint-Cycles

Theorem 35 Assume Crypto. Let {G n } be a uniformly computable in polynomial time sequence of k-regular graphs, with k ≥ 5. There is a polynomial p where for each G n , there is a partition x of k 3 ln k components each containing a cycle with

Proof. We partition the vertices of G into c = k/3 ln k components by assigning each vertex to a component chosen independently and uniformly at random. With positive probability, we show that every component contains a cycle. It is sufficient to prove that every vertex has an edge leading to another vertex in the same component. This implies that starting at any vertex there exists a path of arbitrary length that does not leave the component of the vertex, so a sufficiently long path must include a cycle. A bad event A v = {vertex v has no neighbor in the same component}. Thus

A v is determined by the component choices of itself and of its out neighbors N out (v) and these choices are independent. Thus by the Mutual Independence Principle, (Proposition 3) the dependency set of A v consist of those u that share a neighor with v, i.e., those u for which ({v} ∪ N (v)) ∩ ({u} ∪ N (u)) = 0. Thus the size of this dependency is at most d = (k + 1) 2 . Take d = (k + 1) 2 and p = k -3 , so ep(d + 1) = e(1 + (k + 1) 2 )/k 3 ≤ 1, holds for k ≥ 5. Thus, noting that k ≥ 5, by Lovasz Local Lemma, (Lemma 6),

Thus by Corolloray 5, there is a polynomial p, where for each graph G n ∈ Q of n vertices, there is a partition x ∈ Proofs(G n ) with . Thus

-log γ n < -m(n) log 1 -e/2 k(n) < 2em(n)2 -k(n) .

By Corollary 5, there is a polynomial p, where for all n, there is a satisfying assignment x ∈ D n of Φ(n) with K p (x) < 2m(n)e2 -k(n) + O(log n).