We adapt techniques from the constraint programming and satisfiability literatures to expedite the search for graph automorphisms. Specifically, we implement conflict-driven backjumping, several branching heuristics, andrestarts. To support backjumping, we extend high-performance search for graph automorphisms with a novel framework for conflict analysis. Empirically, these techniques improve performance up to several orders of magnitude.

The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time nlog n+O(1). The decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time nO(log log n). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of permutational isomorphism of permutation groups.

We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp (Otilde(k2radicn)), where n is the number of vertices. (The rank is the maximum size of edges; the tilde refers to a polylogarithmic factor.) The case of bounded k answers a 24-year-old question and removes an obstacle to improving the worst case-bound for Graph Isomorphism testing. The best previously known bound, even for k = 3, was Cn(Luks 1999).

Modern society is heavily dependent on wireless networks for providing voice and data communications. Wireless data broadcast has recently emerged as an attractive way to disseminate dynamic data to a large number of clients. In data broadcast systems, the server proactively transmits the information on a downlink channel; the clients access the data by listening to the channel. Wireless data broadcast systems can serve a large number of heterogeneous clients, minimizing power consumption as well as protecting the privacy of the clients' locations. The availability and relatively low cost of antennas resulted in a number of potential threats to the integrity of the wireless infrastructure. In particular, the data broadcast systems are vulnerable to jamming, i.e., the use of active signals to prevent data broadcast. The goal of jammers is to cause disruption, resulting in long waiting times and excessive power consumption. In this paper we investigate efficient schedules for wireless data broadcast that perform well in the presence of a jammer. We show that the waiting time of client can be reduced by adding redundancy to the schedule and establish upper and lower bounds on the achievable minimum waiting time under different requirements on the staleness of the transmitted data