Klim Efremenko - קלים יפרמנקו

Klim Efremenko

I am a faculty member at the School of Computer Science at Ben Gurion University.
My main research interests are Error Correcting Codes, Interactive Communication and Computational Complexity.

[Info] [Short Bio] [Teaching] [Call for Postdocs & Interns]

Contact Information

Office: Ben-Gurion University Building 37, Room 303
Phone:+972-3-6407996
Email: [first] [at] bgu.ac.il
Mail: Klim Efremenko, Ben-Gurion University P.O. Box 653 Beer-Sheva 84105, Israel

Short Biography

I am a faculty member of the School of Computer Science at Ben Gurion University.
2015-2017 I was post-doc at Tel-Aviv University where I work with Amir Shpilka
I was a fellow at Simons Institute at Berekeley during 2015.
Before that I was a Simons Fellow at University of Chicago
And a member at Institute for Advanced Study in the group of Avi Wigderson I graduated with a Ph.D. in Computer Science in 2012 from the Tel-Aviv University, where I was advised by Prof. Amnon Ta-Shma and Oded Regev.


Grants
[2018-2022] Israel Science Foundation (ISF) -- Individual research grant.
[2020-2026] European Research Council(ERC) strating grant

Call for Postdocs and Interns

I am looking for post-docs and students who are interested in working on the field of Error Correcting Codes and Interactive Communication. Full call is here

    Publications


  1. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Optimal Error Resilience of Adaptive Message Exchange
    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
    [Abstract] [Paper: PDF]

  2. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Binary Interactive Error Resilience Beyond 1/8
    Foundations of Computer Science (FOCS 2020)
    [Abstract] [Paper: PDF]

  3. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Interactive Error Resilience Beyond $\frac{2}{7}$
    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
    [Abstract] [Paper: PDF]

  4. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Radio Network Coding Requires Logarithmic Overhead.
    Foundations of Computer Science (FOCS 2019)
    [Abstract] [Paper: PDF]

  5. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Interactive coding over the noisy broadcast channel
    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing(STOC 2018)
    [Abstract] [Paper: PDF]

  6. Klim Efremenko and Gillat Kol and Raghuvansh Saxena
    Noisy Beeps

    Principles of Distributed Computing (PODC) 2020 [Abstract] [Paper: PDF]

  7. Mark Braverman and Klim Efremenko and Ran Gelles and Michael A. Yitayew:
    Optimal Short-Circuit Resilient Formulas.
    Computational Complexity Conference(CCC 2019)
    [Abstract] [Paper: PDF]

  8. Klim Efremenko and Aryeh Kontorovich and Moshe Noivirt:
    Fast and Bayes-consistent nearest neighbors.

    [Abstract] [Paper: PDF]

  9. Klim Efremenko and Garg, Ankit and Oliveira, Rafael and Wigderson, Avi
    Barriers for rank methods in arithmetic complexity
    Innovations in Theoretical Computer Science Conference (ITCS 2018)
    [Abstract] [Paper: PDF]

  10. Klim Efremenko and Elad Haramaty and Yael Kalai
    Interactive Coding with Nearly Optimal Round and Communication Blowup
    Innovations in Theoretical Computer Science Conference (ITCS 2020)
    [Abstract] [Paper: PDF]

  11. Ankit Singh Rawat and Itzhak Tamo and Venkatesan Guruswam and Klim Efremenko
    MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth
    IEEE Transactions on Information Theory 2018

  12. Mark Braverman Klim Efremenko and Ran Gelles and Bernhard Haeupler
    Constant-rate coding for multiparty interactive communication is impossible.
    Journal of the ACM 2017, Symposium on Theory of Computing (STOC) 2016,
    [Abstract] [Paper: PDF]

  13. Noga Alon Mark Braverman Klim Efremenko and Ran Gelles and Bernhard Haeupler
    Reliable Communication over Highly Connected Noisy Networks
    invited to Distributed Computing (DIST) special issue of Principles of Distributed Computing (PODC) 2016
    [Abstract] [Paper: PDF]

  14. Noga Alon Klim Efremenko and Benny Sudakov
    Testing Equality in Communication Graphs.
    IEEE Information Theory 2017
    [Abstract] [Paper: PDF]

  15. Klim Efremekno, Joseph Landsberg, Hal Schenck and Jerzy Weyman
    The method of shifted partial derivatives cannot separate the permanent from the determinant
    Mathematics of Computation 2018
    [Abstract] [Paper: PDF]

  16. Klim Efremekno, Joseph Landsberg, Hal Schenck and Jerzy Weyman
    On minimal free resolutions and the method of shifted partial derivatives in complexity theory.
    Journal of Algebra 2018
    [Abstract] [Paper: PDF]

  17. Mark Braverman and Klim Efremenko
    List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
    Special issue of the SIAM Journal of Computing for FOCS 2014.
    [Abstract] [Paper: PDF]

  18. Klim Efremenko and Ran Gelles and Bernhard Haeupler
    Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
    IEEE Transactions on Information Theory 2016, (appeared in ITCS 2015)
    [Abstract] [Paper: PDF]

  19. Klim Efremenko
    From Irreducible Representations to Locally Decodable Codes.
    The 44st ACM Symposium on Theory of Computing, STOC 2012
    [Abstract] [BiBTeX] [Paper: PDF]

  20. Avraham Ben-Aroya, Klim Efremenko and Amnon Ta-Shma
    Local List Decoding with a Constant Number of Queries.
    51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010
    [Abstract] [BiBTeX] [Paper: PDF]

  21. Avraham Ben-Aroya, Klim Efremenko and Amnon Ta-Shma
    A Note on Amplifying the Error-Tolerance of Locally Decodable Codes.
    Electronic Colloquium on Computational Complexity (ECCC) 17: 134 (2010)
    [Abstract] [BiBTeX] [Paper: PDF]

  22. Klim Efremenko
    3-Query Locally Decodable Codes of Subexponential Length
    STOC 2009 Special Issue SIAM Journal on Computing
    [Abstract] [BiBTeX] [Paper: PDF]

  23. Klim Efremenko and Omer Reingold
    How Well Do Random Walks Parallelize?
    APPROX-RANDOM, 2009
    [Abstract] [BiBTeX] [Paper: PDF]

  24. Raffaell Clifford , Klim Efremenko, Ely Porat and Amir Rothschild
    From Coding Theory to Efficient Pattern Matching
    20 nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
    [Abstract] [BiBTeX] [Paper: PDF]

  25. Klim Efremenko and Ely Porat
    Approximating General Metric Distances Between a Pattern and a Text
    19nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),2008
    [Abstract] [BiBTeX] [Paper: PDF]

  26. Raffaell Clifford , Klim Efremenko, Ely Porat and Amir Rothschild
    Pattern Matching with Don't Cares and Few Errors
    Journal of Computer and System Sciences (JCSS), 2010
    [Abstract] [BiBTeX] [Paper: PDF]

  27. Raffaell Clifford , Klim Efremenko, Benny Porat and Ely Porat
    A Black Box for Online Approximate Pattern Matching
    Information and Computation, 2011
    [Abstract] [BiBTeX] [Paper: PDF]

  28. Raffaell Clifford , Klim Efremenko, Benny Porat, Ely Porat and Amir Rothschild
    Mismatch sampling
    Information and Computation, 2012
    [Abstract] [BiBTeX] [Paper: PDF]