research
∙
09/08/2023
On Interactive Coding Schemes with Adaptive Termination
In interactive coding, Alice and Bob wish to compute some function f of ...
share
research
∙
07/13/2023
A Noise Resilient Transformation for Streaming Algorithms
In a streaming algorithm, Bob receives an input x ∈{0,1}^n via a stream ...
research
∙
05/07/2023
A New Upper Bound on the Maximal Error Resilience of Interactive Error-Correcting Codes
In an interactive error-correcting code (iECC), Alice and Bob engage in ...
research
∙
04/04/2023
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
We investigate one of the most basic problems in streaming algorithms: a...
research
∙
12/12/2022
Binary Error-Correcting Codes with Minimal Noiseless Feedback
In the setting of error-correcting codes with feedback, Alice wishes to ...
research
∙
07/03/2022
Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel
Given a noiseless protocol π_0 computing a function f(x, y) of Alice and...
research
∙
04/04/2022
An Optimal Algorithm for Certifying Monotone Functions
Given query access to a monotone function f{0,1}^n→{0,1} with certificat...
research
∙
01/28/2022
Positive Rate Binary Interactive Error Correcting Codes Resilient to >1/2 Adversarial Erasures
An interactive error correcting code (𝗂𝖤𝖢𝖢) is an interactive protocol w...
research
∙
11/07/2021
Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to >1/2 Adversarial Corruption
An error correcting code (𝖤𝖢𝖢) allows a sender to send a message to a re...
research
∙
10/28/2021
