7 citations · 12 across the 5 of their papers we have counts for
5 papers
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…
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…
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…
Cancellation-Free Circuits in Unbounded and Bounded Depth
Joan Boyar, Magnus Find
We study the notion of "cancellation-free" circuits. This is a restriction of linear Boolean circuits (XOR circuits), but can be considered as being equivalent to previously studie…
Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
Joan Boyar, Magnus Find
We continue to study the notion of cancellation-free linear circuits. We show that every matrix can be computed by a cancellation- free circuit, and almost all of these are at most…