Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDKlim 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
Books and Theses
- 2013
[b1]Klim Efremenko:
A theory of locally decodable codes. Tel Aviv University, Israel, 2013
Journal Articles
- 2022
- [j12]Mark Braverman
, Klim Efremenko, Ran Gelles, Michael A. Yitayew:
Optimal Short-Circuit Resilient Formulas. J. ACM 69(4): 26:1-26:37 (2022) - 2019
- [j11]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable communication over highly connected noisy networks. Distributed Comput. 32(6): 505-515 (2019) - 2018
- [j10]Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM 65(1): 4:1-4:41 (2018) - [j9]Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman:
The method of shifted partial derivatives cannot separate the permanent from the determinant. Math. Comput. 87(312): 2037-2045 (2018) - [j8]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. IEEE Trans. Inf. Theory 64(10): 6506-6525 (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, Benny Sudakov:
Testing Equality in Communication Graphs. IEEE Trans. Inf. Theory 63(11): 7569-7574 (2017) - 2016
- [j5]Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Inf. Theory 62(8): 4575-4588 (2016) - 2012
- [j4]Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild:
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) - 2011
- [j2]Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat:
A black box for online approximate pattern matching. Inf. Comput. 209(4): 731-736 (2011) - 2010
- [j1]Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
Pattern matching with don't cares and few errors. J. Comput. Syst. Sci. 76(2): 115-124 (2010)
Conference and Workshop Papers
- 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 - 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, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena:
Circuits resilient to short-circuit errors. STOC 2022: 582-594 - 2021
- [c27]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS 2021: 634-645 - [c26]Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran:
Statistically Near-Optimal Hypothesis Selection. FOCS 2021: 909-919 - [c25]Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Computation over the Noisy Broadcast Channel with Malicious Parties. ITCS 2021: 82:1-82:19 - [c24]Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena:
Optimal error resilience of adaptive message exchange. STOC 2021: 1235-1247 - 2020
- [c23]Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt:
Fast and Bayes-consistent nearest neighbors. AISTATS 2020: 1276-1286 - [c22]Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena:
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. FOCS 2020: 470-481 - [c21]Klim Efremenko, Elad Haramaty, Yael Tauman Kalai:
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, Gillat Kol, Raghuvansh R. Saxena:
Interactive error resilience beyond 2/7. STOC 2020: 565-578 - 2019
- [c18]Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew:
Optimal Short-Circuit Resilient Formulas. CCC 2019: 10:1-10:22 - [c17]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Radio Network Coding Requires Logarithmic Overhead. FOCS 2019: 348-369 - 2018
- [c16]Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson:
Barriers for Rank Methods in Arithmetic Complexity. ITCS 2018: 1:1-1:19 - [c15]Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive coding over the noisy broadcast channel. STOC 2018: 507-520 - 2017
- [c14]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
∊-MSR codes with small sub-packetization. ISIT 2017: 2043-2047 - 2016
- [c13]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable Communication over Highly Connected Noisy Networks. PODC 2016: 165-173 - [c12]Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Constant-rate coding for multiparty interactive communication is impossible. STOC 2016: 999-1010 - 2015
- [c11]Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. ITCS 2015: 11-20 - 2014
- [c10]Mark Braverman, Klim Efremenko:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. FOCS 2014: 236-245 - 2012
- [c9]Klim Efremenko:
From irreducible representations to locally decodable codes. STOC 2012: 327-338 - 2010
- [c8]Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
Local List Decoding with a Constant Number of Queries. FOCS 2010: 715-722 - 2009
- [c7]Klim Efremenko, Omer Reingold:
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 - 2008
- [c4]Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat:
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, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild:
Mismatch Sampling. SPIRE 2008: 99-108 - 2007
- [c1]Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
k -Mismatch with Don't Cares. ESA 2007: 151-162
Informal and Other Publications
- 2023
- [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
- [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
- [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
- [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) - 2019
- [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
- [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
- [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
- [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
- [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
- [i8]Mark Braverman, Klim Efremenko:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. TR14 (2014) - 2011
- [i7]Klim Efremenko:
From Irreducible Representations to Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [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) - 2009
- [i4]Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
Pattern matching with don't cares and few errors. Search Methodologies 2009 - 2008
- [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)
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-05-02 23:57 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:
