The matrix compiler
Lax119563.MatrixCompiler · concepts/Lax119563/MatrixCompiler.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let and , and let be an implicit parity system with coordinates and conflict round . Then there are colored graphs , constructed from , such that:
- If , then Spoiler wins the bijective pebble game on with pebbles in rounds.
- Duplicator survives the bijective pebble game on with pebbles for rounds, or indefinitely if .
- With an absolute constant, , where , and the two graphs have at most edges. Their binary encoding has length ; in particular, colors are written with bits.
- The binary encoding of the pair can be computed from the binary encoding of by a deterministic multitape Turing machine in time , where is the bit length of and suppresses a fixed power of . The machine and all constants are absolute; in particular and are part of the input.
Here is the check matrix of the code of codewords whose blocks have equal parity and whose block coordinates sum to zero: its rows are the block-parity checks comparing blocks with block , followed by the checksum checks for the sum of the block coordinates. For a schema , is obtained from by restricting to the columns in and deleting zero rows; is its number of rows and its number of nonzero entries. Finally, .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Matrix.Basic |
| 2 | import Mathlib.Data.Nat.Log |
| 3 | import Lax119563.ColoredGraphs |
| 4 | import Lax119563.DeterministicTime |
| 5 | import Lax119563.ImplicitParitySystems |
| 6 | import Lax119563.ImplicitSystemEncodings |
| 7 | import Lax119563.PebbleGame |
| 8 | |
| 9 | /-! |
| 10 | --- |
| 11 | title: The matrix compiler |
| 12 | type: theorem |
| 13 | --- |
| 14 | Let and , and let |
| 15 | be an implicit parity system with coordinates |
| 16 | and conflict round . |
| 17 | Then there are colored graphs , constructed from , such |
| 18 | that: |
| 19 | |
| 20 | 1. If , then Spoiler wins the bijective pebble game on |
| 21 | with pebbles in rounds. |
| 22 | 2. Duplicator survives the bijective pebble game on with |
| 23 | pebbles for rounds, or indefinitely if . |
| 24 | 3. With an absolute constant, , |
| 25 | where |
| 26 | , and the two graphs have at most edges. Their |
| 27 | binary encoding has length ; in particular, colors are written with |
| 28 | bits. |
| 29 | 4. The binary encoding of the pair can be computed from the |
| 30 | binary encoding of by a deterministic multitape Turing machine in time |
| 31 | , where is the bit length of and |
| 32 | suppresses a fixed power of . The machine and all constants are absolute; |
| 33 | in particular and are part of the input. |
| 34 | |
| 35 | Here is the check matrix of the code of |
| 36 | codewords whose blocks have equal parity and whose block coordinates sum to zero: its rows |
| 37 | are the block-parity checks comparing blocks with block , |
| 38 | followed by the checksum checks for the sum of the block coordinates. For a schema , |
| 39 | is obtained from by restricting to the columns in and deleting zero |
| 40 | rows; is its number of rows and its number of nonzero entries. |
| 41 | Finally, . |
| 42 | |
| 43 | # Implementation notes |
| 44 | |
| 45 | The paper states this theorem for the explicit graph construction of the matrix compiler, |
| 46 | together with its size bound and construction time (Lemma "Matrix size"). Here the |
| 47 | construction is an unspecified function `compile` from implicit parity systems to graph |
| 48 | pairs; its properties are the game clauses, the size bounds, and that a single deterministic |
| 49 | machine computes it within steps, where and are absolute. |
| 50 | Only the constant of the round bound may depend on . |
| 51 | |
| 52 | Since is part of the input of the machine, the statement serves both the quasi-linear |
| 53 | reduction for fixed and polynomial-time reductions in which grows with the input. |
| 54 | -/ |
| 55 | |
| 56 | open Lax119563.ColoredGraphs Lax119563.PebbleGame Lax119563.ImplicitParitySystems |
| 57 | Lax119563.ImplicitSystemEncodings Lax119563.BinaryEncodings Lax119563.DeterministicTime |
| 58 | open Lax489179.TuringMachine (Machine Deterministic) |
| 59 | |
| 60 | namespace Lax119563.MatrixCompiler |
| 61 | |
| 62 | variable {k ℓ : ℕ} |
| 63 | |
| 64 | /-- The check matrix `B`. Row `inl i` is the block-parity check comparing block `i` with the |
| 65 | last block; row `inr t` is the checksum check of bit `t` of the block coordinates. -/ |
| 66 | def checkMatrix (k ℓ : ℕ) : Matrix (Fin (k - 1) ⊕ Fin ℓ) (Coord k ℓ) (ZMod 2) := |
| 67 | Matrix.of fun row c => |
| 68 | match row with |
| 69 | | .inl i => if (c.1 : ℕ) = i ∨ (c.1 : ℕ) = k - 1 then 1 else 0 |
| 70 | | .inr t => c.2 t |
| 71 | |
| 72 | open Classical in |
| 73 | /-- The number `m_e` of rows of `B_e`: rows of `B` that are nonzero on `ℭ_e`. -/ |
| 74 | noncomputable def numRows {w : ℕ} (e : Schema k ℓ w) : ℕ := |
| 75 | (Finset.univ.filter fun row => ∃ c ∈ e.domain, checkMatrix k ℓ row c ≠ 0).card |
| 76 | |
| 77 | open Classical in |
| 78 | /-- The number `nnz(B_e)` of nonzero entries of `B_e`. -/ |
| 79 | noncomputable def nnz {w : ℕ} (e : Schema k ℓ w) : ℕ := |
| 80 | ((Finset.univ ×ˢ e.domain).filter fun x => checkMatrix k ℓ x.1 x.2 ≠ 0).card |
| 81 | |
| 82 | /-- `Λ = 1 + max ({0} ∪ {m_e : e ∈ 𝓔})`. -/ |
| 83 | noncomputable def Λ (I : ImplicitParitySystem k ℓ) : ℕ := |
| 84 | 1 + (I.schemas.map numRows).foldr max 0 |
| 85 | |
| 86 | /-- The size parameter `S = ∑_v |ℭ_v| + (k+1) ∑_e nnz(B_e)`. -/ |
| 87 | noncomputable def matrixSize (I : ImplicitParitySystem k ℓ) : ℕ := |
| 88 | ∑ v, (I.domain v).card + (k + 1) * (I.schemas.map nnz).sum |
| 89 | |
| 90 | /-- **The matrix compiler.** There is a construction `compile` of graph pairs from implicit |
| 91 | parity systems such that, for `k ≥ 3`, the bijective `(k+1)`-pebble game on the pair follows |
| 92 | unit propagation: Spoiler wins in `O_k(Λ(τ+1))` rounds if a conflict occurs in round `τ`, and |
| 93 | Duplicator survives `τ - 1` rounds. The graphs have `O(S)` vertices and at most three times |
| 94 | as many edges as vertices, and their encoding has length `O(S log (S + 2))`. A single deterministic machine computes the encoding of the pair |
| 95 | from the encoding of the system in time `O((H + S) log^c (H + S + 2))`. -/ |
| 96 | axiom matrix_compiler : |
| 97 | ∃ compile : ∀ {k ℓ : ℕ}, ImplicitParitySystem k ℓ → ColoredGraph × ColoredGraph, |
| 98 | (∃ C : ℕ, ∀ k : ℕ, 3 ≤ k → ∃ Cₖ : ℕ, ∀ ℓ : ℕ, 1 ≤ ℓ → |
| 99 | ∀ I : ImplicitParitySystem k ℓ, |
| 100 | (∀ τ : ℕ, I.conflictRound = τ → |
| 101 | SpoilerWinsWithin (k + 1) (Cₖ * Λ I * (τ + 1)) (compile I).1 (compile I).2) ∧ |
| 102 | (∀ r : ℕ, (r : ℕ∞) + 1 ≤ I.conflictRound → |
| 103 | DuplicatorSurvives (k + 1) r (compile I).1 (compile I).2) ∧ |
| 104 | (compile I).1.n + (compile I).2.n ≤ C * matrixSize I ∧ |
| 105 | (compile I).1.numEdges + (compile I).2.numEdges ≤ |
| 106 | 3 * ((compile I).1.n + (compile I).2.n) ∧ |
| 107 | (encodeGraphPair (compile I).1 (compile I).2).length ≤ |
| 108 | C * (matrixSize I + 1) * (Nat.log 2 (matrixSize I + 2) + 1)) ∧ |
| 109 | (∃ M : Machine, Deterministic M ∧ ∃ C c : ℕ, ∀ k : ℕ, 3 ≤ k → ∀ ℓ : ℕ, 1 ≤ ℓ → |
| 110 | ∀ I : ImplicitParitySystem k ℓ, |
| 111 | ComputesWithin M (encodeSystem I) (encodeGraphPair (compile I).1 (compile I).2) |
| 112 | (C * (bitLength I + matrixSize I) * |
| 113 | Nat.log 2 (bitLength I + matrixSize I + 2) ^ c)) |
| 114 | |
| 115 | end Lax119563.MatrixCompiler |
| 116 |
Implementation notes
The paper states this theorem for the explicit graph construction of the matrix compiler, together with its size bound and construction time (Lemma "Matrix size"). Here the construction is an unspecified function from implicit parity systems to graph pairs; its properties are the game clauses, the size bounds, and that a single deterministic machine computes it within steps, where and are absolute. Only the constant of the round bound may depend on .
Since is part of the input of the machine, the statement serves both the quasi-linear reduction for fixed and polynomial-time reductions in which grows with the input.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments