Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms ... more >>>