Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-191 | 14th May 2015 19:34

Boolean functions with a vertex-transitive group of automorphisms

Revision #2
Authors: Petr Savicky
Accepted on: 14th May 2015 19:34
Keywords:

Abstract:

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.

Changes to previous version:

- 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.

Revision #1 to TR13-191 | 7th January 2015 13:22

Boolean functions with a vertex-transitive group of automorphisms

Revision #1
Authors: Petr Savicky
Accepted on: 7th January 2015 13:22
Keywords:

Abstract:

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.

Changes to previous version:

A larger number of changes improving readability is introduced.

Paper:

TR13-191 | 26th December 2013 19:21

Boolean functions with a vertex-transitive group of automorphisms

TR13-191
Authors: Petr Savicky
Publication: 28th December 2013 21:50
Keywords:

Abstract:

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.

Comment(s):

Comment #1 to TR13-191 | 20th January 2014 20:41

Correction

Authors: Petr Savicky
Accepted on: 20th January 2014 20:41
Keywords:

Comment:

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.

ISSN 1433-8092 | Imprint