Permutations arise in a variety of real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations, however, is difficult since there are n! permutations, and unlike many problems, they cannot be represented effectively by graphical models due to the mutual exclusivity constraints typically associated with permutations. I will present a more effective representation which uses the "low-frequency'' terms of a Fourier decomposition to represent distributions over permutations compactly. For such representations to be truly useful, we need to be able to efficiently do inference, and to this end, I will discuss a set of useful inference operations, including marginalization and conditioning, which work completely in the Fourier domain. Performing inference on low frequency Fourier-based approximations, can often lead to functions which do not correspond to any valid distribution. To combat such errors, I will talk about a method for projecting approximations to a relaxed marginal polytope and demonstrate the effectiveness of the approach on a real camera-based multi-person tracking scenario. Finally, I will talk about approaches for splitting a distribution into independent factors and the inverse problem of merging independent factors to form a joint in the Fourier domain. I will discuss how the splitting and joining operations can be applied to our ongoing work on "adaptive inference", where we exploit independence in order to gain speedups for inference. This is joint work with Carlos Guestrin and Leonidas Guibas.