### Article

## Exact Value of the Nonmonotone Complexity of Boolean Functions

We study the complexity of the realization of Boolean functions by circuits in infinite complete bases containing all monotone functions with zero weight (cost of use) and finitely many nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in the case where the only nonmonotone element of the basis is negation was completely described by A. A. Markov: the minimum number of negations sufficient for the realization of an arbitrary Boolean function *f* (the inversion complexity of the function *f*) is equal to ]log_2(*d*(*f*) + 1)[, where *d*(*f*) is the maximum (over all increasing chains of sets of values of the variables) number of changes of the function value from 1 to 0. In the present paper, this result is generalized to the case of the computation of Boolean functions over an arbitrary basis *B* of prescribed form. It is shown that the minimum number of nonmonotone functions sufficient for computing an arbitrary Boolean functionf is equal to ]log_2(*d*(*f*)/*D*(*B*)+1)[, where *D*(*B*) = max *d*(ω); the maximum is taken over all nonmonotone functions ω of the basis *B*.

The problem of multi-valued functions realization by circuits over special basis is inverstigated. The basis consis of Post negation and all monotone functions.

The complexity of realization of *k*-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function *x*+1(mod *k*)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function *f*, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (*d*(*f*)+1)+*O*(1), here *d*(*f*) is the maximum number of the value decrease of the value of *f* taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.

We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. Conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can only be of superpolynomial size. Positive existential and nonrecursive datalog rewritings of queries over ontologies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings are superpolynomial unless NP⊆P/poly. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and observe that the query entailment problem for such queries is fixed-parameter tractable.

We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL , linear Datalog± and sticky Datalog±. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP⊆P/poly. We also prove that nonrecursive datalog rewritings are in general exponentially more succinct than positive existential rewritings, while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants.

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains. A typical example of a general Boolean domain is {1,2}^*n* . We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest.

First we motivate the study of PTFs over the {1,2}^*n* domain by showing their close relation to depth two threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by polynomial size THR ∘ MAJcircuits. We note that known lower bounds for THR ∘ MAJ circuits extends to the likely strictly stronger model of PTFs. We also show that a “max-plus” version of PTFs are related to AC 0 ∘ THR circuits.

We exploit this connection to gain a better understanding of threshold circuits. In particular, we show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomial) size lower bounds for THR ∘ THR circuits.

Finally, having thus motivated the model, we initiate structural studies of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.

We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.

We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.

We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.

This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.