Seminars & Colloquia Calendar
Construction of the Low-Degree Boolean Polynomials
John Chiarelli, Rutgers University
Location: Hill 705
Date & time: Thursday, 29 November 2018 at 5:00PM - 5:48PM
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.