Vol. 13 no. 4

Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity


1. Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday

Seress, Akos ; Szegedy, Mario.
Honoring László (Laci) Babai's 60th birthday, the conference "Combinatorics, Groups, Algorithms, and Complexity" (Ohio State University, March 15-25, 2010) explored the links between the areas mentioned in the title. These areas represent Laci's wide interests in mathematics and […]

2. Computing tensor decompositions of finite matrix groups

Ankaralioglu, Nurullah ; Seress, Akos.
We describe an algorithm to compute tensor decompositions of central products of groups. The novelty over previous algorithms is that in the case of matrix groups that are both tensor decomposable and imprimitive, the new algorithm more often outputs the more desirable tensor decomposition.

3. Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem

Hayes, Thomas P..
For every positive integer k, we construct an explicit family of functions f : \0, 1\(n) -\textgreater \0, 1\ which has (k + 1) - party communication complexity O(k) under every partition of the input bits into k + 1 parts of equal size, and k-party communication complexity Omega (n/k(4)2(k)) under […]

4. On the minimal distance of a polynomial code

Pach, Peter Pal ; Szabo, Csaba.
For a polynomial f(x) is an element of Z(2)[x] it is natural to consider the near-ring code generated by the polynomials f circle x, f circle x(2) ,..., f circle x(k) as a vectorspace. It is a 19 year old conjecture of Gunter Pilz that for the polynomial f (x) - x(n) broken vertical bar x(n-1) […]

5. The extended equivalence and equation solvability problems for groups

Horvath, Gabor ; Szabo, Csaba.
We prove that the extended equivalence problem is solvable in polynomial time for finite nilpotent groups, and coNP-complete, otherwise. We prove that the extended equation solvability problem is solvable in polynomial time for finite nilpotent groups, and NP-complete, otherwise.

6. On the residual solvability of generalized free products of solvable groups

Kahrobaei, Delaram ; Majewicz, Stephen.
In this paper, we study the residual solvability of the generalized free product of solvable groups.

7. On the sensitivity of cyclically-invariant Boolean functions

Chakraborty, Sourav.
In this paper we construct a cyclically invariant Boolean function whose sensitivity is Theta(n(1/3)). This result answers two previously published questions. Turan (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Omega(root n). Kenyon and […]

8. Polynomial-time normalizers

Luks, Eugene M. ; Miyazaki, Takunari.
For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all of whose nonabelian composition factors lie in S-d; in particular, Gamma(d) includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the […]

9. On the metric dimension of Grassmann graphs

Bailey, Robert F. ; Meagher, Karen.
The metric dimension of a graph Gamma is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph G(q)(n, k) (whose vertices are the k-subspaces of F-q(n), and are adjacent […]