Vol 13, No 4

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

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 theoretical computer science; his work has revealed and enriched many of the interconnections between them.

The conference had 109 participants from North America, Europe, Asia, and Australia (31 of them from overseas), including 3 Nevanlinna prize winners, 32 students, 13 postdocs, 20 females, and 18 former and current students of Laci Babai. The program consisted of 73 talks and a problem session. The full list of talks can be found in the introductory article by the guest editors of this special issue who also served as the organizers of the conference.

We thank all participants and speakers for the success of the conference. We wish to express our gratitude to the National Science Foundation, National Security Agency, and The Ohio State Mathematical Research Institute for their generous support.

This special issue contains papers in the conference topics, but not necessarily coinciding with the authors' talks at the conference. Each paper has been peer-reviewed. Toniann Pitassi, László Pyber, Uwe Schöning, Jiří Sgall, and Aner Shalev served with us as editors of this special issue. We thank for their work as well as for the assistance of the anonymous referees.

Akos Seress and Mario Szegedy, Guest Editors

Table of Contents

Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai’s 60th birthday PDF PostScript
Ákos Seress, Mario Szegedy 1-4
Computing tensor decompositions of finite matrix groups PDF PostScript
Nurullah Ankaralioglu, Ákos Seress 5-14
Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem PDF PostScript
Thomas P Hayes 15-22
The extended equivalence and equation solvability problems for groups PDF PostScript
Gábor Horváth, Csaba Szabó 23-32
On the minimal distance of a polynomial code PDF PostScript
Péter Pál Pach, Csaba Szabó 33-44
On the residual solvability of generalized free products of solvable groups PDF PostScript
Delaram Kahrobaei, Stephen Majewicz 45-50
On the sensitivity of cyclically-invariant Boolean functions PDF PostScript
Sourav Chakraborty 51-60
Polynomial-time normalizers PDF PostScript
Eugene M Luks, Takunari Miyazaki 61-96
On the metric dimension of Grassmann graphs PDF PostScript
Robert F Bailey, Karen Meagher 97-104


ISSN: 1365-8050