|
|
 |
|
Mardi 12 Mars
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Reverse Chvatal-Gomory rank. |
| Description: |
Roland Grappe We introduce the reverse Chvatal-Gomory rank r*(P) of an integral
polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all
rational polyhedra whose integer hull is P. A well-known example in
dimension two shows that there exist integral polytopes P with r*(P)
infinite. We provide a geometric characterization of polyhedra with this
property in general dimension, and investigate upper bounds on r*(P)
when this value is finite.
This is a joint work with Michele Conforti, Alberto Del Pia, Marco Di
Summa and Yuri Faenza.  |
| Heure: |
14:00 - 17:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Bipartite subfamilies of planar graphs |
| Description: |
Juanjo Rué Perna I will survey the techniques used to get asymptotic results for subfamilies of planar graphs, as well as how to relate this methodology with the context of map enumeration. In the second part of the talk, I willexplain the ideas behind some on-going projects related to the enumeration of bipartite subfamilies of graphs. |
Vendredi 15 Mars
| Heure: |
13:30 - 14:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Linear Dependent Types For Differential Privacy |
| Description: |
Marco Gaboardi Differential privacy offers a way to answer queries about
sensitive information while offering strong, provable privacy guarantees.
Several tools have been developed for certifying that a given query is
differentially private. In one approach, Reed and Pierce[31] proposed a
functional programming language, Fuzz, for writing differentially private
queries. Fuzz uses linear types to track sensitivity, as well as a
probability monad to express randomized computation; it guarantees that any
program that has a certain type is differentially private. Fuzz can
successfully verify many useful queries. However, it fails when the
analysis depends on values that are not known statically.
We present DFuzz, an extension of Fuzz with a combination of linear indexed
types and lightweight dependent types. This combination allows a richer
sensitivity analysis that is able to analyze a larger class of queries,
including queries whose sensitivity depends on runtime information. As in
Fuzz, the differential privacy guarantees follows directly from the
soundness theorem for the type system. We demonstrate the enhanced
expressivity of DFuzz by certifying differential privacy a broad class of
iterative algorithms that could not be typed previously. We conclude by
discussing the challenges of DFuzz type checking. |
|
|
