Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
From MaRDI portal
Publication:2816303
DOI10.1137/140958207zbMath1345.68251arXiv1307.3301OpenAlexW2460132610MaRDI QIDQ2816303
Publication date: 4 July 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.3301
Related Items (7)
The Limitations of Optimization from Samples ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Recognizing Coverage Functions ⋮ Tractability of explaining classifier decisions ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Improved approximation of linear threshold functions
- On the hardness of approximating minimum vertex cover
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Inequalities in Fourier analysis
- Boolean functions with low average sensitivity depend on few coordinates
- Toward efficient agnostic learning
- On the distribution of the Fourier spectrum of Boolean functions
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- On learning monotone DNF under product distributions
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- On the hardness of approximating Multicut and Sparsest-Cut
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Combinatorial auctions with decreasing marginal utilities
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On maximizing welfare when utility functions are subadditive
- On the fourier tails of bounded functions over the discrete cube
- Maximizing Non-monotone Submodular Functions
- Property testing and its connection to learning and approximation
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Covering minimum spanning trees of random subgraphs
- Concentration for self-bounding functions and an inequality of Talagrand
- Learning Monotone Decision Trees in Polynomial Time
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Improved lower bounds for embeddings into L1
- A theory of the learnable
- Learning Decision Trees Using the Fourier Spectrum
- A sharp concentration inequality with applications
- Rademacher penalties and structural risk minimization
- Submodular Functions: Learnability, Structure, and Optimization
- 10.1162/153244303321897690
- Advanced Lectures on Machine Learning
- Learning Pseudo-Boolean k-DNF and Submodular Functions
This page was built for publication: Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
