Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MONOTONE FUNCTIONS:
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 >>>




ISSN 1433-8092 | Imprint