论文标题
通过（不平衡）双质
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
论文作者
论文摘要
当我们得到明确给予概念类别时，我们研究计算（和近似）VC维度和Littlestone维度的复杂性。我们从最大（不平衡）双智能问题中简单地减少了近似VC维度和Littlestone的尺寸。通过这种连接，我们得出了一系列近似结果和运行时间下限的硬度。例如，在（随机的）间隙指数时间假设或强烈种植的集团假设下，我们显示出严格的不XIMIMISINE结果：在多项式时间中，这两个维度都难以近似于$ O（\ log n）$的因子。这些改善了[Manurangsi和Rubinstein，Colt，2017]的恒定因素不可Ximibibibibibibibility。
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].
