# CS584 Reading Notes

## Minimum distance problem

As proved by Vardy [1], the problem of determining the minimum distance of a binary code is NP-complete. Further, Dumer et al prove that it is not possible to approximate a solution to this problem, to a factor better than $2^{\log^{1-\epsilon}(n)}$ [2].

In Cheng [3], the authors reduce an NP-complete problem using a randomized reduction to prove that minimum distance of algebraic geometry codes is NP-complete. Interestingly, Stephens-Davidowitz et al [4] prove that there are no non-trivial algorithms that can solve the minimum distance problem.

Thus possible study directions then in this topic would be to understand and prove the best known complexity bounds for this problem and find how close real-world algorithms are to these bounds.

## Applying coding theory to complexity
In the seminal paper by Trevisan [5], there are multiple applications of coding theory to problems in complexity. Some major themes are -

1. Using codes to improve algorithmic efficiency. For example number of bits used in secure communication, efficient use of random resources
2. Use of codes to characterize NP and P, to show that approximating an algorithm is as hard as the exact solution

Some interesting research directions are locally decodable codes, locally testable codes, reduction of approximation and exact solutions.

## Hash function design

Hash functions map an arbitrary string $\Sigma^k$ to a finite field $\mathcal{F}^n$. They are used in a wide range of applications such as cryptography, databases and others. There are certain requirements on the properties of hash functions that are useful in different application domains. For example, low rate of hash collisions prevents cryptographic attacks.

In Jutla et al [5], they prove that linear codes can be used to design good hash functions. There are some gaps in there analysis, which can be helpful direction to study.

## References

[1] - The intractability of computing the minimum distance of a code. [Link](https://ieeexplore.ieee.org/document/641542)

[2] - Hardness of approximating the minimum distance of a linear code. [Link](https://cseweb.ucsd.edu/~daniele/papers/DMS.pdf)

[3] - Hard problems of algebraic geometry codes. [Link](https://ieeexplore.ieee.org/document/4418467)

[4] - SETH-hardness of coding problems. [Link](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjx5IDGxp37AhVUjokEHYfCChEQFnoECBAQAQ&url=https%3A%2F%2Feccc.weizmann.ac.il%2Freport%2F2019%2F159%2Fdownload%2F&usg=AOvVaw2yLJayFlXSHO7ebY00AZ6U)

[5] - Some applications of coding theory in computational complexity. [Link](https://arxiv.org/pdf/cs/0409044.pdf)

[5] - Provably good codes for hash function design. [Link](https://ieeexplore.ieee.org/document/4729745)