6 papers
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…
Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to Adversarial Corruption
Meghal Gupta, Yael Tauman Kalai, Rachel Zhang
An error correcting code () allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver…
The Optimal Error Resilience of Interactive Communication Over Binary Channels
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 a non-adaptive (fixed order, fixe…
A formula for -Polynomials in terms of -Vectors and Stabilization of -Polynomials
Meghal Gupta
Given a quiver associated to a cluster algebra and a sequence of vertices, iterative mutation leads to -Polynomials which appear in numerous places in the cluster algebraic lite…
Bounding extremal functions of forbidden matrices using -formations
Jesse Geneson, Meghal Gupta
First, we prove tight bounds of on the extremal function of the forbidden pair of ordered sequences and $(…