The size of the ball of radius d in Levenstein metric depends on the center of the ball. During this project it is suggested to investigate the distribution of the sizes of Levenstein balls, i.e. estimate the mathematical expectation and variance of the size, and find its maximal and minimum value.

For the case d=1 and 2 this question have already been addressed in papers [1] and [2] correspondingly, where some theoretical results have been obtained. The task of the project is to verify it with numerical computation, and obtain similar estimations for d>2.

[1] Bar-Lev, D., Etzion, T., & Yaakobi, E. (2021, July). On Levenshtein balls with radius one. In 2021 IEEE International Symposium on Information Theory (ISIT) (pp. 1979-1984). IEEE.

[2] He, L., & Ye, M. (2023, June). The size of Levenshtein ball with radius 2: Expectation and concentration bound. In 2023 IEEE International Symposium on Information Theory (ISIT) (pp. 850-855). IEEE.

In paper 

"Correcting a Single Error in Feedback Channels" the problem of correcting a single error with feedback was investigated. It was mainly devoted to binary channels, namely, binary symmetric and asymmetric channels. A general theorem, which allows constructing codes correcting one error with one feedback, was proved. For the symmetric channel with one error, it was proved that with two feedbacks one can transmit as many messages as with complete feedback.

In this project, it is proposed to generalize these results to the case of two errors. Namely, it is required to prove the theorem, which describes optimal codes, correcting 2 errors with one feedback. After that, some optimization problems should be solved to find the parameters of optimal codes.