Fetching the paper…
Reading the bibliography…
Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning.
Matroids, submodular functions and certain polyhedra
Jack Edmonds · 1970
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.
Constant depth circuits, Fourier transform and learnability
N. Linial, Y. Mansour, and N. Nisan · 1993
Earlier work this paper cites.
Learning boolean formulas
M. Kearns, M. Li, and L. Valiant · 1994
Earlier work this paper cites.
Toward efficient agnostic learning
M. Kearns, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
On Russo’s approximate zero-one law
M. Talagrand · 1994
Earlier work this paper cites.
A combinatorial algorithm for minimizing symmetric submodular functions
Maurice Queyranne · 1995
Earlier work this paper cites.
On the Fourier spectrum of monotone functions
N. Bshouty and C. Tamon · 1996
Earlier work this paper cites.
How much are increasing sets positively correlated?
M. Talagrand · 1996
Earlier work this paper cites.
Matroids and submodular functions
András Frank · 1997
Earlier work this paper cites.
On learning monotone boolean functions
A. Blum, C. Burch, and J. Langford · 1998
Earlier work this paper cites.
Boolean functions with low average sensitivity depend on few coordinates
E. Friedgut · 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.
Testing monotonicity
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky · 2000
Earlier work this paper cites.
Rademacher processes and bounding the risk of function learning
Vladimir Koltchinskii and Dmitriy Panchenko · 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 and Gaussian complexities: Risk bounds and structural results
P. Bartlett and S. Mendelson · 2002
Earlier work this paper cites.
On the noise sensitivity of monotone functions
Elchanan Mossel and Ryan O’Donnell · 2002
Cited alongside, same era.
Concentration inequalities
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet · 2003
Cited alongside, same era.
Computational Applications of Noise Sensitivity
R. O’Donnell · 2003
Cited alongside, same era.
Near-optimal sensor placements in gaussian processes
C. Guestrin, A. Krause, and A. Singh · 2005
Cited alongside, same era.
On learning monotone boolean functions under the uniform distribution
Kazuyuki Amano and Akira Maruoka · 2006
Cited alongside, same era.
Combinatorial auctions with decreasing marginal utilities
D. J. Lehmann B. Lehmann and N. Nisan · 2006
Cited alongside, same era.
Approximating submodular functions everywhere
M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni · 2009
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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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.
On maximizing welfare when utility functions are subadditive
Uriel Feige · 2006
Cited alongside, same era.
Covering minimum spanning trees of random subgraphs
M. Goemans and J. Vondrák · 2006
Cited alongside, same era.
Near-optimal sensor placements: maximizing information while minimizing communication cost
A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg · 2006
Cited alongside, same era.
Concentration for self-bounding functions and an inequality of talagrand
C. McDiarmid and B. Reed · 2006
Cited alongside, same era.
Submodular functions are noise stable
M. Cheraghchi, A. Klivans, P. Kothari, and H. Lee · 2012
Later among the works it cites.
Concise representations of discrete submodular functions, 2013
E. Blais, K. Onak, R. Servedio, and G. Yaroslavtsev · 2013
Later among the works it cites.
Representation, approximation and learning of submodular functions using low-rank decision trees
V. Feldman, P. Kothari, and J. Vondrák · 2013
Later among the works it cites.
Optimal bounds on approximation of submodular and XOS functions by juntas
V. Feldman and J. Vondrák · 2013
Later among the works it cites.
Learning halfspaces under log-concave densities: Polynomial approximations and moment matching
Daniel M. Kane, Adam Klivans, and Raghu Meka · 2013
Later among the works it cites.
KKL, Kruskal-Katona, and monotone nets
Ryan O’Donnell and Karl Wimmer · 2013
Later among the works it cites.
Learning pseudo-boolean k-DNF and submodular functions
S. Raskhodnikova and G. Yaroslavtsev · 2013
Later among the works it cites.
The need for structure in quantum speedups
Scott Aaronson and Andris Ambainis · 2014
Later among the works it cites.
On the sum of L1 influences
Arturs Backurs and Mohammad Bavarian · 2014
Later among the works it cites.
L p {}_{\mbox{p}} -testing
Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev · 2014
Later among the works it cites.
Learning coverage functions and private release of marginals
V. Feldman and P. Kothari · 2014
Later among the works it cites.
Nearly tight bounds on $\ell_1$ approximation of self-bounding functions
V. Feldman, P. Kothari, and J. Vondrák · 2014
Later among the works it cites.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Later among the works it cites.
Approximate resilience, monotonicity, and the complexity of agnostic learning
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer · 2015
Closest in time.