I mostly worry about non-linearity, Gauss took care about the rest And for gate minimization part of the puzzle take a look at

Arist Kojevnikov Alexander S. Kulikov Grigory Yaroslavtsev
Finding Effcient Circuits Using SAT-solvers

E. Demenkov A. Kojevnikov A. Kulikov G. Yaroslavtsev
New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions