# CSAIL Event Calendar: Previous Series

 [A&C seminar] The homomorphism domination exponentSpeaker: Swastik Kopparty , MITDate: September 18 2008 Time: 4:00PM to 5:00PM Location: D507Host: Madhu Sudan, MITContact: Aleksander Madry, madry@mit.eduRelevant URL: http://people.csail.mit.edu/madry/algcompsem/For fixed graphs F and G, we study the relationship between the number of homomorphisms from F to T and from G to T for an arbitrary graph T. We define the homomorphism domination exponent of F and G, denoted by hde(F,G), to be the largest constant c such that |Hom(F,T)| \geq |Hom(G,T)|^c for all T. The decidability of "hde(F,G) \geq 1" is an important open question in database theory (known as the containment problem for conjunctive queries with multiset semantics). We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of F and G where hde(F,G) can be computed exactly. In particular, we show that hde(F,G) is computable when F is chordal and G is series-parallel. Our techniques are based on information theory and linear programming, and generalize the entropy variants of Shearer's lemma due to Radhakrishnan, Friedgut, Kahn and others. Joint work with Ben Rossman (MIT).See other events that are part of See other events happening in September 2008