Research Talks at the Zuse Institute Berlin

Differential privacy is a concept that can be used to express the extent to which algorithms like database queries, statistics and machine learning procedures, preserve a certain notion of privacy of an input dataset. Prominent applications of the technique include the US census and user data aggregation procedures of multiple large tech companies. The correct implementation of such algorithms requires a substantial amount of care, which motivated the development of type systems tailored to verify the differential privacy properties of programs. We implemented a type checker for one such type system and integrated it with the julia programming language to enable not only verification but automatic inference of privacy parameters for a reasonable subset of julia code.

For almost two decades, mixed integer programming (MIP) solvers have used graph-based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this talk, we discuss improvements for MIP conflict analysis by instead using reasoning based on cuts, inspired by the development of conflict-driven solvers for pseudo-Boolean optimization. Phrased in MIP terminology, this type of conflict analysis can be understood as a sequence of linear combinations, integer roundings, and cut generation. We leverage this MIP perspective to design a new conflict analysis algorithm based on mixed integer rounding cuts, which theoretically dominates the state-of-the-art method in pseudo-Boolean optimization using Chvátal-Gomory cuts. Furthermore, we discuss how to extend this cut-based conflict analysis from pure binary programs to mixed binary programs and-in limited form-to general MIP with also integer-valued variables. Our experimental results indicate that the new algorithm improves the default performance of SCIP in terms of running time, number of nodes in the search tree, and the number of instances solved.

We present a framework that transforms geometric and combinatorial problems into optimization tasks by designing loss functions that vanish precisely when the desired coloring properties are achieved. We employ neural networks trained through gradient descent to minimize these loss functions, allowing for efficient exploration of the solution space. We demonstrate the effectiveness of the method on variants of the Hadwiger-Nelson problem, which asks for plane colorings that avoid monochromatic unit-distance pairs and sketch how the approach can be applied to other problems.