A Short Tutorial on the Theory of Monotone Systems' Identification

We include here several short presentations or fragments of presentations to provide introduction to this area of research, to its basic notions and results. These presentations are typically in PDF (or sometimes in post-script) format, and best if viewed in full screen mode.

There are many applications in which an implicitly given hypergraph (or set of vectors, or set of elements in the product of lattices, etc.) has to be generated. For a few typical problems of this type click here.
In these examples the input involves a definition/description, which is viewed and used as an oracle for the output. The length of the output in these problems is frequently much larger than the length of the input description. To measure the efficiency of generation, there are several definitions in the literature incorporating the lengths of both the input and the output. For the definitions of the three most frequently used such measures of complexity and for some properties of these measures click here.
Even though there are several results of this type in the literature (see here for a short overview), most of these are utilizing one of the handful mathematical techniques available either to prove that a generation problem is hard, or to construct an efficient algorithm. We provide here a short overview of some of the typical techniques used in the literature together with some illustrative, simple examples for their applications.
An important special case of generation problems is the identification of monotone systems, or equivalently, the generation of maximal independent sets of an independence system, when such systems are represented by a membership oracle. For definitions click here.
Let us note first that both of these problems are NP-hard generation problems, in general, according to the cited result by (Lawler, Lenstra and Rinnooy-Kan, 1980). Let us also note that most previously cited examples in fact belong to this family of problems, however the successful techniques we recalled from the literature utilize the input description in a much more substantial way than the computation of the values of the membership oracle would do. For a brief analysis of membership oracle based identification of monotone systems click here. This analysis shows that the very general technique of joint generation provides an efficient way to identify uniformly dual-bounded monotone systems.
Monotne systems can always be viewed as the set of minimal feasible solutions to an inquality of the form f(x) ł t, where f is a monotone function. In this research we proved that if f is one of the following types, then the set of minimal feasible solutions to the inequality f(x) ł t is uniformly dual-bounded, i.e., that it can be generated efficiently by joint generation:
In fact, conjunctions of uniformly dual-bounded systems can also be shown to be uniformly dual-bounded. Thus, the set of minimal feasible solutions to any system involving monotone inequalities of the above types is also uniformly dual-bounded. Let us further remark that the set of maximal infeasible solutions to such systems typically is not uniformy dual-bounded, and cannot be generated efficiently, unless P=NP.
It turns out that monotone systems arising in many important applications are in fact special cases of the above types of systems, and hence are uniformly dual-bounded. This implies that joint generation is a common efficient method for their generation. As examples, let us list below a number of such applications. In fact for most of these applications joint generation is the first, and only known non-exponential generation method.