Fancy reductions between counting problemsSpeaker: Ben
Title: Fancy reductions between counting problems
Date: 11 Nov 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Abstract: If you want to reduce an NP problem A to another NP problem B, you’ll probably give a many-one reduction: an algorithm that converts a given instance φ of A into an instance φ’ of B such that solutions of φ map to solutions of φ’. If you want to reduce between problems in #P (the counting analog of NP), you can still use many-one reductions, but you can also perform exotic reductions that rely on linear algebra and don’t preserve individual solutions. Polynomial interpolation maps an instance φ of A to a whole family of instances of B; solving a resulting system of equations yields the number of solutions to φ. A holographic reduction maps φ to φ’ but doesn’t preserve individual solutions; rather, counting the number of solutions to φ’ is equivalent to counting the number of solutions to φ up to a ‘change of basis’. I’ll introduce these two reduction methods (both due to Valiant). No background in counting complexity will be assumed.