REVIEW 1 cited by
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We study the complexity of computing (and approximating) VC Dimension and Littlestone's Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension and Littlestone's Dimension. With this connection, we derive a range of hardness of approximation results and running time lower bounds. For example, under the (randomized) Gap-Exponential Time Hypothesis or the Strongish Planted Clique Hypothesis, we show a tight inapproximability result: both dimensions are hard to approximate to within a factor of $o(\log n)$ in polynomial-time. These improve upon constant-factor inapproximability results from [Manurangsi and Rubinstein, COLT 2017].
Forward citations
Cited by 1 Pith paper
-
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
For learners restricted to ERM or weak consistency oracles, the paper proves exponential mistake and regret lower bounds in online learning and polynomial-query upper bounds in transductive online learning, with impro...
Discussion (0). Continue with ORCID to comment.