Applications in Complexity Theory and Cryptography
Algorithms developed for list decoding of several interesting code families have found interesting applications in computational complexity and the field of cryptography. Following is a sample list of applications outside of coding theory:
- Construction of hard-core predicates from one-way permutations.
- Predicting witnesses for NP-search problems.
- Amplifying hardness of Boolean functions.
- Average case hardness of permanent of random matrices.
- Extractors and Pseudorandom generators.
- Efficient traitor tracing.
Read more about this topic: List Decoding
Famous quotes containing the words complexity and/or theory:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“Many people have an oversimplified picture of bonding that could be called the “epoxy” theory of relationships...if you don’t get properly “glued” to your babies at exactly the right time, which only occurs very soon after birth, then you will have missed your chance.”
—Pamela Patrick Novotny (20th century)