Towards a classical proof of exponential lower bound for 2-probe smooth codes

Rahul Jain

Let C: {0,1}^n -> {0,1}^m be a code encoding an n-bit string into an m-bit string. Such a code is called a (q, c, e) smooth code if there exists a decoding algorithm which while de…