Theorem 1 — every 1-rectangle cover of has size
ProvedExtensionComplexity.TSP.rectangle_cover_lower_boundcommunication-complexitylower-boundp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1rectangle-cover
Let be the matrix indexed by -bit strings, and let be its support matrix. Theorem 1 (de Wolf 2003): every -monochromatic rectangle cover of has size . That is, there are and such that for all , if are rectangles each containing only -entries of and together containing all of them, then
Equivalently, the function has nondeterministic communication complexity . Combined with Theorem 4 this gives , the source of all lower bounds in the mission.
Formalization Note is read as: there exist and with (real power) for all . Rectangles are arbitrary pairs of sets of bit strings and may overlap.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_CorrelationMatrix import Definitions.Def_ExtensionComplexity_TSP_SlackMatrix
Formal statement
namespace ExtensionComplexity.TSP
/-- **Theorem 1** [de Wolf 2003] (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:8): every
1-monochromatic rectangle cover of `suppmat(M)`, `M = M(n)`, has size `2^{Ω(n)}`: there are
`C > 0` and `N` such that for every `n ≥ N`, every cover of the 1-entries of the support of
`M(n)` by `k` 1-monochromatic rectangles has `k ≥ 2^{Cn}`. -/
theorem rectangle_cover_lower_bound :
∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n ≥ N, ∀ (k : ℕ)
(R : Fin k → Set (Fin n → Bool) × Set (Fin n → Bool)),
IsOneRectangleCover (suppM n) R → (2 : ℝ) ^ (C * n) ≤ k := by sorry
end ExtensionComplexity.TSP
Source
Fiorini, Massar, Pokutta, Tiwary, de Wolf, Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62(2) (2015), Art. 17, p. 17:8, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.