Pages that link to "Item:Q3985804"

The following pages link to CREW PRAM<scp>s</scp> and Decision Trees (Q3985804):

Displaying 44 items.

• Pseudo-average block sensitivity equals average sensitivity (Q293418) (← links)
• Quantum query complexity of almost all functions with fixed on-set size (Q347109) (← links)
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma (Q451107) (← links)
• An improved lower bound on the sensitivity complexity of graph properties (Q551172) (← links)
• Computing Boolean functions from multiple faulty copies of input bits (Q596147) (← links)
• Sensitivity vs. block sensitivity (an average-case study) (Q671409) (← links)
• Helping by unambiguous computation and probabilistic computation (Q675865) (← links)
• Improved direct product theorems for randomized query complexity (Q693002) (← links)
• Block sensitivity of minterm-transitive functions (Q719324) (← links)
• On the parity complexity measures of Boolean functions (Q974756) (← links)
• On the P versus NP intersected with co-NP question in communication complexity (Q1044738) (← links)
• The equivalence of two problems on the cube (Q1194759) (← links)
• On read-once threshold formulae and their randomized decision tree complexity (Q1208407) (← links)
• Exact lower time bounds for computing Boolean functions on CREW PRAMs (Q1329159) (← links)
• Separating the power of EREW and CREW PRAMs with small communication width (Q1373140) (← links)
• Gossiping and broadcasting versus computing functions in networks. (Q1427193) (← links)
• Composition limits and separating examples for some Boolean function complexity measures (Q1701350) (← links)
• Complexity measures and decision tree complexity: a survey. (Q1853508) (← links)
• On the decisional complexity of problems over the reals (Q1854429) (← links)
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions (Q1887146) (← links)
• Minterm-transitive functions with asymptotically smallest block sensitivity (Q1944206) (← links)
• Sensitivity versus block sensitivity of Boolean functions (Q1944916) (← links)
• Arthur-Merlin games in Boolean decision trees (Q1961380) (← links)
• Nondeterministic and randomized Boolean hierarchies in communication complexity (Q2041245) (← links)
• Sensitivities and block sensitivities of elementary symmetric Boolean functions (Q2048184) (← links)
• Certificate complexity of elementary symmetric Boolean functions (Q2089681) (← links)
• Conflict complexity is lower bounded by block sensitivity (Q2219069) (← links)
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
• Maximal sensitivity of Boolean nested canalizing functions (Q2272408) (← links)
• Laced Boolean functions and subset sum problems in finite fields (Q2275906) (← links)
• Extended learning graphs for triangle finding (Q2300731) (← links)
• Block sensitivity of weakly symmetric functions (Q2382286) (← links)
• Optimal parallel quantum query algorithms (Q2408924) (← links)
• Quantum certificate complexity (Q2475404) (← links)
• Alternation, sparsity and sensitivity: bounds and exponential gaps (Q2632012) (← links)
• Collectively canalizing Boolean functions (Q2687272) (← links)
• Dimension-free bounds and structural results in communication complexity (Q2698435) (← links)
• Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma (Q2948459) (← links)
• Low-Sensitivity Functions from Unambiguous Certificates. (Q4638078) (← links)
• Certificate complexity and symmetry of nested canalizing functions (Q5024675) (← links)
• New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity (Q5090948) (← links)
• Equality alone does not simulate randomness (Q5091765) (← links)
• Does Looking Inside a Circuit Help (Q5111215) (← links)
• On the resolution of the sensitivity conjecture (Q5123060) (← links)