BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:773@lincs.fr
DTSTART;TZID=Europe/Paris:20230517T103000
DTEND;TZID=Europe/Paris:20230517T113000
DTSTAMP:20230629T135623Z
URL:https://www.lincs.fr/events/sorting-under-partial-information/
SUMMARY:Sorting under Partial Information
DESCRIPTION:We present the following article: Cardinal\, Fiorini\, Joret\,
 Jungers\, and Munro. Sorting under partial information (without the
 ellipsoid algorithm). Proceedings of the forty-second ACM symposium on
 Theory of computing. 2010.\n\n"We revisit the well-known problem of sorting
 under partial information: sort a finite set given the outcomes of
 comparisons between some pairs of elements. The input is a partially
 ordered set P\, and solving the problem amounts to discovering an unknown
 linear extension of P\, using pairwise comparisons. The
 information-theoretic lower bound on the number of comparisons needed in
 the worst case is log e(P)\, the binary logarithm of the number of linear
 extensions of P. In a breakthrough paper\, Jeff Kahn and Jeong Han Kim
 (STOC 1992) showed that there exists a polynomial-time algorithm for the
 problem achieving this bound up to a constant factor. Their algorithm
 invokes the ellipsoid algorithm at each iteration for determining the next
 comparison\, making it impractical.\n\nWe develop efficient algorithms for
 sorting under partial information. Like Kahn and Kim\, our approach relies
 on graph entropy. However\, our algorithms differ in essential ways from
 theirs. Rather than resorting to convex programming for computing the
 entropy\, we approximate the entropy\, or make sure it is computed only
 once in a restricted class of graphs\, permitting the use of a simpler
 algorithm."
CATEGORIES:Network Theory,Working Group,Youtube
LOCATION:Room 4B01\, 19 place Marguerite Perey\, Palaiseau\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=19 place Marguerite Perey\,
 Palaiseau\, France;X-APPLE-RADIUS=100;X-TITLE=Room 4B01:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20230326T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR