Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-MONOTONICITY:
Reports tagged with Non-monotonicity:
TR14-072 | 29th April 2014
Sajin Koroth, Jayalal Sarma

Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>




ISSN 1433-8092 | Imprint