9 citations · 17 across the 6 of their papers we have counts for
9 papers
Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
Minshen Zhu
Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenom…
Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Alexander R. Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes encoding \emph{messages} in to \emph{codewords} in , with super-fast decoding algo…
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
Kuan Cheng, Elena Grigorescu, Xin Li +2
The goal of the trace reconstruction problem is to recover a string given many independent {\em traces} of , where a trace is a subsequence obtained from deletin…
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Alex Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes with super-fast decoding algorithms. They are important mathematical objects in many areas of theor…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
A heapable sequence is a sequence of numbers that can be arranged in a "min-heap data structure". Finding a longest heapable subsequence of a given sequence was proposed by Byers,…
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Trace reconstruction considers the task of recovering an unknown string given a number of independent "traces", i.e., subsequences of obtained by randomly and…
The Maximum Binary Tree Problem
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree…
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Pinyan Lu, Kuan Yang, Chihao Zhang +1
Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approxima…