ECCC-Report TR13-191https://eccc.weizmann.ac.il/report/2013/191Comments and Revisions published for TR13-191en-usThu, 14 May 2015 19:34:05 +0300
Revision 2
| Boolean functions with a vertex-transitive group of automorphisms |
Petr Savicky
https://eccc.weizmann.ac.il/report/2013/191#revision2A 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.Thu, 14 May 2015 19:34:05 +0300https://eccc.weizmann.ac.il/report/2013/191#revision2
Revision 1
| Boolean functions with a vertex-transitive group of automorphisms |
Petr Savicky
https://eccc.weizmann.ac.il/report/2013/191#revision1A 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.
Wed, 07 Jan 2015 13:22:43 +0200https://eccc.weizmann.ac.il/report/2013/191#revision1
Comment 1
| Correction |
Petr Savicky
https://eccc.weizmann.ac.il/report/2013/191#comment1The 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.
Mon, 20 Jan 2014 20:41:53 +0200https://eccc.weizmann.ac.il/report/2013/191#comment1
Paper TR13-191
| Boolean functions with a vertex-transitive group of automorphisms |
Petr Savicky
https://eccc.weizmann.ac.il/report/2013/191A 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.
Sat, 28 Dec 2013 21:50:52 +0200https://eccc.weizmann.ac.il/report/2013/191