Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > VC DIMENSION:
Reports tagged with VC Dimension:
TR94-024 | 12th December 1994
Marek Karpinski, Angus Macintyre

#### Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

We introduce a new method for proving explicit upper bounds on the VC
Dimension of general functional basis networks, and prove as an
application, for the first time, the VC Dimension of analog neural
networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$
to ... more >>>

TR95-051 | 16th October 1995
Pascal Koiran

#### VC Dimension in Circuit Complexity

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>

TR95-055 | 24th November 1995
Marek Karpinski, Angus Macintyre

#### VC Dimension of Sigmoidal and General Pfaffian Networks

We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ... more >>>

TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

#### Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

TR15-025 | 22nd February 2015
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

#### Teaching and compressing for low VC-dimension

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and
for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ... more >>> TR15-040 | 24th March 2015 Shay Moran, Amir Yehudayoff #### Proper PAC learning is compressing Revisions: 1 We prove that proper PAC learnability implies compression. Namely, if a concept$C \subseteq \Sigma^X$is properly PAC learnable with$d$samples, then$C$has a sample compression scheme of size$2^{O(d)}$. In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ... more >>> TR15-189 | 25th November 2015 Shay Moran, Cyrus Rashtchian #### Shattered Sets and the Hilbert Function Revisions: 2 We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>> TR18-051 | 15th March 2018 Stasys Jukna #### Derandomizing Dynamic Programming and Beyond Revisions: 1 We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>> TR20-114 | 22nd July 2020 Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar #### Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond The disjointness problem - where Alice and Bob are given two subsets of$\{1, \dots, n\}\$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

ISSN 1433-8092 | Imprint