Showing 2024Show all
3 papers · 1 filter
cs.CC2024
Nearly-Linear Time Seeded Extractors with Short Seeds
Dean Doron, João Ribeiro
Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameter…
cs.IT2024
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
Dean Doron, Jonathan Mosheiff, Mary Wootters
The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate has relative distance at least $\fra…
cs.IT2024
Random Reed-Solomon Codes are List Recoverable with Optimal List Size
Dean Doron, S. Venkitesh
We prove that Reed-Solomon (RS) codes with random evaluation points are list recoverable up to capacity with optimal output list size, for any input list size. Namely, given an inp…