Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique

November 02, 2022 · The Ethereal · 🏛 Information Technology Convergence and Services

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Pasin Manurangsi arXiv ID 2211.01443 Category cs.CC: Computational Complexity Cross-listed cs.LG Citations 9 Venue Information Technology Convergence and Services Last Checked 6 months ago

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].