Average-case deterministic query complexity of Boolean functions with fixed weight

DOI10.1007/978-981-95-0215-8_15MaRDI QIDQ6867277zbMATH OpenFDO

Authors Yuan Li, Haowei Wu, Yi Yang

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0215-8_15

zbMATH Keywords

average-case query complexitycriticalitydecision treeswitching lemmaweight

Mathematics Subject Classification ID

Boolean functions (94D10)

Cites work

• Analysis of Boolean Functions
• Average-case quantum query complexity
• Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
• Complexity measures and decision tree complexity: a survey.
• Critical exponents for two-dimensional percolation
• Criticality of AC^0-formulae
• Criticality of regular formulas
• Decision trees and influence: an inductive proof of the OSSS inequality
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the Correlation of Parity and Small-Depth Circuits
• Quantum query complexity of almost all functions with fixed on-set size
• Random-Turn Hex and Other Selection Games
• Separations in query complexity using cheat sheets
• The influence lower bound via query elimination
• The monotone complexity of \(k\)-clique on random graphs

This page was built for publication: Average-case deterministic query complexity of Boolean functions with fixed weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6867277)