Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>