Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MONOTONE COMPUTATION:
Reports tagged with monotone computation:
TR21-100 | 11th July 2021
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

#### Karchmer-Wigderson Games for Hazard-free Computation

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games.

Using this game, we ... more >>>

TR22-031 | 16th February 2022
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

#### Transparency Beyond VNP in the Monotone Setting

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be ... more >>>

TR22-071 | 13th May 2022
We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:
(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>