8 citations · 25 across the 28 of their papers we have counts for
4 papers · 1 filter
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…
The Advice Complexity of a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice…
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…
Tight Bounds for Restricted Grid Scheduling
Joan Boyar, Faith Ellen
The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remai…