Klim Efremenko

Klim Efremenko


I am on job market hire me


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 am a fellow at Simons Institute at Berekeley
Before that I was a Simons Fellow at University of Chicago
And a member at Institute for Advanced Study

Publications

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

  2. Klim Efremenko and Ran Gelles and Bernhard Haeupler
    Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
    Submitted
    [Abstract] [Paper: PDF]

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

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

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

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

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

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

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

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

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

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