13 papers
Linear-Time Encodable and Decodable Quantum Error-Correcting Codes
Adam Wills, Ting-Chun Lin, Rachel Yun Zhang +1
Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locall…
List Decoding Bounds for Binary Codes with Noiseless Feedback
Meghal Gupta, Rachel Yun Zhang
In an error-correcting code, a sender encodes a message such that it is still decodable by a receiver on the other end of a noisy channel. In the setting of \e…
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…
New Codes on High Dimensional Expanders
Irit Dinur, Siqi Liu, Rachel Yun Zhang
We describe a new parameterized family of symmetric error-correcting codes with low-density parity-check matrices (LDPC). Our codes can be described in two seemingly different ways…
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…
Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
In the setting of error-correcting codes with feedback, Alice wishes to communicate a -bit message to Bob by sending a sequence of bits over a channel while noiselessly rece…
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…
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…
-Sum-Free Sets
Rachel Zhang
The Minkowski sum of two subsets and of a finite abelian group is defined as all pairwise sums of elements of and : . The…
The Relation between Composability and Splittability of Permutation Classes
Rachel Zhang
A permutation class is said to be splittable if there exist two proper subclasses such that any can be red-blue colored so that the red (respective…