Generic Error SDP and Generic Error CVE
Vortrag von Prof. Dr. Felice Manganiello
Datum: 06.12.23 Zeit: 16.00 - 17.00 Raum:
In this talk we generalize the concept of error sets beyond those defined by a metric and use the set-theoretic difference operator to characterize when these error sets are detectable or correctable by codes. We prove the existence of a general, metric-less form of the Gilbert-Varshamov bound, and show that - like in the Hamming setting - a random code corrects a generic error set with overwhelming probability. We define the generic error SDP (GE-SDP), which is contained in the complexity class of NP-hard problems, and use its hardness to demonstrate the security of generic error CVE (GE-CVE). This is a joint work with Freeman Slaughter.