Middle East Technical University Institute of Applied Mathematics Seminars

The Multiplicative Complexity of 6-variable Boolean Functions
Çağdaş Çalık
The National Institute of Standards and Technology (NIST), USA, Turkey
Özet : The multiplicative complexity of a Booleanfunction is the minimum number of AND gates that are necessary and sufficientto implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable,even for functions with small number of inputs. Turan et al. showed thatn-variable Boolean functions can be implemented with at most n-1 AND gates forn < 6. A counting argument can be used to show that, for n > 6, thereexist n-variable Boolean functions with multiplicative complexity of at leastn. In this talk, we will describe a method to find the multiplicativecomplexity of Boolean functions by analyzing circuits with a particular numberof AND gates and utilizing the affine equivalence of functions. We use thismethod to study the multiplicative complexity of 6-variable Boolean functions,and calculate the multiplicative complexities of all 150,357 affine equivalence classes. We showthat any 6-variable Boolean function can be implemented using at most 6 ANDgates. Additionally, we exhibit specific 6-variable Boolean functions whichhave multiplicative complexity 6.
  Tarih : 20.03.2018
  Saat : 15:40
  Yer : Institute of Applied Mathematics, S212
  Dil : English
  Web : http://iam.metu.edu.tr/event-calendars#colloquia