CSAIL Event Calendar: Previous Series
|
[A&C seminar] The homomorphism domination exponent Speaker: Swastik Kopparty , MIT Relevant 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.
|
