15 citations · 48 across the 23 of their papers we have counts for
30 papers
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
Omar Alrabiah, Venkatesan Guruswami, Ray Li
A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate codes are not list-decodable using list-size beyond an error…
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
Improved rate-distance trade-offs for quantum codes with restricted connectivity
Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna +1
For quantum error-correcting codes to be realizable, it is important that the qubits subject to the code constraints exhibit some form of limited connectivity. The works of Bravyi…
Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami +2
Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field element…
Approximating binary longest common subsequence in almost-linear time
Xiaoyu He, Ray Li
The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programmi…
Efficient Near-Optimal Codes for General Repeat Channels
Francisco Pernice, Ray Li, Mary Wootters
Given a probability distribution over the non-negative integers, a -repeat channel acts on an input symbol by repeating it a number of times distributed…