OAI/NumberTheory/TwoPoint/Circuits/CircuitSwitchingLemma.lean

GitHub source file

3 declarations, 0 contain sorry, 0 declared as axioms

A switching estimate sufficient for the fixed-depth application. The position/separator encoding gives a quadratic dependence on term width; this still yields polylogarithmic degree for every fixed circuit depth.

  1. lemma OAI.TwoPointCorrelations.finite_geometric_tail line 17
  2. theorem OAI.TwoPointCorrelations.canonicalDNFTree_switching line 46
  3. theorem OAI.TwoPointCorrelations.dnf_restriction_has_shallow_tree line 86