On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
Questo lavoro dimostra che gli algoritmi più veloci per l'approssimazione del problema del vettore più vicino (CVP) implicherebbero miglioramenti significativi per Max-Cut e Max-2-Lin(2), fornendo evidenze sulla necessità di tempo esponenziale per CVP e mostrando che la sicurezza post-quantistica della crittografia basata sui reticoli non può essere sostenuta da QSETH a causa di limitazioni nelle riduzioni quantistiche non adattive.