Fetching the paper…
Reading the bibliography…
We study the problem of approximating and learning coverage functions.
Matroids, submodular functions and certain polyhedra
J. Edmonds · 1970
Earlier work this paper cites.
Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
G. Cornuejols, M. Fisher, and G. Nemhauser · 1977
Earlier work this paper cites.
Submodular functions and convexity
L. Lovász · 1983
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
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.
Learning decision trees using the Fourier spectrum
E. Kushilevitz and Y. Mansour · 1993
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. Goemans and D. Williamson · 1995
Earlier work this paper cites.
Selection of relevant features and examples in machine learning
A. Blum and P. Langley · 1997
Earlier work this paper cites.
Matroids and submodular functions
A. Frank · 1997
Earlier work this paper cites.
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
J. Jackson · 1997
Earlier work this paper cites.
A threshold of ln n \ln n for approximating set cover
U. Feige · 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.
Learning dnf in time 2 õ(n 1/3 {}^{\mbox{1/3}} )
A. Klivans and R. Servedio · 2004
Earlier work this paper cites.
Practical privacy: the sulq framework
A. Blum, C. Dwork, F. McSherry, and K. Nissim · 2005
Earlier work this paper cites.
Near-optimal sensor placements in gaussian processes
C. Guestrin, A. Krause, and A. Singh · 2005
Earlier work this paper cites.
Combinatorial auctions with decreasing marginal utilities
D. J. Lehmann B. Lehmann and N. Nisan · 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.
Calibrating noise to sensitivity in private data analysis
C. Dwork, F. McSherry, K. Nissim, and A. Smith · 2006
Cited alongside, same era.
On maximizing welfare when utility functions are subadditive
U. Feige · 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.
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar · 2007
Sketching valuation functions
A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan, and T. Roughgarden · 2012
Later among the works it cites.
Learning valuation functions
M.F. Balcan, Florin Constantin, Satoru Iwata, and Lei Wang · 2012
Later among the works it cites.
Testing coverage functions
D. Chakrabarty and Z. Huang · 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.
A complete characterization of statistical query learning with applications to evolvability
V. Feldman · 2012
Later among the works it cites.
Private data release via learning thresholds
M. Hardt, G. Rothblum, and R. Servedio · 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…
Cited alongside, same era.
Polynomial regression under arbitrary product distributions
E. Blais, R. O’Donnell, and K. Wimmer · 2008
Cited alongside, same era.
Agnostically learning halfspaces
A. Kalai, A. Klivans, Y. Mansour, and R. Servedio · 2008
Cited alongside, same era.
Optimal approximation for the submodular welfare problem in the value oracle model
J. Vondrák · 2008
Cited alongside, same era.
On the complexity of differentially private data release: efficient algorithms and hardness results
C. Dwork, M. Naor, O. Reingold, G. Rothblum, and S. Vadhan · 2009
Cited alongside, same era.
A note on concentration of submodular functions
Jan Vondrák · 2010
Cited alongside, same era.
Least absolute deviations, 2010
Wikipedia · 2010
Cited alongside, same era.
S. Raskhodnikova and G. Yaroslavtsev · 2012
Later among the works it cites.
Faster algorithms for privately releasing marginals
J. Thaler, J. Ullman, and S. Vadhan · 2012
Later among the works it cites.
Fingerprinting codes and the price of approximate differential privacy
M. Bun, J. Ullman, and S. P. Vadhan · 2013
Closest in time.
Efficient algorithms for privately releasing marginals via convex relaxations
C. Dwork, A. Nikolov, and K. Talwar · 2013
Closest in time.
Optimal bounds on approximation of submodular and xos functions by juntas
V. Feldman and J. Vondrák · 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.
Submodular optimization with submodular cover and submodular knapsack constraints
R. K. Iyer and J. A. Bilmes · 2013
Closest in time.
Learnability of DNF with representation-specific queries
L. Yang, A. Blum, and J. Carbonell · 2013
Closest in time.
Faster private release of marginals on small databases
K. Chandrasekaran, J. Thaler, J. Ullman, and A. Wan · 2014
Closest in time.
Agnostic learning of disjunctions on symmetric distributions
V. Feldman and P. Kothari · 2014
Closest in time.