1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
Ray Li
We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any , assuming the Strong Exponenti…
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…
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Ray Li, Percy Liang, Stephen Mussmann
Decision Tree is a classic formulation of active learning: given hypotheses with nonnegative weights summing to 1 and a set of tests that each partition the hypotheses, output…
Lower bounds for Max-Cut in -free graphs via semidefinite programming
Charles Carlson, Alexandra Kolla, Ray Li +3
For a graph , let denote the size of the maximum cut in . The problem of estimating as a function of the number of vertices and edges of has a long history…