Klim Efremenko

99 papers A* 25A 11B 2C 1Journal 57Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Unbounded Error Correcting Codes. SODA Klim Efremenko, Or Zamir
2026	A	`conf`	Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. ITCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2025	A	`conf`	Amortized Closure and Its Applications in Lifting for Resolution over Parities. CCC Klim Efremenko, Dmitry Itsykson
2025	J	`jnl`	Amortized Closure and Its Applications in Lifting for Resolution over Parities. Electron. Colloquium Comput. Complex. Klim Efremenko, Dmitry Itsykson
2025	A*	`conf`	Constant Rate Codes for Adaptive Broadcasts Do Not Exist. FOCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2025	J	`jnl`	Constant Rate Codes for Adaptive Broadcasts Do Not Exist. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2025	J	`jnl`	Information Dissemination via Broadcasts in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena
2025	J	`jnl`	Lower Bounds for Regular Resolution over Parities. SIAM J. Comput. Klim Efremenko, Michal Garlík, Dmitry Itsykson
2025	A	`conf`	Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. ITCS Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2025	J	`jnl`	Strong ETH Holds for Bounded-Depth Resolution over Parities. Electron. Colloquium Comput. Complex. Klim Efremenko, Dmitry Itsykson
2025	A*	`conf`	Tournament Robustness via Redundancy. EC Klim Efremenko, Hendrik Molter, Meirav Zehavi
2025	J	`jnl`	Tournament Robustness via Redundancy. CoRR Klim Efremenko, Hendrik Molter, Meirav Zehavi
2025	J	`jnl`	Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2024	A	`conf`	Information Dissemination via Broadcasts in the Presence of Adversarial Noise. CCC Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena
2024	A*	`conf`	Lower Bounds for Regular Resolution over Parities. STOC Klim Efremenko, Michal Garlík, Dmitry Itsykson
2024	J	`jnl`	The Rate of Interactive Codes is Bounded Away from 1. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2024	J	`jnl`	Unbounded Error Correcting Codes. CoRR Klim Efremenko, Or Zamir
2023	A*	`conf`	Interactive Coding with Small Memory. SODA Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2023	J	`jnl`	Lower bounds for regular resolution over parities. Electron. Colloquium Comput. Complex. Klim Efremenko, Michal Garlík, Dmitry Itsykson
2023	A	`conf`	Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. ITCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2023	A*	`conf`	Protecting Single-Hop Radio Networks from Message Drops. ICALP Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2023	J	`jnl`	Protecting Single-Hop Radio Networks from Message Drops. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2023	A*	`conf`	The Rate of Interactive Codes Is Bounded Away from 1. STOC Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2022	A*	`conf`	Binary Codes with Resilience Beyond 1/4 via Interaction. FOCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2022	J	`jnl`	Binary Codes with Resilience Beyond 1/4 via Interaction. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2022	J	`jnl`	Circuits Resilient to Short-Circuit Errors. Electron. Colloquium Comput. Complex. Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
2022	A*	`conf`	Circuits resilient to short-circuit errors. STOC Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2022	J	`jnl`	Interactive Coding with Small Memory. Electron. Colloquium Comput. Complex. Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai
2022	J	`jnl`	Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2022	J	`jnl`	Optimal Short-Circuit Resilient Formulas. J. ACM Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2022	J	`jnl`	Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2021	J	`jnl`	Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$). Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2021	J	`jnl`	Computation Over the Noisy Broadcast Channel with Malicious Parties. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2021	A	`conf`	Computation over the Noisy Broadcast Channel with Malicious Parties. ITCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2021	J	`jnl`	Optimal Error Resilience of Adaptive Message Exchange. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2021	A*	`conf`	Optimal error resilience of adaptive message exchange. STOC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2021	A*	`conf`	Statistically Near-Optimal Hypothesis Selection. FOCS Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
2021	J	`jnl`	Statistically Near-Optimal Hypothesis Selection. CoRR Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran
2021	A*	`conf`	Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2021	J	`jnl`	Tight Bounds for General Computation in Noisy Broadcast Networks. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2020	A*	`conf`	Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. FOCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	A	`conf`	Fast and Bayes-consistent nearest neighbors. AISTATS Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt
2020	A	`conf`	Interactive Coding with Constant Round and Communication Blowup. ITCS Klim Efremenko, Elad Haramaty, Yael Tauman Kalai
2020	J	`jnl`	Interactive Error Resilience Beyond 2/7. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2020	A*	`conf`	Interactive error resilience beyond 2/7. STOC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	A*	`conf`	Noisy Beeps. PODC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	J	`jnl`	Non-parametric Binary regression in metric spaces with KL loss. CoRR Ariel Avital, Klim Efremenko, Aryeh Kontorovich, David Toplin, Bo Waggoner
2019	J	`jnl`	Fast and Bayes-consistent nearest neighbors. CoRR Klim Efremenko, Aryeh Kontorovich, Moshe Noivirt
2019	J	`jnl`	Noisy Beeps. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2019	A	`conf`	Optimal Short-Circuit Resilient Formulas. CCC Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2019	A*	`conf`	Radio Network Coding Requires Logarithmic Overhead. FOCS Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2019	J	`jnl`	Radio Network Coding Requires Logarithmic Overhead. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2019	J	`jnl`	Reliable communication over highly connected noisy networks. Distributed Comput. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2018	A	`conf`	Barriers for Rank Methods in Arithmetic Complexity. ITCS Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2018	J	`jnl`	Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2018	J	`jnl`	Interactive Coding with Constant Round and Communication Blowup. Electron. Colloquium Comput. Complex. Klim Efremenko, Elad Haramaty, Yael Kalai
2018	A*	`conf`	Interactive coding over the noisy broadcast channel. STOC Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2018	J	`jnl`	MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. IEEE Trans. Inf. Theory Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2018	J	`jnl`	Optimal Short-Circuit Resilient Formulas. CoRR Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2018	J	`jnl`	The method of shifted partial derivatives cannot separate the permanent from the determinant. Math. Comput. Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman
2017	J	`jnl`	Barriers for Rank Methods in Arithmetic Complexity. CoRR Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Barriers for Rank Methods in Arithmetic Complexity. Electron. Colloquium Comput. Complex. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson
2017	J	`jnl`	Interactive Coding Over the Noisy Broadcast Channel. Electron. Colloquium Comput. Complex. Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2017	J	`jnl`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM J. Comput. Mark Braverman, Klim Efremenko
2017	J	`jnl`	MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. CoRR Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2017	J	`jnl`	Testing Equality in Communication Graphs. IEEE Trans. Inf. Theory Noga Alon, Klim Efremenko, Benny Sudakov
2017	B	`conf`	∊-MSR codes with small sub-packetization. ISIT Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2016	A*	`conf`	Constant-rate coding for multiparty interactive communication is impossible. STOC Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Inf. Theory Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	A*	`conf`	Reliable Communication over Highly Connected Noisy Networks. PODC Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	Testing Equality in Communication Graphs. Electron. Colloquium Comput. Complex. Noga Alon, Klim Efremenko, Benny Sudakov
2016	J	`jnl`	The method of shifted partial derivatives cannot separate the permanent from the determinant. CoRR Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman
2015	J	`jnl`	Constant-rate coding for multiparty interactive communication is impossible. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	A	`conf`	Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. ITCS Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. CoRR Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	On minimal free resolutions and the method of shifted partial derivatives in complexity theory. CoRR Klim Efremenko, J. M. Landsberg, Hal Schenck, Jerzy Weyman
2015	J	`jnl`	Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2014	A*	`conf`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. FOCS Mark Braverman, Klim Efremenko
2014	J	`jnl`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko
2013	—	`—`	A theory of locally decodable codes Klim Efremenko
2012	J	`jnl`	3-Query Locally Decodable Codes of Subexponential Length. SIAM J. Comput. Klim Efremenko
2012	A*	`conf`	From irreducible representations to locally decodable codes. STOC Klim Efremenko
2012	J	`jnl`	Mismatch sampling. Inf. Comput. Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild
2011	J	`jnl`	A black box for online approximate pattern matching. Inf. Comput. Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat
2011	J	`jnl`	From Irreducible Representations to Locally Decodable Codes. Electron. Colloquium Comput. Complex. Klim Efremenko
2010	J	`jnl`	A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. Electron. Colloquium Comput. Complex. Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010	A*	`conf`	Local List Decoding with a Constant Number of Queries. FOCS Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010	J	`jnl`	Local list decoding with a constant number of queries. Electron. Colloquium Comput. Complex. Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010	J	`jnl`	Pattern matching with don't cares and few errors. J. Comput. Syst. Sci. Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild
2009	A*	`conf`	3-query locally decodable codes of subexponential length. STOC Klim Efremenko
2009	A*	`conf`	From coding theory to efficient pattern matching. SODA Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild
2009	—	`conf`	How Well Do Random Walks Parallelize?. APPROX-RANDOM Klim Efremenko, Omer Reingold
2009	—	`conf`	Pattern matching with don't cares and few errors. Search Methodologies Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild
2008	J	`jnl`	3-Query Locally Decodable Codes of Subexponential Length. Electron. Colloquium Comput. Complex. Klim Efremenko
2008	B	`conf`	A Black Box for Online Approximate Pattern Matching. CPM Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat
2008	J	`jnl`	Approximating General Metric Distances Between a Pattern and a Text CoRR Klim Efremenko, Ely Porat
2008	A*	`conf`	Approximating general metric distances between a pattern and a text. SODA Ely Porat, Klim Efremenko
2008	J	`jnl`	Improved Deterministic Length Reduction CoRR Amihood Amir, Klim Efremenko, Oren Kapah, Ely Porat, Amir Rothschild
2008	C	`conf`	Mismatch Sampling. SPIRE Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild