7 citations · 12 across the 5 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.CC2014
Constructive Relationships Between Algebraic Thickness and Normality
Joan Boyar, Magnus Gausdal Find
We study the relationship between two measures of Boolean functions; \emph{algebraic thickness} and \emph{normality}. For a function , the algebraic thickness is a variant of th…
cs.CC2014
Multiplicative Complexity of Vector Valued Boolean Functions
Magnus Gausdal Find, Joan Boyar
We consider the multiplicative complexity of Boolean functions with multiple bits of output, studying how large a multiplicative complexity is necessary and sufficient to provide a…
cs.CC2014
On the Complexity of Computing Two Nonlinearity Measures
Magnus Gausdal Find
We study the computational complexity of two Boolean nonlinearity measures: the nonlinearity and the multiplicative complexity. We show that if one-way functions exist, no algorith…