Monotonicity checking

Kyureghyan M (2004)
Bielefeld (Germany): Bielefeld University.

Download
OA
Bielefeld Dissertation | English
Author
Supervisor
Ahlswede, Rudolf (Prof. Dr. Dr. h.c.)
Alternative Title
Monotonie-Überprüfung
Abstract
The monotonicity checking problem is a sorting-type problem defined as: Given a finite poset and an unknown real-valued function on it, find out whether this function is order preserving. We investigate the worst case behaviour of decision monotonicity checking algorithms. Two models are considered: the comparison model and the linear model. In the comparison model the queries are pairwise comparisons of values of the function. We get some general bounds on monotonicity checking complexity and analyse the dependence of the complexity of monotonicity checking on certain type of combinatorial operations on posets. We determine the monotonicity checking complexity of the ranked poset in which every two elements of different rank are comparable and get nontrivial lower and upper bounds on the complexity of monotonicity checking of the Boolean lattice. Also, we investigate monotonicity checking of functions that take a "small" number of different values and determine the monotonicity checking complexity of Boolean functions. The queries in this model are comparisons of linear combinations of the values of the input function. We consider a geometric interpretation of monotonicity checking and give a method for establishing lower bounds on the complexity of monotonicity checking in the linear model using this interpretation. We use this method to establish a lower bound on the monotonicity checking complexity of a particular poset. As a consequence, we get a lower bound on the complexity of simultaneous determination of the minimum and the maximum of a sequence of real numbers.
Year
PUB-ID

Cite this

Kyureghyan M. Monotonicity checking. Bielefeld (Germany): Bielefeld University; 2004.
Kyureghyan, M. (2004). Monotonicity checking. Bielefeld (Germany): Bielefeld University.
Kyureghyan, M. (2004). Monotonicity checking. Bielefeld (Germany): Bielefeld University.
Kyureghyan, M., 2004. Monotonicity checking, Bielefeld (Germany): Bielefeld University.
M. Kyureghyan, Monotonicity checking, Bielefeld (Germany): Bielefeld University, 2004.
Kyureghyan, M.: Monotonicity checking. Bielefeld University, Bielefeld (Germany) (2004).
Kyureghyan, Marina. Monotonicity checking. Bielefeld (Germany): Bielefeld University, 2004.
Main File(s)
File Name
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar