Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Meghal Gupta:

TR23-131 | 8th September 2023
Meghal Gupta, Rachel Zhang

On Interactive Coding Schemes with Adaptive Termination

In interactive coding, Alice and Bob wish to compute some function $f$ of their individual private inputs $x$ and $y$. They do this by engaging in an interactive protocol to jointly compute $f(x,y)$. The goal is to do this in an error-resilient way, such that even given some fraction of ... more >>>

TR23-104 | 14th July 2023
Meghal Gupta, Rachel Zhang

A Noise Resilient Transformation for Streaming Algorithms

In a streaming algorithm, Bob receives an input $x \in \{0,1\}^n$ via a stream and must compute a function $f$ in low space. However, this function may be fragile to errors in the input stream. In this work, we investigate what happens when the input stream is corrupted. Our main ... more >>>

TR22-095 | 5th July 2022
Meghal Gupta, Rachel Zhang

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>

ISSN 1433-8092 | Imprint