OAI/Combinatorics/LowSpaceSubsetSum/Separators/SeparatorCheck.lean

GitHub source file

14 declarations, 0 contain sorry, 0 declared as axioms

Four-block weighted disjointness check

A top mask has four local blocks of g indices. The check preprocesses both compatibility tables, traverses the useful tuples without storing them, and uses the first-match weight search at each terminal branch.

  1. abbrev OAI.LowSpaceSubsetSum.SeparatorCheck.Record line 19
  2. def OAI.LowSpaceSubsetSum.SeparatorCheck.localMask line 21
  3. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.localMask_mem line 24
  4. def OAI.LowSpaceSubsetSum.SeparatorCheck.blocks line 27
  5. def OAI.LowSpaceSubsetSum.SeparatorCheck.run line 31
  6. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.ofFamily_pair_good line 35
  7. def OAI.LowSpaceSubsetSum.SeparatorCheck.Covered line 51
  8. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.pairGood_iff line 56
  9. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.correct line 61
  10. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.covered_disjoint line 68
  11. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.sound line 76
  12. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.finds_fixed_pair line 83
  13. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.peak_le line 90
  14. theorem OAI.LowSpaceSubsetSum.SeparatorCheck.peak_capacity line 95