Jonathan Mosheiff   (יונתן מושיוב)

I am a Senior Lecturer (Assistant Professor) at Ben-Gurion University's Department of Computer Science.

Until 2022 I was a postdoc at Carnegie Mellon University's School of Computer Science, hosted by Prof. Venkatesan Guruswami.

Prior to that, I was a postdoc at the Faculty of Mathematics and Computer Science at the Weizmann Institute, hosted by Prof. Irit Dinur.

I obtained my PhD at the School of Computer Science and Engineering at The Hebrew University under the guidance of Prof. Nati Linial. During my PhD, I was an Adams Fellow.

## Research Interests

• Broad interest in theory of computer science and combinatorics
• Error correcting codes
• The theory of group stability and testability and its connection to property testing

Here is my CV.

## Papers

• Sparsity and $\ell_p$-Restricted Isometry. Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff. Preprint. [pdf].

• Testability in Group Theory. Oren Becker, Alexander Lubotzky and Jonathan Mosheiff. Preprint. [pdf].

• Punctured Low-Bias Codes Behave Like Random Linear Codes. Venkatesan Guruswami and Jonathan Mosheiff. FOCS (2022). [pdf].

• $\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices. Venkatesan Guruswami, Peter Manohar and Jonathan Mosheiff. CCC (2022). [pdf].

• Testability of Relations Between Permutations. Oren Becker, Alexander Lubotzky and Jonathan Mosheiff. FOCS (2021). [pdf].

• Threshold Rates for Properties of Random Codes. Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas and Mary Wootters. ITCS (2021) (as "Sharp Threshold Rates for Random Codes"), IEEE Transactions on Information Theory (to appear). [pdf].

• LDPC Codes Achieve List Decoding Capacity. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters. FOCS (2020), special issue of SICOMP (to appear). [pdf].

• Bounds for List-Decoding and List-Recovery of Random Linear Codes. Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas and Mary Wootters. RANDOM (2020), IEEE Transactions on Information Theory (to appear). [pdf].

• Abelian Groups are Polynomially Stable. Oren Becker and Jonathan Mosheiff. International Mathematics Research Notices (2020). [pdf].

• On the Weight Distribution of Random Binary Linear Codes. Nati Linial and Jonathan Mosheiff. Random Structures & Algorithms (2020). [pdf].

• On the Rigidity of Sparse Random Graphs. Nati Linial and Jonathan Mosheiff. Journal of Graph Theory (2017). [pdf].

• Prime Languages. Orna Kupferman and Jonathan Mosheiff. MFCS (2013), special issue of Information and Computation (2015). [pdf].

### Papers outside of main research scope

• Two-machine Flow Shop and Open Shop Scheduling Problems with a Single Maintenance Window. "Gur Mosheiov, Assaf Sarig, Vitaly Strusevich and Jonathan Mosheiff. European Journal of Operational Research (2018).[pdf].

## Contact

My email username is mosheiff, and the domain is bgu.ac.il.