{"id":"palomar/PALOMAR-2026-11-09-000020","url":"https://github.com/bishara74/lowhalf-mul3/tree/b6c00ef8d94ff578585b428270df1af271a96bd6","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-09-000020-v1.json","repo":"https://github.com/bishara74/lowhalf-mul3","tags":["cs.CC","msc:68Q06","msc:68Q17","msc:94D10"],"score":0,"title":"Unrestricted Boolean multiplicative complexity of the 3x3 low-half multiplier","trust":"high","domain":"cs.CC","source":"palomar","authors":["Bshara Alhodali"],"reviews":0,"subject":"cs.CC","summary":"Formalizes the target lowMul3, the three low bits of the product of two 3-bit integers (the product modulo 8), in the unrestricted XOR--AND circuit model of arXiv:2608.30238v1, where XOR and constants are free and either input of a paid AND gate may reuse arbitrary earlier nonlinear wires. Phase 1 proves that the three ANF coordinates agree with integer multiplication modulo 8 on all 64 inputs, and gives an explicit six-gate circuit, one of whose gates reuses two earlier nonlinear wires. Phase 2 adds the derivative lemma (Lemma 8 of the four-gate note in paper/notes/). Phase 3 proves the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-09","reactions":{},"formalized":true,"formalizes":[{"title":"The multiplicative complexity of the three-bit low-half multiplier","identifier":"","relationship":"formalizes"}]}