k -Mismatch with Don't Cares. - Raphaël Clifford; Klim Efremenko; Ely Porat; Amir Rothschild (ESA, 2007)

Approximating general metric distances between a pattern and a text. - Ely Porat; Klim Efremenko (SODA, 2008)

Improved Deterministic Length Reduction - Amihood Amir; Klim Efremenko; Oren Kapah; Ely Porat; Amir Rothschild (CoRR, 2008)

How Well Do Random Walks Parallelize?. - Klim Efremenko; Omer Reingold (APPROX-RANDOM, 2009)

From coding theory to efficient pattern matching. - Raphaël Clifford; Klim Efremenko; Ely Porat; Amir Rothschild (SODA, 2009)

Local list decoding with a constant number of queries. - Avraham Ben-Aroya; Klim Efremenko; Amnon Ta-Shma (Electron. Colloquium Comput. Complex., 2010)

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. - Avraham Ben-Aroya; Klim Efremenko; Amnon Ta-Shma (Electron. Colloquium Comput. Complex., 2010)

Pattern matching with don't cares and few errors. - Raphaël Clifford; Klim Efremenko; Ely Porat; Amir Rothschild (J. Comput. Syst. Sci., 2010)

From Irreducible Representations to Locally Decodable Codes. - Klim Efremenko (Electron. Colloquium Comput. Complex., 2011)

A black box for online approximate pattern matching. - Raphaël Clifford; Klim Efremenko; Benny Porat; Ely Porat (Inf. Comput., 2011)

Mismatch sampling. - Raphaël Clifford; Klim Efremenko; Benny Porat; Ely Porat; Amir Rothschild (Inf. Comput., 2012)

3-Query Locally Decodable Codes of Subexponential Length. - Klim Efremenko (SIAM J. Comput., 2012)

A theory of locally decodable codes - Klim Efremenko (2013)

On minimal free resolutions and the method of shifted partial derivatives in complexity theory. - Klim Efremenko; J. M. Landsberg; Hal Schenck; Jerzy Weyman (CoRR, 2015)

Constant-rate coding for multiparty interactive communication is impossible. - Mark Braverman; Klim Efremenko; Ran Gelles; Bernhard Haeupler (Electron. Colloquium Comput. Complex., 2015)

Testing Equality in Communication Graphs. - Noga Alon; Klim Efremenko; Benny Sudakov (Electron. Colloquium Comput. Complex., 2016)

Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. - Klim Efremenko; Ran Gelles; Bernhard Haeupler (IEEE Trans. Inf. Theory, 2016)

∊-MSR codes with small sub-packetization. - Ankit Singh Rawat; Itzhak Tamo; Venkatesan Guruswami; Klim Efremenko (ISIT, 2017)

Barriers for Rank Methods in Arithmetic Complexity. - Klim Efremenko; Ankit Garg; Rafael Mendes de Oliveira; Avi Wigderson (Electron. Colloquium Comput. Complex., 2017)

Interactive Coding Over the Noisy Broadcast Channel. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2017)

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. - Mark Braverman; Klim Efremenko (SIAM J. Comput., 2017)

Interactive Coding with Constant Round and Communication Blowup. - Klim Efremenko; Elad Haramaty; Yael Kalai (Electron. Colloquium Comput. Complex., 2018)

The method of shifted partial derivatives cannot separate the permanent from the determinant. - Klim Efremenko; J. M. Landsberg; Hal Schenck; Jerzy Weyman (Math. Comput., 2018)

MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. - Ankit Singh Rawat; Itzhak Tamo; Venkatesan Guruswami; Klim Efremenko (IEEE Trans. Inf. Theory, 2018)

Reliable communication over highly connected noisy networks. - Noga Alon; Mark Braverman; Klim Efremenko; Ran Gelles; Bernhard Haeupler (Distributed Comput., 2019)

Noisy Beeps. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2019)

Radio Network Coding Requires Logarithmic Overhead. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2019)

Fast and Bayes-consistent nearest neighbors. - Klim Efremenko; Aryeh Kontorovich; Moshe Noivirt (AISTATS, 2020)

Non-parametric Binary regression in metric spaces with KL loss. - Ariel Avital; Klim Efremenko; Aryeh Kontorovich; David Toplin; Bo Waggoner (CoRR, 2020)

Interactive Error Resilience Beyond 2/7. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2020)

Statistically Near-Optimal Hypothesis Selection. - Olivier Bousquet; Mark Braverman; Gillat Kol; Klim Efremenko; Shay Moran (FOCS, 2021)

Computation Over the Noisy Broadcast Channel with Malicious Parties. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2021)

Tight Bounds for General Computation in Noisy Broadcast Networks. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2021)

Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$). - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2021)

Optimal Error Resilience of Adaptive Message Exchange. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2021)

Round-vs-Resilience Tradeoffs for Binary Feedback Channels. - Mark Braverman; Klim Efremenko; Gillat Kol; Raghuvansh Saxena; Zhijun Zhang 007 (Electron. Colloquium Comput. Complex., 2022)

Circuits Resilient to Short-Circuit Errors. - Klim Efremenko; Bernhard Haeupler; Yael Kalai; Pritish Kamath; Gillat Kol; Nicolas Resch; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2022)

Interactive Coding with Small Memory. - Klim Efremenko; Bernhard Haeupler; Gillat Kol; Nicolas Resch; Raghuvansh Saxena; Yael Tauman Kalai (Electron. Colloquium Comput. Complex., 2022)

Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2022)

Binary Codes with Resilience Beyond 1/4 via Interaction. - Klim Efremenko; Gillat Kol; Raghuvansh Saxena; Zhijun Zhang 007 (Electron. Colloquium Comput. Complex., 2022)

Optimal Short-Circuit Resilient Formulas. - Mark Braverman; Klim Efremenko; Ran Gelles; Michael A. Yitayew (J. ACM, 2022)

Lower bounds for regular resolution over parities. - Klim Efremenko; Michal Garlík; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2023)

Protecting Single-Hop Radio Networks from Message Drops. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2023)

Unbounded Error Correcting Codes. - Klim Efremenko; Or Zamir (CoRR, 2024)

The Rate of Interactive Codes is Bounded Away from 1. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2024)

Tournament Robustness via Redundancy. - Klim Efremenko; Hendrik Molter; Meirav Zehavi (EC, 2025)

Amortized Closure and Its Applications in Lifting for Resolution over Parities. - Klim Efremenko; Dmitry Itsykson (Electron. Colloquium Comput. Complex., 2025)

Information Dissemination via Broadcasts in the Presence of Adversarial Noise. - Klim Efremenko; Gillat Kol; Dmitry Paramonov; Ran Raz; Raghuvansh Saxena (Electron. Colloquium Comput. Complex., 2025)