Jonathan Mosheiff (יונתן מושיוב)
I am a Senior Lecturer (Assistant Professor) at Ben-Gurion University's Department of Computer Science.Prior to that, I held postdoc positions at Carnegie Mellon University and the Weizmann Institute.
Research Interests
Error correcting codes
Broad interest in theory of computer science and combinatorics
The theory of group stability and testability and its connection to property testing
Research
Selected Talks
| Title | Venue | Links |
|---|---|---|
| Probabilistic and Combinatorial Methods | Error-Correcting Codes: Theory and Practice Boot Camp at the Simons Institute for the Theory of Computing January 2024 | Part 1 Part 2 Part 3 |
| Derandomizing Random Linear Codes | Recent Advances in Coding Theory Workshop at STOC 2022 | Video |
Selected Publications
| Title | Authors | Venue | Links |
|---|---|---|---|
| When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? | Dean Doron Jonathan Mosheiff Mary Wootters | RANDOM 2024 | full version |
| Punctured Low-Bias Codes Behave Like Random Linear Codes | Venkatesan Guruswami Jonathan Mosheiff | FOCS 2022 Discrete Analysis | full version talk |
| ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices | Venkatesan Guruswami Peter Manohar Jonathan Mosheiff | CCC 2022 | full version talk by Peter |
| Testability of Relations Between Permutations | Oren Becker Alexander Lubotzky Jonathan Mosheiff | FOCS 2021 | full version talk |
| Threshold Rates for Properties of Random Codes (former name: Sharp threshold rates for random codes) | Venkatesan Guruswami Jonathan Mosheiff Nicolas Resch Shashwat Silas Mary Wootters | ITCS 2021 and IEEE Transactions in Information Theory | full version talk by Shashwat |
| LDPC Codes Achieve List Decoding Capacity | Jonathan Mosheiff Nicolas Resch Noga Ron-Zewi Shashwat Silas Mary Wootters | FOCS 2020 and SICOMP (special FOCS issue) | full version talk |
| Bounds for List-Decoding and List- Recovery of Random Linear Codes | Venkatesan Guruswami Ray Li Jonathan Mosheiff Nicolas Resch Shashwat Silas Mary Wootters | RANDOM 2020 and IEEE Transactions in Information Theory | full version talk by Nic |
Unpublished Manuscripts
| Title | Authors | Links |
|---|---|---|
| Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent | Matan Levi Jonathan Mosheiff Nikhil Shagrithaya | full version |
| Low-Degree Polynomials Are Good Extractors | Omar Alrabiah Jesse Goodman Jonathan Mosheiff João Ribeiro | full version |
| Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes | Jonathan Mosheiff Nicolas Resch Kuo Shang Chen Yuan | full version |
| Sparsity and ℓp-Restricted Isometry | Venkatesan Guruswami Peter Manoar Jonathan Mosheiff | full version |
Teaching
Courses I taught at BGU:
| Course | Semester |
|---|---|
| Design of Algorithms for Ashalim Students | Spring 24/25 |
| A Combinatorial Introduction to Coding Theory | Fall 23/24 |
| Algorithmic Problem Solving | Spring 22/23 |
As a grad student at HUJI I created the course Algorithmic Problem Solving with my friend Oren Becker.I was also a teaching assistant in Computability and Complexity for seven years. For six of them I had the pleasure of working and singing with Shaull Almagor (this is a playlist).
Students
| Name | Title | Degree | Date |
|---|---|---|---|
| Matan Levi | Threshold Phenomena in Coding Theory | PhD | October 2022 - Present |
I am looking for talented MSc and PhD students, as well as postdocs.
Contact
I am located in Room 312, Building 37 at the main BGU campus.My email is [email protected].
Refereed Publications
| Title | Authors | Venue | Links |
|---|---|---|---|
| When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? | Dean Doron Jonathan Mosheiff Mary Wootters | RANDOM 2024 | full version |
| Testability in Group Theory | Oren Becker Alexander Lubotzky Jonathan Mosheiff | Israeli Journal of Mathematics (2023) | full version |
| Punctured Low-Bias Codes Behave Like Random Linear Codes | Venkatesan Guruswami Jonathan Mosheiff | FOCS 2022 Discrete Analysis | full version talk |
| ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices | Venkatesan Guruswami Peter Manohar Jonathan Mosheiff | CCC 2022 | full version talk by Peter |
| Testability of Relations Between Permutations | Oren Becker Alexander Lubotzky Jonathan Mosheiff | FOCS 2021 | full version talk |
| Threshold Rates for Properties of Random Codes (former name: Sharp threshold rates for random codes) | Venkatesan Guruswami Jonathan Mosheiff Nicolas Resch Shashwat Silas Mary Wootters | ITCS 2021 and IEEE Transactions in Information Theory | full version talk by Shashwat |
| LDPC Codes Achieve List Decoding Capacity | Jonathan Mosheiff Nicolas Resch Noga Ron-Zewi Shashwat Silas Mary Wootters | FOCS 2020 and SICOMP (special FOCS issue) | full version talk |
| Bounds for List-Decoding and List- Recovery of Random Linear Codes | Venkatesan Guruswami Ray Li Jonathan Mosheiff Nicolas Resch Shashwat Silas Mary Wootters | RANDOM 2020 and IEEE Transactions in Information Theory | full version talk by Nic |
| Abelian Groups are Polynomially Stable | Oren Becker Jonathan Mosheiff | International Mathematics Research Notices (2020) | full version |
| On the Weight Distribution of Random Binary Linear Codes | Nati Linial Jonathan Mosheiff | Random Structures & Algorithms (2020) | full version |
| Two-machine Flow Shop and Open Shop Scheduling Problems with a Single Maintenance Window | Gur Mosheiov Assaf Sarig Vitaly Strusevich Jonathan Mosheiff | European Journal of Operational Research (2018) | full version |
| On the Rigidity of Sparse Random Graphs | Nati Linial Jonathan Mosheiff | Journal of Graph Theory (2017) | full version |
| Prime Languages | Orna Kupferman Jonathan Mosheiff | MFCS 2013 and Information and Computation (special MFCS issue) | full version |