Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Boolean functions with a vertex-transitive group of automorphisms

RSS-Feed




Revision #2
Authors: Petr Savicky
Accepted on: 14th May 2015 19:34
Downloads: 642
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
Downloads: 723
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
Downloads: 1790
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