OAI/Combinatorics/EditDistance/HashCuts.lean

GitHub source file

17 declarations, 0 contain sorry, 0 declared as axioms

Finite cut hashes and averaged separation

  1. def OAI.EditCutHash.sep line 14
  2. lemma OAI.EditCutHash.sep_nonneg line 15
  3. lemma OAI.EditCutHash.sep_le_one line 16
  4. lemma OAI.EditCutHash.sep_self line 17
  5. lemma OAI.EditCutHash.sep_eq_one line 18
  6. def OAI.EditCutHash.distance line 23
  7. lemma OAI.EditCutHash.distance_nonneg line 26
  8. def OAI.EditCutHash.coin line 29
  9. def OAI.EditCutHash.probability line 32
  10. def OAI.EditCutHash.key line 35
  11. lemma OAI.EditCutHash.coin_sum line 39
  12. lemma OAI.EditCutHash.probability_nonneg line 42
  13. lemma OAI.EditCutHash.probability_sum line 52
  14. lemma OAI.EditCutHash.collision_indicator line 58
  15. theorem OAI.EditCutHash.collision_probability line 75
  16. lemma OAI.EditCutHash.separation_probability line 91
  17. lemma OAI.EditCutHash.separation_bound line 102