BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20261022T224525Z
UID:Seminar-dept-1504@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20261013T130000
DTEND:20261013T140000
SUMMARY:School Seminar Series
DESCRIPTION:Yelena Yuditsky: Biclique decompositions from Welzl orders\n\nA biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We are interested in biclique decompositions of small size, where the size of a decomposition is defined as the sum of the numbers of vertices in its bicliques.\n\n\n\nWe consider graphs whose vertices admit an ordering such that the neighborhood of every vertex is the union of a sublinear number of intervals. For this class of graphs, we establish bounds on the size of biclique decompositions and provide an algorithm for constructing such decompositions.\n\n\n\nOur results have several applications, including upper bounds for the Zarankiewicz problem, as well as applications to matrix multiplication, quantum circuit complexity, and shortest-path algorithms.\n\n\n\nThis is a joint work with Jean Cardinal and Rose McCarty. \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1504
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR