We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains. To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang’s sensitivity theorem using "pseudo-characters", which witness the degree of a function. Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.

The index erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight Ω(√n) lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. To prove our main result, we first extend the so-called automorphism principle (Høyer et al. STOC 2007) to the general adversary method for state conversion problems (Lee et al. STOC 2011), which allows one to exploit the symmetries of these problems to lower bound their quantum query complexity. Using this method, we establish a strong connection between the quantum query complexity of non-coherent symmetric state generation problems and the well-known Krein parameters of association schemes. Krein parameters are usually hard to determine, nevertheless, we give a novel way of computing certain Krein parameters of a commutative association scheme defined over partial permutations. We believe the study of this association scheme may also be of independent interest.

We consider the algebraic combinatorics of the set of injections from a k-element set to an n-element set. In particular, we give a new combinatorial formula for the spherical functions of the Gelfand pair (Sk× Sn, diag(Sk) × Sn-k). We use this combinatorial formula to give new Delsarte linear programming bounds on the size of codes over injections.

For even k ∊ ℕ, the matchings connectivity matrix Mk is a binary matrix indexed by perfect matchings on k vertices; the entry at (M, M‘) is 1 iff M ∪ M‘ forms a single cycle. Cygan et al. (STOC 2013) showed that the rank of Mk over ℤ is and used this to give an time algorithm for counting Hamiltonian cycles modulo 2 on graphs of pathwidth pw, carrying over to the decision problem via witness isolation. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within Mk, which enabled a “pattern propagation” commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar “pattern propagation” when only a black-box lower bound on the asymptotic rank of Mk is given; no stronger structural insights such as the existence of large permutation submatrices in Mk are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes p) parameterized by pathwidth. To apply this technique, we prove that the rank of Mk over the rationals is 4k/poly(k), using the representation theory of the symmetric group and various insights from algebraic combinatorics. We also show that the rank of Mk over ℤp is Ω(1.57k) for any prime p ≠ 2. Combining our rank bounds with the new pattern propagation technique, we show that Hamiltonian cycles cannot be counted in time O*((6 – ε)pw) for any ε > 0 unless SETH fails. This bound is tight due to a O*(6pw) time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes p ≠ 2 in time O*(3.57pw), indicating that the modulus can affect the complexity in intricate ways.

Tucker characterized the minimal forbidden submatrices of binary matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find such a minimal one in any binary matrix that does not have the consecutive-ones property. Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find such a minimal one in any graph that is not an interval graph.