1.2k citations · 2.5k across the 41 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
quant-ph2016★ 21 cited
Optimal Quantum Sample Complexity of Learning Algorithms
Srinivasan Arunachalam, Ronald de Wolf
In learning theory, the VC dimension of a concept class is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\…
cs.CC2016★ 5 cited
On the sum-of-squares degree of symmetric quadratic functions
Troy Lee, Anupam Prakash, Ronald de Wolf +1
We study how well functions over the boolean hypercube of the form can be approximated by sums of squares of low-degree polynomials, obtaining good bounds…