Klim Efremenko

Hendrik Molter

Meirav Zehavi

Proceedings of the 26th ACM Conference on Economics and Computation, 2025

Round-Vs-Resilience Tradeoffs for Binary Feedback Channels.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Amortized Closure and Its Applications in Lifting for Resolution over Parities.

[BibT_eX]

[DOI]

Dmitry Itsykson

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Unbounded Error Correcting Codes.

[BibT_eX]

[DOI]

Or Zamir

CoRR, 2024

Lower Bounds for Regular Resolution over Parities.

[BibT_eX]

[DOI]

Michal Garlík

Dmitry Itsykson

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

The Rate of Interactive Codes Is Bounded Away from 1.

[BibT_eX]

[DOI]

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

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Protecting Single-Hop Radio Networks from Message Drops.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Circuits resilient to short-circuit errors.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Optimal error resilience of adaptive message exchange.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Computation over the Noisy Broadcast Channel with Malicious Parties.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

[BibT_eX]

[DOI]

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

Statistically Near-Optimal Hypothesis Selection.

[BibT_eX]

[DOI]

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

2020

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

[BibT_eX]

[DOI]

CoRR, 2020

Interactive error resilience beyond 2/7.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Noisy Beeps.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Interactive Coding with Constant Round and Communication Blowup.

[BibT_eX]

[DOI]

Elad Haramaty

Yael Tauman Kalai

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Fast and Bayes-consistent nearest neighbors.

[BibT_eX]

[DOI]

Aryeh Kontorovich

Moshe Noivirt

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

2019

Radio Network Coding Requires Logarithmic Overhead.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Optimal Short-Circuit Resilient Formulas.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

The method of shifted partial derivatives cannot separate the permanent from the determinant.

[BibT_eX]

[DOI]

Math. Comput., 2018

Interactive coding over the noisy broadcast channel.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Barriers for Rank Methods in Arithmetic Complexity.

[BibT_eX]

[DOI]

Rafael Mendes de Oliveira

Ankit Garg

Avi Wigderson

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

∊-MSR codes with small sub-packetization.

[BibT_eX]

[DOI]

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

2016

Testing Equality in Communication Graphs.

[BibT_eX]

[DOI]

Noga Alon

Benny Sudakov

Electron. Colloquium Comput. Complex., 2016

Constant-rate coding for multiparty interactive communication is impossible.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Reliable Communication over Highly Connected Noisy Networks.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

On minimal free resolutions and the method of shifted partial derivatives in complexity theory.

[BibT_eX]

[DOI]

CoRR, 2015

Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback.

[BibT_eX]

[DOI]

Ran Gelles

Bernhard Haeupler

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

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

[BibT_eX]

[DOI]

Mark Braverman

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

A theory of locally decodable codes

[BibT_eX]

[DOI]

PhD thesis, 2013

2012

From irreducible representations to locally decodable codes.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2010

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes.

[BibT_eX]

[DOI]

Avraham Ben-Aroya

Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2010

Local List Decoding with a Constant Number of Queries.

[BibT_eX]

[DOI]

Avraham Ben-Aroya

Amnon Ta-Shma

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

3-query locally decodable codes of subexponential length.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

From coding theory to efficient pattern matching.

[BibT_eX]

[DOI]

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

Pattern matching with don't cares and few errors.

[BibT_eX]

[DOI]

Proceedings of the Search Methodologies, 05.07. - 10.07.2009, 2009

How Well Do Random Walks Parallelize?.

[BibT_eX]

[DOI]

Omer Reingold

Proceedings of the Approximation, 2009

2008

Improved Deterministic Length Reduction

[BibT_eX]

[DOI]

CoRR, 2008

Mismatch Sampling.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2008

Approximating general metric distances between a pattern and a text.

[BibT_eX]

[DOI]

Ely Porat