Ray Li

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

2019 · Society for Industrial and Applied Mathematics eBooks

Decision Tree 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 …

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

2024

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, …