Orthogonal vectors and randomized hypothesis
DefinitionNearLogSetCover966_Main_Supplement_OVp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
An orthogonal-vectors instance consists of indexed groups of distinct binary vectors in dimension . Its YES condition is
The randomized logarithmic-dimension hypothesis says that for every fixed and , there is excluding a two-sided bounded-error randomized solver on . The solver uses the same operational random-program model and succeeds with probability at least on both input classes. This premise is used only in Theorem 4.8.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Random
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
structure OrthogonalVectors where
k : ℕ
n : ℕ
d : ℕ
vectors : Fin k → Fin n → Bits d
distinct : ∀ i, Function.Injective (vectors i)
def OrthogonalVectors.yes (I : OrthogonalVectors) : Prop :=
∃ a : Fin I.k → Fin I.n, ∀ j : Fin I.d, ∃ i : Fin I.k, I.vectors i (a i) j = false
def OrthogonalVectors.encode (I : OrthogonalVectors) : Str :=
unary I.k ++ unary I.n ++ unary I.d ++
(List.ofFn fun i => (List.ofFn fun a => List.ofFn (I.vectors i a)).flatten).flatten
/-- Two-sided bounded error, including actual worst-case time on every random path. -/
noncomputable def OVSolver (k : ℕ) (c exponent C : ℝ) (P : RandomProgram) (n₀ : ℕ) : Prop :=
∀ I : OrthogonalVectors, I.k = k → max 2 n₀ ≤ I.n →
(I.d : ℝ) ≤ c * log2 I.n →
let B := C * (I.n : ℝ) ^ exponent
P.halts I.encode B ∧
P.prob I.encode B (fun y => (I.yes ∧ y = [true]) ∨ (¬ I.yes ∧ y = [false])) ≥ 2 / 3
noncomputable def RandomizedOVHypothesis : Prop :=
∀ k : ℕ, 2 ≤ k → ∀ ε : ℝ, 0 < ε → ∃ c : ℝ, 0 < c ∧
¬ ∃ (P : RandomProgram) (C : ℝ) (n₀ : ℕ),
0 < C ∧ OVSolver k c ((k : ℝ) - ε) C P n₀
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Hypothesis 2.2, printed p.9 (PDF p.11)