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.