5 papers
Dueling Optimization with a Monotone Adversary
Avrim Blum, Meghal Gupta, Gene Li +3
We introduce and study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an…
Constant Query Local Decoding Against Deletions Is Impossible
Meghal Gupta
Locally decodable codes (LDC's) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices. For substituti…
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…
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…
Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel
Meghal Gupta, Rachel Yun Zhang
Given a noiseless protocol computing a function of Alice and Bob's private inputs , the goal of interactive coding is to construct an error-resilient protocol…