Klim Efremenko

According to our database, Klim Efremenko authored at least 44 papers between 2007 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Protecting Single-Hop Radio Networks from Message Drops.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2023

Lower bounds for regular resolution over parities.

Klim Efremenko, Michal Garlík, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2023

The Rate of Interactive Codes Is Bounded Away from 1.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Optimal Short-Circuit Resilient Formulas.

Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew

J. ACM, 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

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

Interactive Coding with Small Memory.

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

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

Round-vs-Resilience Tradeoffs for Binary Feedback Channels.

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

2021

Optimal Error Resilience of Adaptive Message Exchange.

Klim Efremenko, Gillat Kol, 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

Tight Bounds for General Computation in Noisy Broadcast Networks.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Computation Over the Noisy Broadcast Channel with Malicious Parties.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Statistically Near-Optimal Hypothesis Selection.

Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Interactive Error Resilience Beyond 2/7.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2020

Non-parametric Binary regression in metric spaces with KL loss.

Ariel Avital, Klim Efremenko, Aryeh Kontorovich, David Toplin, Bo Waggoner

CoRR, 2020

Fast and Bayes-consistent nearest neighbors.

Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Radio Network Coding Requires Logarithmic Overhead.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2019

Noisy Beeps.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2019

Reliable communication over highly connected noisy networks.

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Distributed Comput., 2019

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

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

Constant-Rate Coding for Multiparty Interactive Communication Is Impossible.

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

J. ACM, 2018

Interactive Coding with Constant Round and Communication Blowup.

Klim Efremenko, Elad Haramaty, Yael Kalai

Electron. Colloquium Comput. Complex., 2018

2017

Interactive Coding Over the Noisy Broadcast Channel.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2017

Barriers for Rank Methods in Arithmetic Complexity.

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Electron. Colloquium Comput. Complex., 2017

∊-MSR codes with small sub-packetization.

Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

2016

Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback.

Klim Efremenko, Ran Gelles, Bernhard Haeupler

IEEE Trans. Inf. Theory, 2016

Testing Equality in Communication Graphs.

Noga Alon, Klim Efremenko, Benny Sudakov

Electron. Colloquium Comput. Complex., 2016

2015

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

2014

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise.

Mark Braverman, Klim Efremenko

Electron. Colloquium Comput. Complex., 2014

2013

A theory of locally decodable codes

Klim Efremenko

PhD thesis, 2013

2012

Mismatch sampling.

Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild

Inf. Comput., 2012

2011

A black box for online approximate pattern matching.

Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat

Inf. Comput., 2011

From Irreducible Representations to Locally Decodable Codes.

Klim Efremenko

Electron. Colloquium Comput. Complex., 2011

2010

Pattern matching with don't cares and few errors.

Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild

J. Comput. Syst. Sci., 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

Local list decoding with a constant number of queries.

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2010

2009

From coding theory to efficient pattern matching.

Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

How Well Do Random Walks Parallelize?.

Klim Efremenko, Omer Reingold

Proceedings of the Approximation, 2009

2008

3-Query Locally Decodable Codes of Subexponential Length.

Klim Efremenko

Electron. Colloquium Comput. Complex., 2008

Improved Deterministic Length Reduction

Amihood Amir, Klim Efremenko, Oren Kapah, Ely Porat, Amir Rothschild

CoRR, 2008

Approximating general metric distances between a pattern and a text.

Ely Porat, Klim Efremenko

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

<i>k</i> -Mismatch with Don't Cares.

Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild

Proceedings of the Algorithms, 2007