Separations between combinatorial measures for transitive functions
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- A composition theorem for decision tree complexity
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- A strong direct product theorem for quantum query complexity
- Adversary lower bound for the \(k\)-sum problem
- An improved lower bound on the sensitivity complexity of graph properties
- Block sensitivity of minterm-transitive functions
- Block sensitivity of weakly symmetric functions
- Complexity measures and decision tree complexity: a survey.
- Composition limits and separating examples for some Boolean function complexity measures
- Computational Complexity
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Deterministic communication vs. partition number
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Low-sensitivity functions from unambiguous certificates
- Lower bounds on probabilistic linear decision trees
- On fractional block sensitivity
- On rank vs. communication complexity
- On the degree of Boolean functions as real polynomials
- On the sensitivity complexity of \(k\)-uniform hypergraph properties
- On the sensitivity complexity of bipartite graph properties
- On the sensitivity of cyclically-invariant Boolean functions
- Properties and applications of Boolean function composition
- Quantum Query Complexity of State Conversion
- Quantum adversary (upper) bound
- Quantum certificate complexity
- Quantum lower bounds by polynomials
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- Randomized communication versus partition number
- Reflections for quantum query algorithms
- Sensitivity vs. block sensitivity of Boolean functions
- Separations between combinatorial measures for transitive functions
- Separations in query complexity based on pointer functions
- Separations in query complexity using cheat sheets
- Strengths and Weaknesses of Quantum Computing
- Superlinear advantage for exact quantum algorithms
- Symmetries, graph properties, and quantum speedups
- The Zero-Error Randomized Query Complexity of the Pointer Function
- The critical complexity of graph properties
- Towards better separation between deterministic and randomized query complexity
- Unambiguous DNFs and Alon-Saks-Seymour
This page was built for publication: Separations between combinatorial measures for transitive functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875997)
