It was shown some years ago that the computation time for many important Boolean functions of n arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n. On the other hand, it is known that every Boolean function of n ... more >>>

We investigate the computational complexity of the Boolean Isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for $\overline{BI}$, where the ... more >>>

For any Boolean function $f$ let $L(f)$ be its formula size complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and every $k\le n/2$, we describe a probabilistic distribution on formulas in the basis $\{\land,\oplus,1\}$ in some given set of $n$ variables and of the size at most $l(k)=4^k$. Let $p_{n,k}(f)$ ... more >>>

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered ... more >>>

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>