Short bio: 

Aurore Guillevic is researcher at Inria Nancy (a French research institute in computer science) and works on the implementation aspects of public-key cryptography (elliptic curves, pairings), and record computations (discrete logarithm computation in finite fields, integer factorization). She is visiting the Crypto and Security group until July 2022. 

Title:  

The knapsack algorithm in analytical chemistry 

Abstract:  

In analytical chemistry, one aims at identifying the chemical formula of unknown compounds, given the mass spectra from a Time of Flight Electron Ionisation Mass Spectrometer (ToF EI MS). For each measured mass, a knapsack algorithm enumerates the possible formulas, given the input masses of the elements H, C, N, O, F, S, Cl, Br, I. Because of the uncertainty of the measures, each target mass is an interval, and the enumeration produces too many candidates. In a second phase, we designed a likelihood estimator and an optimisation algorithm based in a pseudo-fragmentation graph encoded as a DAG. The procedure was successfully tested on  a training dataset of 36 known substances: CFC, PFC and HFC, and validated on a test set of 23 substances, 18 of the Kigali amendment to the Montreal protocol, 3 HFOs, and 3 other halogenated compounds. More than a hundred of new unknown atmospheric pollutants were detected in urban area air thanks to this work. Preprint available at hal.inria.fr/hal-03176025, Python scripts and datasets available at gitlab.inria.fr/guillevi/alpinac/ with L-GPL license. 

Joint work with Myriam Guillevic, Climate Gases Group (https://www.empa.ch/web/s503/climate-gases), EMPA, ETHZ, Switzerland.