default search action
Klim Efremenko
Person information
- affiliation: Ben-Gurion University, Beer Sheva, Israel
- affiliation (former): University of California, Simons Institute for the Theory of Computing, Berkeley, CA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c35]Klim Efremenko
, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena:
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. CCC 2024: 19:1-19:33 - [c34]Klim Efremenko
Lower Bounds for Regular Resolution over Parities. STOC 2024: 640-651 - [i38]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
The Rate of Interactive Codes is Bounded Away from 1. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c33]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Protecting Single-Hop Radio Networks from Message Drops. ICALP 2023: 53:1-53:20 - [c32]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. ITCS 2023: 46:1-46:20 - [c31]Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena:
Interactive Coding with Small Memory. SODA 2023: 3587-3613 - [c30]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
The Rate of Interactive Codes Is Bounded Away from 1. STOC 2023: 1424-1437 - [i37]Klim Efremenko, Michal Garlík, Dmitry Itsykson:
Lower bounds for regular resolution over parities. Electron. Colloquium Comput. Complex. TR23 (2023) - [i36]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Protecting Single-Hop Radio Networks from Message Drops. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j12]Mark Braverman
Optimal Short-Circuit Resilient Formulas. J. ACM 69(4): 26:1-26:37 (2022) - [c29]Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
Binary Codes with Resilience Beyond 1/4 via Interaction. FOCS 2022: 1-12 - [c28]Klim Efremenko
Circuits resilient to short-circuit errors. STOC 2022: 582-594 - [i35]Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. TR22 (2022) - [i34]Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena:
Circuits Resilient to Short-Circuit Errors. Electron. Colloquium Comput. Complex. TR22 (2022) - [i33]Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai:
Interactive Coding with Small Memory. Electron. Colloquium Comput. Complex. TR22 (2022) - [i32]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds. Electron. Colloquium Comput. Complex. TR22 (2022) - [i31]Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Binary Codes with Resilience Beyond 1/4 via Interaction. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c27]Klim Efremenko
Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS 2021: 634-645 - [c26]Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko
Statistically Near-Optimal Hypothesis Selection. FOCS 2021: 909-919 - [c25]Klim Efremenko
Computation over the Noisy Broadcast Channel with Malicious Parties. ITCS 2021: 82:1-82:19 - [c24]Klim Efremenko
Optimal error resilience of adaptive message exchange. STOC 2021: 1235-1247 - [i30]Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran:
Statistically Near-Optimal Hypothesis Selection. CoRR abs/2108.07880 (2021) - [i29]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Computation Over the Noisy Broadcast Channel with Malicious Parties. Electron. Colloquium Comput. Complex. TR21 (2021) - [i28]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Tight Bounds for General Computation in Noisy Broadcast Networks. Electron. Colloquium Comput. Complex. TR21 (2021) - [i27]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$). Electron. Colloquium Comput. Complex. TR21 (2021) - [i26]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Optimal Error Resilience of Adaptive Message Exchange. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c23]Klim Efremenko
Fast and Bayes-consistent nearest neighbors. AISTATS 2020: 1276-1286 - [c22]Klim Efremenko
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. FOCS 2020: 470-481 - [c21]Klim Efremenko
Interactive Coding with Constant Round and Communication Blowup. ITCS 2020: 7:1-7:34 - [c20]Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena:
Noisy Beeps. PODC 2020: 418-427 - [c19]Klim Efremenko
Interactive error resilience beyond 2/7. STOC 2020: 565-578 - [i25]Ariel Avital, Klim Efremenko, Aryeh Kontorovich, David Toplin, Bo Waggoner:
Non-parametric Binary regression in metric spaces with KL loss. CoRR abs/2010.09886 (2020) - [i24]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Error Resilience Beyond 2/7. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j11]Noga Alon, Mark Braverman, Klim Efremenko
Reliable communication over highly connected noisy networks. Distributed Comput. 32(6): 505-515 (2019) - [c18]Mark Braverman, Klim Efremenko
Optimal Short-Circuit Resilient Formulas. CCC 2019: 10:1-10:22 - [c17]Klim Efremenko
Radio Network Coding Requires Logarithmic Overhead. FOCS 2019: 348-369 - [i23]Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt:
Fast and Bayes-consistent nearest neighbors. CoRR abs/1910.05270 (2019) - [i22]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Noisy Beeps. Electron. Colloquium Comput. Complex. TR19 (2019) - [i21]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Radio Network Coding Requires Logarithmic Overhead. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j10]Mark Braverman, Klim Efremenko
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM 65(1): 4:1-4:41 (2018) - [j9]Klim Efremenko
The method of shifted partial derivatives cannot separate the permanent from the determinant. Math. Comput. 87(312): 2037-2045 (2018) - [j8]Ankit Singh Rawat
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. IEEE Trans. Inf. Theory 64(10): 6506-6525 (2018) - [c16]Klim Efremenko
Barriers for Rank Methods in Arithmetic Complexity. ITCS 2018: 1:1-1:19 - [c15]Klim Efremenko
Interactive coding over the noisy broadcast channel. STOC 2018: 507-520 - [i20]Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew:
Optimal Short-Circuit Resilient Formulas. CoRR abs/1807.05014 (2018) - [i19]Klim Efremenko, Elad Haramaty, Yael Kalai:
Interactive Coding with Constant Round and Communication Blowup. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j7]Mark Braverman, Klim Efremenko
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM J. Comput. 46(1): 388-428 (2017) - [j6]Noga Alon, Klim Efremenko
Testing Equality in Communication Graphs. IEEE Trans. Inf. Theory 63(11): 7569-7574 (2017) - [c14]Ankit Singh Rawat
∊-MSR codes with small sub-packetization. ISIT 2017: 2043-2047 - [i18]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. CoRR abs/1709.08216 (2017) - [i17]Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson:
Barriers for Rank Methods in Arithmetic Complexity. CoRR abs/1710.09502 (2017) - [i16]Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson:
Barriers for Rank Methods in Arithmetic Complexity. Electron. Colloquium Comput. Complex. TR17 (2017) - [i15]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Coding Over the Noisy Broadcast Channel. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j5]Klim Efremenko
Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Inf. Theory 62(8): 4575-4588 (2016) - [c13]Noga Alon, Mark Braverman, Klim Efremenko
Reliable Communication over Highly Connected Noisy Networks. PODC 2016: 165-173 - [c12]Mark Braverman, Klim Efremenko
Constant-rate coding for multiparty interactive communication is impossible. STOC 2016: 999-1010 - [i14]Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman:
The method of shifted partial derivatives cannot separate the permanent from the determinant. CoRR abs/1609.02103 (2016) - [i13]Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c11]Klim Efremenko
Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. ITCS 2015: 11-20 - [i12]Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. CoRR abs/1501.00624 (2015) - [i11]Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman:
On minimal free resolutions and the method of shifted partial derivatives in complexity theory. CoRR abs/1504.05171 (2015) - [i10]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. TR15 (2015) - [i9]Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Constant-rate coding for multiparty interactive communication is impossible. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c10]Mark Braverman, Klim Efremenko
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. FOCS 2014: 236-245 - [i8]Mark Braverman, Klim Efremenko:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [b1]Klim Efremenko:
A theory of locally decodable codes. Tel Aviv University, Israel, 2013 - 2012
- [j4]Raphaël Clifford
Mismatch sampling. Inf. Comput. 214: 112-118 (2012) - [j3]Klim Efremenko
3-Query Locally Decodable Codes of Subexponential Length. SIAM J. Comput. 41(6): 1694-1703 (2012) - [c9]Klim Efremenko
From irreducible representations to locally decodable codes. STOC 2012: 327-338 - 2011
- [j2]Raphaël Clifford
A black box for online approximate pattern matching. Inf. Comput. 209(4): 731-736 (2011) - [i7]Klim Efremenko:
From Irreducible Representations to Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j1]Raphaël Clifford
Pattern matching with don't cares and few errors. J. Comput. Syst. Sci. 76(2): 115-124 (2010) - [c8]Avraham Ben-Aroya, Klim Efremenko
Local List Decoding with a Constant Number of Queries. FOCS 2010: 715-722 - [i6]Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
Local list decoding with a constant number of queries. Electron. Colloquium Comput. Complex. TR10 (2010) - [i5]Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c7]Klim Efremenko
How Well Do Random Walks Parallelize?. APPROX-RANDOM 2009: 476-489 - [c6]Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
From coding theory to efficient pattern matching. SODA 2009: 778-784 - [c5]Klim Efremenko
3-query locally decodable codes of subexponential length. STOC 2009: 39-44 - [i4]Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
Pattern matching with don't cares and few errors. Search Methodologies 2009 - 2008
- [c4]Raphaël Clifford
A Black Box for Online Approximate Pattern Matching. CPM 2008: 143-151 - [c3]Ely Porat, Klim Efremenko:
Approximating general metric distances between a pattern and a text. SODA 2008: 419-427 - [c2]Raphaël Clifford
Mismatch Sampling. SPIRE 2008: 99-108 - [i3]Amihood Amir, Klim Efremenko, Oren Kapah, Ely Porat, Amir Rothschild:
Improved Deterministic Length Reduction. CoRR abs/0802.0017 (2008) - [i2]Klim Efremenko, Ely Porat:
Approximating General Metric Distances Between a Pattern and a Text. CoRR abs/0802.1427 (2008) - [i1]Klim Efremenko:
3-Query Locally Decodable Codes of Subexponential Length. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c1]Raphaël Clifford
k -Mismatch with Don't Cares. ESA 2007: 151-162
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 00:32 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: