A tighter relation between sensitivity complexity and certificate complexity
From MaRDI portal
Publication:5915958
DOI10.1016/j.tcs.2018.08.025zbMath1418.68103arXiv1609.04342OpenAlexW2889257031WikidataQ129318015 ScholiaQ129318015MaRDI QIDQ5915958
Publication date: 28 February 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.04342
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The critical complexity of graph properties
- On the degree of Boolean functions as real polynomials
- Complexity measures and decision tree complexity: a survey.
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- Smooth Boolean Functions are Easy
- A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
- Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
- A New Approach to the Sensitivity Conjecture
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- CREW PRAM<scp>s</scp> and Decision Trees
- On the Sensitivity Conjecture
- On the Sensitivity Conjecture for Disjunctive Normal Forms
- On the Sensitivity Complexity of k-Uniform Hypergraph Properties
- Low-Sensitivity Functions from Unambiguous Certificates.
- Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
- Tighter Relations between Sensitivity and Other Complexity Measures
- Sensitivity Versus Certificate Complexity of Boolean Functions
This page was built for publication: A tighter relation between sensitivity complexity and certificate complexity
