23 citations · 74 across the 22 of their papers we have counts for
3 papers · 1 filter
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…
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…
List Learning with Attribute Noise
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba +2
We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT 1988) as a variant of PAC learn…