Meghal Gupta

activity

20162024

most citedTight Space Lower Bound for Pseudo-Deterministic Approximate Counting

1 citations · 1 across the 9 of their papers we have counts for

collaborators

Showing 2022 · cs.DSShow all

3 papers · 2 filters

cs.DS2022

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Meghal Gupta, Rachel Yun Zhang

Given a noiseless protocol $π_{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…

cs.DS2022

An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Sarayu Manoj

Given query access to a monotone function $f : {0, 1}^{n} \to {0, 1}$ with certificate complexity $C (f)$ and an input $x^{⋆}$ , we design an algorithm that outputs a size-$C(f)…

cs.DS2022

Positive Rate Binary Interactive Error Correcting Codes Resilient to $> \frac{1}{2}$ Adversarial Erasures

Meghal Gupta, Rachel Zhang

An interactive error correcting code ( $iECC$ ) is an interactive protocol with the guarantee that the receiver can correctly determine the sender's message, even in the pre…

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

An Optimal Algorithm for Certifying Monotone Functions

Positive Rate Binary Interactive Error Correcting Codes Resilient to >21​ Adversarial Erasures

Positive Rate Binary Interactive Error Correcting Codes Resilient to $> \frac{1}{2}$ Adversarial Erasures