Approximate F₂-Sketching of Valuation Functions
From MaRDI portal
Approximate F 2-Sketching of Valuation Functions
Recommendations
- scientific article; zbMATH DE number 7250148
- Exponential tractability of \(L_2\)-approximation with function values
- Approximation of multi-valued mappings
- On approximations of multivalued maps
- The relative approximation degree in valued function fields
- Sketching valuation functions
- scientific article; zbMATH DE number 15286
- Approximation of contractible valued correspondences by functions
- scientific article; zbMATH DE number 55000
Cites work
- Analysis of Boolean Functions
- Communication Complexity
- Communication Complexity of Simultaneous Messages
- Composition theorems in communication complexity
- Extensions of Lipschitz mappings into a Hilbert space
- scientific article; zbMATH DE number 3668648 (Why is no real title available?)
- scientific article; zbMATH DE number 1769898 (Why is no real title available?)
- scientific article; zbMATH DE number 7051222 (Why is no real title available?)
- scientific article; zbMATH DE number 7250148 (Why is no real title available?)
- scientific article; zbMATH DE number 6789285 (Why is no real title available?)
- Incidence geometries and the pass complexity of semi-streaming set cover
- Is submodularity testable?
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- Learning submodular functions
- On the parity complexity measures of Boolean functions
- On the power of circuits with gates of low \(L_{1}\) norms.
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
- Randomized communication complexity for linear algebra problems over finite fields
- Recent advances on the log-rank conjecture in communication complexity
- SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
- Semi-streaming algorithms for annotated graph streams
- Semi-streaming set cover
- Single pass spectral sparsification in dynamic streams
- Sketching as a tool for numerical linear algebra
- Sketching valuation functions
- Sparse and Lopsided Set Disjointness via Information Theory
- Streaming algorithms for submodular function maximization
- Structure of protocols for XOR functions
- Submodular functions are noise stable
- Testing coverage functions
- Testing submodularity and other properties of valuation functions
- The communication complexity of the Hamming distance problem
- The space complexity of approximating the frequency moments
- Tight bounds for single-pass streaming complexity of the set cover problem
- Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
- Turnstile streaming algorithms might as well be linear sketches
This page was built for publication: Approximate F_2-Sketching of Valuation Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875529)
