A tighter relation between sensitivity complexity and certificate complexity (Q5915958): Difference between revisions

@@ Property / DOI @@
-.1016/j.tcs.2018.08.025
@@ Property / DOI: 10.1016/j.tcs.2018.08.025 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W2889257031
@@ Property / OpenAlex ID: W2889257031 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04342
@@ Property / arXiv ID: 1609.04342 / rank @@
+Normal rank
@@ Property / cites work @@
+Tighter Relations between Sensitivity and Other Complexity Measures
+Normal rank
@@ Property / cites work @@
+A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
+Normal rank
@@ Property / cites work @@
+Sensitivity Versus Certificate Complexity of Boolean Functions
+Normal rank
@@ Property / cites work @@
+Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
+Normal rank
@@ Property / cites work @@
+Q4608575
@@ Property / cites work: Q4608575 / rank @@
+Normal rank
@@ Property / cites work @@
+Low-Sensitivity Functions from Unambiguous Certificates.
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
+Normal rank
@@ Property / cites work @@
+A New Approach to the Sensitivity Conjecture
@@ Property / cites work: A New Approach to the Sensitivity Conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Smooth Boolean Functions are Easy
@@ Property / cites work: Smooth Boolean Functions are Easy / rank @@
+Normal rank
@@ Property / cites work @@
+Q5368747
@@ Property / cites work: Q5368747 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Sensitivity Conjecture for Disjunctive Normal Forms
+Normal rank
@@ Property / cites work @@
+Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
+Normal rank
@@ Property / cites work @@
+On the Sensitivity Complexity of k-Uniform Hypergraph Properties
+Normal rank
@@ Property / cites work @@
+Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
+Normal rank
@@ Property / cites work @@
+Q4608008
@@ Property / cites work: Q4608008 / rank @@
+Normal rank
@@ Property / cites work @@
+CREW PRAM<scp>s</scp> and Decision Trees
@@ Property / cites work: CREW PRAM<scp>s</scp> and Decision Trees / rank @@
+Normal rank
@@ Property / cites work @@
+On the degree of Boolean functions as real polynomials
+Normal rank
@@ Property / cites work @@
+On the Sensitivity Conjecture
@@ Property / cites work: On the Sensitivity Conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+The critical complexity of graph properties
@@ Property / cites work: The critical complexity of graph properties / rank @@
+Normal rank
@@ Property / cites work @@
+Q5781249
@@ Property / cites work: Q5781249 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q129318015
@@ Property / Wikidata QID: Q129318015 / rank @@
+Normal rank
@@ Property / DOI @@
+.1016/J.TCS.2018.08.025
@@ Property / DOI: 10.1016/J.TCS.2018.08.025 / rank @@
+Normal rank