Approximate degree composition for recursive functions
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 6789270 (Why is no real title available?)
- Adaptivity vs. postselection, and hardness amplification for polynomial approximation
- Agnostically Learning Halfspaces
- An improved lower bound for the randomized decision tree complexity of recursive majority
- Approximate Degree in Classical and Quantum Computing
- Approximate degree composition for recursive functions
- Approximate inclusion-exclusion for arbitrary symmetric functions
- Approximating the AND-OR tree
- Classical lower bounds from quantum upper bounds
- Composition limits and separating examples for some Boolean function complexity measures
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Impossibility of succinct quantum proofs for collision-freeness
- Improved bounds for the randomized decision tree complexity of recursive majority
- Inclusion-exclusion: exact and approximate
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Learning intersections and thresholds of halfspaces
- Low-sensitivity functions from unambiguous certificates
- Lower bounds on probabilistic linear decision trees
- Making polynomials robust to noise
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- On rank vs. communication complexity
- On the composition of randomized query complexity and approximate degree
- On the degree of Boolean functions as real polynomials
- On the power of statistical zero knowledge
- Perceptrons, PP, and the polynomial hierarchy
- Properties and applications of Boolean function composition
- Quantum lower bounds by polynomials
- Quantum lower bounds for the collision and the element distinctness problems
- Robust polynomials and quantum algorithms
- Short monotone formulae for the majority function
- Span-program-based quantum algorithm for evaluating formulas
- Strong direct product theorems for quantum communication and query complexity
- The intersection of two halfspaces has high threshold degree
- The pattern matrix method
- Toward attribute efficient learning of decision lists and parities
- Two applications of information complexity
This page was built for publication: Approximate degree composition for recursive functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920765)
