Campus Event Calendar
Event Entry
New for: D3
What and Who
An introduction to algebraic reduction methods for counting problems
Mingji Xia
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (basic education)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 11 November 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk, some known counting problems classes such as #CSP, Holant, and counting graph homomorphisms, are introduced in a more general framework called #BCSP. Two important reduction methods for counting problems, holographic reduction and polynomial interpolation are introduced, together with some simple application examples. We will understand the reduction methods, by exploring the conncetion between some linear algebra operations and some special graph gadgets.
Contact
Mingji Xia
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
counting compleixty; #CSP; holographic reduction; polynomial interpolation
Mengji Xia, 11/04/2011 14:37 -- Created document.