Klim Efremenko

Klim Efremenko


Phone: +1-617-775-9306
Email: klimefrem at gmail.com
Here is my CV
Here is my Research Proposal

Research Interests

My main focus of research is in Error Correcting Codes and I have a broad interest in theoretical computer science. Specially I am interested in Error Correction for Interactive Communication and Locally Decodable Codes.

Brief Background

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.
Today I a ma 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

Publications

  1. Klim Efremenko and Elad Haramaty and Yael Kalai
    Interactive Coding with Nearly Optimal Round and Communication Blowup

    [Abstract] [Paper: PDF]

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

  3. 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]

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

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

  6. Klim Efremekno, Joseph Landsberg, Hal Schenck and Jerzy Weyman
    On minimal free resolutions and the method of shifted partial derivatives in complexity theory.

    [Abstract] [Paper: PDF]

  7. 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]

  8. 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]

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

  10. 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]

  11. 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]

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

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

  14. 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]

  15. 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]

  16. 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]

  17. 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]

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