Description
Le problème NP-complet classique de la satisfiabilité d'une formule Booléenne mise sous forme normale conjonctive a connu un intérêt croissant non seulement dans la communauté d'informatique théorique, mais aussi dans des domaines d'applications divers ou une solution pratique à ce problème permet des avancées significatives. Depuis les premiers développements de la procédure de base proposée par Davis, Putnam, Logemann et Loveland (DPLL), il y a plus d'une quarantaine d'années, ce domaine a connu un effort de recherche croissant ayant abouti aux solveurs SAT modernes d'aujourd'hui, capable de résoudre des instances de plusieurs centaines de milliers et même de millions de variables. Dans cet exposé, nous examinerons les idées principales ayant permis ce passage à l'échelle et nous évoquerons quelques directions possibles pour des recherches futures.
Next sessions
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Speaker : Hugo Beguinet - ENS Paris / Thales
The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these[…]-
Cryptography
-
Asymmetric primitive
-
Mode and protocol
-
-
Post-quantum Group-based Cryptography
Speaker : Delaram Kahrobaei - The City University of New York