Smaller gate-count circuits for GF(2^m) multipliers and the AES S-box, with Lean 4 proofs and verifiers
-
Updated
Oct 11, 2026 - Lean
#
circuit-complexity
Here are 8 public repositories matching this topic...
GF(2) Möbius / zeta transform in o(N log N) XOR gates, the first asymptotic improvement over Yates (1937) for circuits with cancellation: proofs, certificates, Lean 4 checks, and closed ideas. Asymptotic only, AI-checked, not yet human-refereed.
algorithms finite-fields theoretical-computer-science formal-verification open-problems reed-muller complexity-theory mathlib boolean-functions lean4 gf2 linear-circuits circuit-complexity algebraic-complexity mobius-transform zeta-transform yates-algorithm xor-circuits fast-transforms
-
Updated
Oct 11, 2026 - C
AI-assisted research notebook mapping P vs NP: proof barriers, adversarial falsification, reproducible experiments, formal verification, and a graveyard of failed ideas.
theorem-proving formal-verification sat computational-complexity automated-reasoning research-notes complexity-theory millennium-problems p-vs-np lean4 ai-mathematics circuit-complexity
-
Updated
Oct 24, 2026 - Python
Exact minimal integer-weight threshold circuits for every 4-input Boolean function (65,536 tables, 222 NPN classes): free-weight optima, capped Pareto frontiers, constructive forms, price of decomposability - all machine-verified.
-
Updated
Aug 7, 2026 - Python
CL-DIAG: Diagnosing canonicalization leakage in supervised learning under group symmetry
machine-learning deep-learning pytorch data-augmentation invariance neurips shortcut-learning boolean-functions group-symmetry circuit-complexity
-
Updated
Mar 20, 2026 - Python
First machine-verified formalization of the natural proofs barrier (Razborov-Rudich 1997) in Lean 4. Zero sorry obligations.
-
Updated
May 12, 2026 - TeX
Optimal depth for Bell-pair preparation on a 1D chain with fixed local resources, ideal coherent control, and independent noisy measurement reports.
information-theory quantum-information quantum-entanglement quantum-measurement entanglement-distribution circuit-complexity adaptive-quantum-circuits
-
Updated
Oct 25, 2026 - Python
Código del TFG de Ingeniería Informática / Code for the Computer Science Bacherlor's Thesis
-
Updated
Sep 3, 2025 - Python
Add this topic to your repo
To associate your repository with the circuit-complexity topic, visit your repo's landing page and select "manage topics."