BOOLE: Quantifying Boolean Frameworks – BOOLE

Boolean logical frameworks are ubiquitous in Computer Science. For computers, information is binary; the circuits (microprocessors, digital signal processors known as DSP, ...) that process it are entirely based on boolean logic; the algorithms and programs that transmit it, emph{encrypt} it, correct it, are based on binary logic (in fact, often on extensions of binary finite fields). Many large-scale combinatorial problems are attacked by algorithms and software directed at solving constraint satisfaction problems, which are none other than basic extensions of the boolean paradigm. Most of the problems arising from boolean frameworks are computationally highly intensive. The implication is the following: When faced with a given (large) problem instance, a great many algorithmic alternatives are possible, but it is hard to know in advance which one should best be used. What is badly needed are methodologies dedicated at predicting with sufficient likelihood which strategy is most likely to succeed in each specific context. In an ideal world, one would then like to have a way of matching accessible structural indicators of boolean problems with the probabilistic behaviour of the complexity of solution strategies. This is precisely where our proposal fits. Our global objective is to quantify the expressive power of major boolean frameworks. By this we mean developing models with which to predict what should hold or not hold in a high number of cases; in other words we want to elucidate statistical properties of boolean structures. This approach departs significantly from the usual worst-case analyses. The eventual goal is to provide powerful guidance in the choice of the best representation or algorithm adapted to a given context, and, in a number of cases, develop new algorithmic strategies based on sound analytic results. In summary, we propose to develop a coherent and general-purpose mathematical toolbox with which to measure and compare quantitative (probabilistic) properties of boolean frameworks regarding computational aspects. The coherence of our proposal stems both from the fact that boolean functions form the common basis of all our investigations, and from the methods that we propose to use and develop, based on analytic combinatorics and probability theory. So far, the scientific communities engaged in research regarding boolean functions and random discrete structures have had very few interactions, and the techniques that we shall develop have been very rarely applied to boolean objects. To summarise, we believe that the novelty of our project is twofold: the introduction of new methods in the analysis of boolean frameworks; the extension of analytic combinatorics and probabilistic methods to a new kind of discrete structures.