Monotonicity checking

In our thesis we consider the complexity of the monotonicity checking problem: given a finite poset and an unknown real-valued function on it find out whether this function is monotone. Two decision models were considered: the comparison model, where the queries are usual comparisons, and the linear model, where the queries are comparisons of linear combinations of the input. This is a report on our results.