4 papers
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,…
Locally Decodable/Correctable Codes for Insertions and Deletions
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu +2
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-c…
On Locally Decodable Codes in Resource Bounded Channels
Jeremiah Blocki, Shubhang Kulkarni, Samson Zhou
Constructions of locally decodable codes (LDCs) have one of two undesirable properties: low rate or high locality (polynomial in the length of the message). In settings where the e…
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…