John Chiarelli, Rutgers University

Abstract

  The degree of a boolean function is an important measure of its complexity, but finding all such functions quickly becomes very computationally dense. In this talk, I will discuss the way in which we can use a property of boolean functions, called the maxonomial hitting set size, to aid in generating all boolean polynomials of degree 3, and how we can take advantage of symmetries to improve our runtime. I will also talk about how this catalog is useful in gaining a greater understanding of the maxonomial hitting set size of arbitrary functions