Low-sensitivity functions from unambiguous certificates

DOI10.4230/LIPICS.ITCS.2017.28MaRDI QIDQ4638078zbMATH OpenOpenAlexFDO

Authors Shalev Ben-David, Pooya Hatami, Avishay Tal

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1605.07084

zbMATH Keywords

Boolean functionsdecision tree complexityquery complexitysensitivity conjecture

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25)

Abstract: We provide new query complexity separations against sensitivity for total Boolean functions: a power $3$ separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power $2.22$ separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity ($U{C}_{min}$). We also show that $U{C}_{min}$ is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between $bs(f)$ and $s(f)$. We also provide a quadratic separation between the tree-sensitivity and decision tree complexity of Boolean functions, disproving a conjecture of Gopalan, Servedio, Tal, and Wigderson (CCC 2016). Along the way, we give a power $1.22$ separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power $1.128$ separation due to G"o"os (FOCS 2015). As a consequence, we obtain an improved $Omega(lo{g}^{1.22}n)$ lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.

Recommendations

• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• Sensitivity versus certificate complexity of Boolean functions
• A tighter relation between sensitivity complexity and certificate complexity
• A tighter relation between sensitivity complexity and certificate complexity

Cites work

• A composition theorem for the Fourier entropy-influence conjecture
• A New Approach to the Sensitivity Conjecture
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• Automata, Languages and Programming
• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• Deterministic communication vs. partition number
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 4130025 (Why is no real title available?)
• scientific article; zbMATH DE number 2019628 (Why is no real title available?)
• scientific article; zbMATH DE number 6789278 (Why is no real title available?)
• Making polynomials robust to noise
• Nearly optimal separations between communication (or query) complexity and partitions
• On fractional block sensitivity
• On the degree of Boolean functions as real polynomials
• On the sensitivity conjecture
• Polynomial degree vs. quantum query complexity
• Properties and applications of Boolean function composition
• Quantum certificate complexity
• Quantum lower bounds by polynomials
• Quantum Query Complexity of State Conversion
• Randomized communication versus partition number
• Randomized query complexity of sabotaged and composed functions
• Rectangles Are Nonnegative Juntas
• Reflections for quantum query algorithms
• Separating decision tree complexity from subcube partition complexity
• Separations in query complexity using cheat sheets
• Size of sets with small sensitivity: a generalization of Simon's lemma
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• SOFSEM 2006: Theory and Practice of Computer Science
• Tighter relations between sensitivity and other complexity measures
• Upper bounds on Fourier entropy

Cited in

(8)

• On the binary and Boolean rank of regular matrices
• On version space compression
• Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• A tighter relation between sensitivity complexity and certificate complexity
• Separations between combinatorial measures for transitive functions
• Approximate degree composition for recursive functions
• Multiclass learnability does not imply sample compression

This page was built for publication: Low-sensitivity functions from unambiguous certificates

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