Lunches
Speakers: Seungbum Jo
We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For 2 x n arrays, we first give upper and lower bounds on space for answering sorted and unsorted 3-sided Top-k queries. For m x n arrays, with m <=n and k <=mn, we obtain (m lg{(k+1)n choose n}+4nm(m-1)+o(n))-bit encoding for answering sorted 4-sided Top-k queries.
Speakers: Alfio Giarlotta
Semiorders are binary relations that are complete, Ferrers, and semitransitive. In particu- lar, they display a transitive asymmetric part (strict preference), and a usually intransitive symmetric part (indifference). Semiorders are among the most studied categories of binary relations in preference modeling. This is due to the vast range of economic scenarios which can modelled by appealing to the notion of ‘just noticeable difference’. We give a univer- sal characterization of semiorders, which uses the notions of a Z-product and a Z-line.
Speakers: Tom Kelly
In a fractional coloring, vertices of a graph are assigned subsets of the [0, 1]-interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most k if it admits a fractional coloring in which the amount of "color" assigned to each vertex is at least 1/k. We investigate fractional colorings where vertices "demand" different amounts of color, determined by local parameters such as the degree of a vertex.
Speakers: Jean-Paul Doignon
A typical two-stage process governs the selection of meal items in an Italian menu. The process admits a direct formalization in terms of choice spaces. Path-independent choice spaces are cryptomorphic to convex geometries (or antimatroids, introduced by Robert E. Jamison). There results a construction of a new convex geometry for a convex geometry (the base) given together with a family of convex geometries (the fibers) indexed by the elements of the base; we call the outcome a resolution.
Speakers: Vissarion Fisikopoulos
We experimentally study the problem of estimating the volume of convex polytopes, focusing on H- and V-polytopes, as well as zonotopes. Although a lot of effort is devoted to practical algorithms for H-polytopes there is no such method for the latter two representations. We propose a new, practical method for all representations, which is faster on H-polytopes; it relies on Hit-and-Run (HnR) sampling, and combines a new simulated annealing method with the Multiphase Monte Carlo (MMC) approach.
Speakers: Samuel Fiorini
Tomorrow Sam will tell us how to compute a maximum independent set in a graph embedded in a fixed surface if there are not many disjoint odd cycles in the graph. Note the unusual room: NO8.202 ("petit séminaire"), because of exams taking place in the other rooms.