This code is for proving lower bounds on the degree of a polynomial threshold function for the Boolean function (s,t)-AND-MAJ, the conjunction of s majority gates each with fan-in t. The case of s=2 was mostly resolved in a paper of OS10, which showed a lower bound of O(log t/log log t), almost matching the s=2 upper bound of O(log t) achieved by BRS91. The best known upper bounds for the case of general s are O(slog s log t) and O(\sqrt(t)log s) by BRS and ACW16. This code generalizes the linear programming approach of OS10 to higher s.

To make this code work, you need to either install [PuLP][https://pypi.org/project/PuLP/] or [Gurobi][https://www.gurobi.com/]. If you have a Gurobi license, you may use the install script to install it, replacing the installation directory and product key variables.