Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Many Boolean functions have short representations by OBDDs (ordered

binary decision diagrams) if appropriate variable orderings are used.

For tree-like circuits, which may contain EXOR-gates, it is proved

that some depth first traversal leads to an optimal variable ordering.

Moreover, an optimal variable ordering and the resulting OBDD

can ...
more >>>

E.A. Okol'nishnikiva

Some operations over Boolean functions are considered. It is shown that

the operation of the geometrical projection and the operation of the

monotone extension can increase the complexity of Boolean functions for

formulas in each finite basis, for switching networks, for branching

programs, and read-$k$-times ...
more >>>

Scott Aaronson

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>

Gyula Gyôr

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Sergei Lozhkin, Alexander Shiganov

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]

that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most

$$

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

$$

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Avishay Tal

For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ is the value of $f$ on $n$ inputs, each of them is the calculation of $g$ on a distinct set of $m$ Boolean variables. Motivated ... more >>>

Srikanth Srinivasan, S Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami ... more >>>

Aniruddha Biswas, Palash Sarkar

The influence of a set of variables on a Boolean function has three separate definitions in the literature, the first due to Ben-Or and Linial (1989), the second due to Fischer et al. (2002) and Blais (2009) and the third due to Tal (2017). The goal of the present work ... more >>>