Klim Efremenko

Or Zamir

CoRR, 2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Protecting Single-Hop Radio Networks from Message Drops.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Lower bounds for regular resolution over parities.

[BibT_eX]

[DOI]

Michal Garlík

Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2023

2022

Optimal Short-Circuit Resilient Formulas.

[BibT_eX]

[DOI]

J. ACM, 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Circuits Resilient to Short-Circuit Errors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Round-vs-Resilience Tradeoffs for Binary Feedback Channels.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Optimal Error Resilience of Adaptive Message Exchange.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Computation Over the Noisy Broadcast Channel with Malicious Parties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Statistically Near-Optimal Hypothesis Selection.

[BibT_eX]

[DOI]

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

2020

Interactive Error Resilience Beyond 2/7.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

CoRR, 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]

Electron. Colloquium Comput. Complex., 2019

Noisy Beeps.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Reliable communication over highly connected noisy networks.

[BibT_eX]

[DOI]

Distributed Comput., 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 with Constant Round and Communication Blowup.

[BibT_eX]

[DOI]

Elad Haramaty

Yael Kalai

Electron. Colloquium Comput. Complex., 2018

2017

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

[BibT_eX]

[DOI]

Mark Braverman

SIAM J. Comput., 2017

Interactive Coding Over the Noisy Broadcast Channel.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Barriers for Rank Methods in Arithmetic Complexity.

[BibT_eX]

[DOI]

Rafael Mendes de Oliveira

Ankit Garg

Avi Wigderson

Electron. Colloquium Comput. Complex., 2017

∊-MSR codes with small sub-packetization.

[BibT_eX]

[DOI]

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

2016

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

[BibT_eX]

[DOI]

Ran Gelles

Bernhard Haeupler

IEEE Trans. Inf. Theory, 2016

Testing Equality in Communication Graphs.

[BibT_eX]

[DOI]

Noga Alon

Benny Sudakov

Electron. Colloquium Comput. Complex., 2016

2015

Constant-rate coding for multiparty interactive communication is impossible.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

2013

A theory of locally decodable codes

[BibT_eX]

[DOI]

PhD thesis, 2013

2012

3-Query Locally Decodable Codes of Subexponential Length.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Mismatch sampling.

[BibT_eX]

[DOI]

Inf. Comput., 2012

2011

A black box for online approximate pattern matching.

[BibT_eX]

[DOI]

Inf. Comput., 2011

From Irreducible Representations to Locally Decodable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

2010

Pattern matching with don't cares and few errors.

[BibT_eX]

[DOI]

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

Electron. Colloquium Comput. Complex., 2010

2009

From coding theory to efficient pattern matching.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Approximating general metric distances between a pattern and a text.

[BibT_eX]

[DOI]

Ely Porat