Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with monotone functions:
TR21-026 | 23rd February 2021
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Conditional Dichotomy of Boolean Ordered Promise CSPs

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>

TR22-186 | 31st December 2022
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma

Power of Decision Trees with Monotone Queries

In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of ... more >>>

TR23-069 | 11th May 2023
Bruno Pasqualotto Cavalar, Igor Carboni Oliveira

Constant-depth circuits vs. monotone circuits

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

- For every $k \geq 1$, there is a monotone function in ${\rm AC^0}$ (constant-depth poly-size circuits) that requires monotone circuits of depth $\Omega(\log^k n)$. This significantly extends a classical result of Okol'nishnikova (1982) and Ajtai ... more >>>

ISSN 1433-8092 | Imprint