Fetching the paper…
Reading the bibliography…
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}).
Étude des coefficients de Fourier des fonctions de L p ( G ) L^{p}(G)
A. Bonami · 1970
Earlier work this paper cites.
Matroids, submodular functions and certain polyhedra
Jack Edmonds · 1970
Earlier work this paper cites.
Inequalities in Fourier analysis
W. Beckner · 1975
Earlier work this paper cites.
Submodular functions and convexity
László Lovász · 1983
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Collective coin flipping, robust voting schemes and minima of banzhaf values
M. Ben-Or and N. Linial · 1985
Earlier work this paper cites.
The influence of variables on Boolean functions
J. Kahn, G. Kalai, and N. Linial · 1988
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
On the degree of boolean functions as real polynomials
N. Nisan and M. Szegedy · 1992
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
E. Kushilevitz and Y. Mansour · 1993
Earlier work this paper cites.
Toward efficient agnostic learning
M. Kearns, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
An O ( n log log n ) O(n^{\log\log n}) learning algorithm for DNF under the uniform distribution
Y. Mansour · 1995
Earlier work this paper cites.
A combinatorial algorithm for minimizing symmetric submodular functions
Maurice Queyranne · 1995
Earlier work this paper cites.
Matroids and submodular functions
András Frank · 1997
Earlier work this paper cites.
Boolean functions with low average sensitivity depend on few coordinates
E. Friedgut · 1998
Earlier work this paper cites.
Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron · 1998
Earlier work this paper cites.
Statistical Learning Theory
V. Vapnik · 1998
Earlier work this paper cites.
A sharp concentration inequality with applications
S. Boucheron, G. Lugosi, and P. Massart · 2000
Earlier work this paper cites.
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
L. Fleischer, S. Fujishige, and S. Iwata · 2001
Earlier work this paper cites.
Rademacher penalties and structural risk minimization
Vladimir Koltchinskii · 2001
Earlier work this paper cites.
Rademacher and Gaussian complexities: Risk bounds and structural results
P. Bartlett and S. Mendelson · 2002
Cited alongside, same era.
On the distribution of the fourier spectrum of boolean functions
Jean Bourgain · 2002
Cited alongside, same era.
Boolean functions whose Fourier transform is concentrated on the first two levels
E. Friedgut, G. Kalai, and A. Naor · 2002
Cited alongside, same era.
Concentration inequalities
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet · 2003
Cited alongside, same era.
On learning monotone DNF under product distributions
R. Servedio · 2004
Cited alongside, same era.
Lecture notes for analytical methods in combinatorics and computer-science (lect 5)
I. Dinur and E. Friedgut · 2005
Cited alongside, same era.
Agnostically learning decision trees
P. Gopalan, A. Kalai, and A. Klivans · 2008
Later among the works it cites.
Vertex cover might be hard to approximate to within 2- ϵ \epsilon ;
S. Khot and O. Regev · 2008
Later among the works it cites.
Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies
A. Krause, A. Singh, and C. Guestrin · 2008
Later among the works it cites.
On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
S. Kakade, K. Sridharan, and A. Tewari · 2008
Later among the works it cites.
Optimal approximation for the submodular welfare problem in the value oracle model
J. Vondrák · 2008
Later among the works it cites.
Improved approximation of linear threshold functions
I. Diakonikolas and R. Servedio · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the hardness of approximating minimum vertex cover
I. Dinur and S. Safra · 2005
Cited alongside, same era.
Near-optimal sensor placements in gaussian processes
C. Guestrin, A. Krause, and A. Singh · 2005
Cited alongside, same era.
Combinatorial auctions with decreasing marginal utilities
D. J. Lehmann B. Lehmann and N. Nisan · 2006
Cited alongside, same era.
On the hardness of approximating multicut and sparsest-cut
S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar · 2006
Cited alongside, same era.
On the Fourier tails of bounded functions over the discrete cube
I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell · 2006
Cited alongside, same era.
An improved approximation algorithm for combinatorial auctions with submodular bidders
S. Dobzinski and M. Schapira · 2006
Cited alongside, same era.
Later among the works it cites.
Approximating submodular functions everywhere
M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni · 2009
Later among the works it cites.
A note on concentration of submodular functions, 2010
J. Vondrák · 2010
Later among the works it cites.
Submodular functions: Learnability, structure, and optimization
M.F. Balcan and N. Harvey · 2011
Later among the works it cites.
Privately releasing conjunctions and the statistical query barrier
A. Gupta, M. Hardt, A. Roth, and J. Ullman · 2011
Later among the works it cites.
Is submodularity testable?
C. Seshadhri and J. Vondrák · 2011
Later among the works it cites.
Learning valuation functions
M.F. Balcan, F. Constantin, S. Iwata, and L. Wang · 2012
Later among the works it cites.
Sketching valuation functions
A. Badanidiyuru, S. Dobzinski, Hu Fu, R. Kleinberg, N. Nisan, and T. Roughgarden · 2012
Later among the works it cites.
Submodular functions are noise stable
M. Cheraghchi, A. Klivans, P. Kothari, and H. Lee · 2012
Later among the works it cites.
DNF sparsification and a faster deterministic counting algorithm
P. Gopalan, R. Meka, and O. Reingold · 2012
Later among the works it cites.
Concise representations of discrete submodular functions, 2013
E. Blais, K. Onak, R. Servedio, and G. Yaroslavtsev · 2013
Closest in time.
Representation, approximation and learning of submodular functions using low-rank decision trees
V. Feldman, P. Kothari, and J. Vondrák · 2013
Closest in time.
Learning pseudo-boolean k-DNF and submodular functions
S. Raskhodnikova and G. Yaroslavtsev · 2013
Closest in time.
Learning coverage functions and private release of marginals
Vitaly Feldman and Pravesh Kothari · 2014
Closest in time.