8 papers · 1 filter
On Interactive Coding Schemes with Adaptive Termination
Meghal Gupta, Rachel Yun Zhang
In interactive coding, Alice and Bob wish to compute some function of their individual private inputs and . They do this by engaging in an interactive protocol to jointl…
Error Correction for Message Streams
Meghal Gupta, Rachel Yun Zhang
In the setting of error correcting codes, Alice wants to send a message to Bob via an encoding that is resilient to error. In this work, we invest…
A New Upper Bound on the Maximal Error Resilience of Interactive Error-Correcting Codes
Meghal Gupta, Rachel Yun Zhang
In an interactive error-correcting code (iECC), Alice and Bob engage in an interactive protocol with the goal of Alice communicating a message to Bob in such a…
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Ofer Grossman, Meghal Gupta, Mark Sellke
We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. In 1978, Morris famously gave a randomized algorithm achi…
An Optimal Algorithm for Certifying Monotone Functions
Meghal Gupta, Naren Sarayu Manoj
Given query access to a monotone function with certificate complexity and an input , we design an algorithm that outputs a size-$C(f)…
Positive Rate Binary Interactive Error Correcting Codes Resilient to Adversarial Erasures
Meghal Gupta, Rachel Zhang
An interactive error correcting code () is an interactive protocol with the guarantee that the receiver can correctly determine the sender's message, even in the pre…