Arrow Research search

Author name cluster

Ray Li

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
1 author row

Possible papers

12

STOC Conference 2024 Conference Paper

Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields

  • Omar Alrabiah
  • Venkatesan Guruswami
  • Ray Li

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 elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed–Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam, established that Reed–Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed–Solomon codes over an exponentially large field size 2 O ( n ) , where n is the block length of the code. A natural question is whether Reed–Solomon codes can still achieve capacity over smaller fields. Recently, Guo and Zhang showed that Reed–Solomon codes are list-decodable to capacity with field size O ( n 2 ). We show that Reed–Solomon codes are list-decodable to capacity with linear field size O ( n ), which is optimal up to the constant factor. We also give evidence that the ratio between the alphabet size q and code length n cannot be bounded by an absolute constant. Our techniques also show that random linear codes are list-decodable up to (the alphabet-independent) capacity with optimal list-size O (1/ε) and near-optimal alphabet size 2 O (1/ε 2 ) , where ε is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O (1/ε) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. Our proofs are based on the ideas of Guo and Zhang, and we additionally exploit symmetries of reduced intersection matrices. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.

Details

FOCS Conference 2021 Conference Paper

Hardness of Approximate Diameter: Now for Undirected Graphs

  • Mina Dalirrooyfard
  • Ray Li
  • Virginia Vassilevska Williams

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer $k\geq 2$ and $\delta > 0$, a $2-\frac{1}{k}-\delta$ approximation for diameter in directed $m$ -edge graphs requires $mn^{1+1/(k-1)-o(1)}$ time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W. , STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, $k=2, 3$ and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

Details

FOCS Conference 2021 Conference Paper

Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]

  • Zeyu Guo 0001
  • Ray Li
  • Chong Shangguan
  • Itzhak Tamo
  • Mary Wootters

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0, 1] there exist RS codes with rate $\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$ that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist $(1-\varepsilon, \ell, O(\ell/\varepsilon))$ -list-recoverable RS codes with rate $\Omega\left(\frac{\varepsilon}{\sqrt{\ell}(\log(1/\varepsilon)+1)}\right)$. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable. 1 1 A full version of this paper is available online at https: //arxiv. org/abs/2011. 04453.

Details

FOCS Conference 2021 Conference Paper

The zero-rate threshold for adversarial bit-deletions is less than 1/2

  • Venkatesan Guruswami
  • Xiaoyu He
  • Ray Li

We prove that there exists an absolute constant 6 > 0 such any binary code $C$ ⊂ {0, 1} N tolerating (1/2 - δ) $N$ adversarial deletions must satisfy| C| ≤ 2 polylog $N$ and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating $N$ /2 adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants $A$ and 6 > 0 such that any set $C$ ⊂ {0, 1} of 2 log A N binary strings must contain two strings $c$ and c’ whose longest common subsequence has length at least (1/2 + δ) N. As an immediate corollary, we show that q-ary codes tolerating a fraction 1 - (1 + 2δ) / $q$ of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.

Details

SODA Conference 2020 Conference Paper

A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree

  • Ray Li
  • Percy Liang
  • Stephen Mussmann

D ecision T ree is a classic formulation of active learning: given n hypotheses with nonnegative weights summing to 1 and a set of tests that each partition the hypotheses, output a decision tree using the provided tests that uniquely identifies each hypothesis and has minimum (weighted) average depth. Previous works showed that the greedy algorithm achieves a O (log n ) approximation ratio for this problem and it is NP-hard beat a O (log n ) approximation, settling the complexity of the problem. However, for U niform D ecision T ree, i. e. D ecision T ree with uniform weights, the story is more subtle. The greedy algorithm's O (log n ) approximation ratio was the best known, but the largest approximation ratio known to be NP-hard is 4 – ε. We prove that the greedy algorithm gives a approximation for Uniform D ecision T ree, where C OPT is the cost of the optimal tree and show this is best possible for the greedy algorithm. As a corollary, we resolve a conjecture of Kosaraju, Przytycka, and Borgstrom [20]. Our results also hold for instances of D ecisio N T ree whose weights are not too far from uniform. Leveraging this result, for all α ϵ (0, 1), we exhibit a approximation algorithm to Uniform D ecision T ree running in subexponential time. As a corollary, achieving any super-constant approximation ratio on U niform D ecision T ree is not NP-hard, assuming the Exponential Time Hypothesis. This work therefore adds approximating U niform D ecision T ree to a small list of natural problems that have subexponential time algorithms but no known polynomial time algorithms. Like the analysis of the greedy algorithm, our analysis of the subexponential time algorithm gives similar approximation guarantees even for slightly nonuniform weights. A key technical contribution of our work is showing a connection between greedy algorithms for U niform D ecision T ree and for M in S um S et C over.

Details

FOCS Conference 2020 Conference Paper

Coded trace reconstruction in a constant number of traces

  • Joshua Brakensiek
  • Ray Li
  • Bruce Spang

The coded trace reconstruction problem asks to construct a code C ⊂ {0, 1} n such that any x ∈ C is recoverable from independent outputs (“traces”) of x from a binary deletion channel (BDC). We present binary codes of rate 1-ε that are efficiently recoverable from exp(Oq(log 1/3 ([1/(ε)]))) (a constant independent of n) traces of a BDCq for any constant deletion probability q ∈ (0, 1). We also show that, for rate 1 -ε binary codes, ~Ω(log 5/2 (1/ε)) traces are required. The results follow from a pair of black-box reductions that show that average-case trace reconstruction is essentially equivalent to coded trace reconstruction. We also show that there exist codes of rate 1 -ε over an Oε(1)-sized alphabet that are recoverable from O(log(1/ε)) traces, and that this is tight.

Details

MFCS Conference 2019 Conference Paper

Enumeration of Preferred Extensions in Almost Oriented Digraphs

  • Serge Gaspers
  • Ray Li

In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on n vertices, all preferred extensions can be enumerated in O^*(3^{n/3}) time and there are directed graphs with Omega(3^{n/3}) preferred extensions. We give faster enumeration algorithms for directed graphs with at most 0. 8004 * n vertices occurring in 2-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time O(1. 2321^n), and we show that there are oriented graphs with Omega(3^{n/6}) > Omega(1. 2009^n) preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in 2-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017).

Details