A Boolean function is called vertex-transitive, if the partition of
the Boolean cube into the preimage of 0 and the preimage of 1 is invariant
under a vertex-transitive group of isometric transformations of the
Boolean cube. Although this is a very restrictive condition, there are
non-trivial functions satisfying this property.
The logarithm of the number of the vertex-transitive
functions of $n$ variables is $\Theta(n^2)$.
There is a polynomial over $\GF$ of any given degree,
which defines a vertex-transitive function, and
quadratic polynomials with this property can be characterized.
There are vertex-transitive functions of $n$ variables with sensitivity
and block sensitivity $\Theta(\log n)$.
For every vertex-transitive function, there is a representation
of roughly quadratic size in $n$,
which can be used to evaluate the function for a given input in
time $O(n^2)$ on random access machine.
- An improved estimate of the number of transitive functions.
- An example of a transitive function, which is not simply transitive.
- A construction of transitive functions with a logarithmic sensitivity.
A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. The logarithm of the number of the vertex-transitive functions of $n$ variables is at least $\Omega(n^2)$ and at most $O(n^2 \log n)$. There is a polynomial over $F_2$ of any given degree, which defines a vertex-transitive function, and quadratic polynomials with this property can be characterized. There is a vertex-transitive function of $n=4^k$ variables with sensitivity $n^{1/2}$. Some properties of the groups of the automorphisms of the vertex-transitive functions are presented.
A larger number of changes improving readability is introduced.
A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.
The formulation of statement (iii) of Lemma 7.1 is not correct in the original version of the paper.
However, this statement is valid with an additional assumption that the group H is a normal subgroup of G. Statement (iii) of Lemma 7.1 with this additional assumption is sufficient for the rest of the paper, since it is used for H, which has index 2 in G, and, hence, is normal.
