Abstract: Among square quadratic systems over F2, those with exactly one solution outnumber those with none — by one part in 2n, at every n, the opposite of the linear case. We give an explicit O(n3) injection from most solution-free systems to uniquely solvable ones, and read it against coNP, DP, NP and the planted-MQ assumption of post-quantum cryptography.
Il seminario si svolgerà in presenza presso il Dipartimento di Matematica e Fisica, Largo San Leonardo Murialdo, 1 - Edificio C - Aula C006
Link identifier #identifier__118786-1Locandina
This post is also available in:
Link identifier #identifier__195885-5
Eng