Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NEGATION-LIMITED COMPLEXITY:
Reports tagged with negation-limited complexity:
TR15-026 | 21st February 2015
Siyao Guo, Ilan Komargodski

Negation-Limited Formulas

Revisions: 1

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>




ISSN 1433-8092 | Imprint