Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUBMODULAR:
Reports tagged with submodular:
TR21-035 | 13th March 2021
Robert Robere, Jeroen Zuiddam

#### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

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 >>>

ISSN 1433-8092 | Imprint