2017
COLT
COLT 2017
Inapproximability of VC Dimension and Littlestone’s Dimension
Abstract
We study the complexity of computing the VC Dimension and Littlestone’s Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$-th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasi-polynomial time ($n^O(\log n)$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for \em approximation algorithms.
🌉
Interdisciplinary Bridge
— Computer Science and Machine Learning
🧭
Keyword Pioneer
— quasi-polynomial time
🐣
Hot Topic Early Bird
— lower bound
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio