CREW PRAM<scp>s</scp> and Decision Trees
From MaRDI portal
Publication:3985804
Recommendations
Cited in
(59)- The critical complexity of all (monotone) boolean functions and monotone graph properties
- Conflict complexity is lower bounded by block sensitivity
- Separating the power of EREW and CREW PRAMs with small communication width
- Certificate complexity and symmetry of nested canalizing functions
- Equality alone does not simulate randomness
- On the resolution of the sensitivity conjecture
- Size of sets with small sensitivity: a generalization of Simon's lemma
- Composition limits and separating examples for some Boolean function complexity measures
- Dimension-free bounds and structural results in communication complexity
- On the parity complexity measures of Boolean functions
- An improved lower bound on the sensitivity complexity of graph properties
- Arthur-Merlin games in Boolean decision trees
- A tighter relation between sensitivity complexity and certificate complexity
- Gossiping and broadcasting versus computing functions in networks.
- On separating the EREW and CREW PRAM models
- Sensitivity versus block sensitivity of Boolean functions
- Block sensitivity of minterm-transitive functions
- scientific article; zbMATH DE number 107961 (Why is no real title available?)
- Pseudo-average block sensitivity equals average sensitivity
- Properties of complexity measures for PRAMs and WRAMs
- Rainbow coloring hardness via low sensitivity polymorphisms
- The equivalence of two problems on the cube
- Helping by unambiguous computation and probabilistic computation
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Computing Boolean functions from multiple faulty copies of input bits
- Maximal sensitivity of Boolean nested canalizing functions
- On the (im)possibility of time-lock puzzles in the quantum random oracle model
- Sensitivity vs. block sensitivity (an average-case study)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Quantum certificate complexity
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- A note on the polynomial representation of Boolean functions over \(\mathrm{GF}(2)\)
- On the elusiveness of Hamiltonian property
- Sensitivities and block sensitivities of elementary symmetric Boolean functions
- Laced Boolean functions and subset sum problems in finite fields
- Low-sensitivity functions from unambiguous certificates
- On the P versus NP intersected with co-NP question in communication complexity
- Cutting planes width and the complexity of graph isomorphism refutations
- Minterm-transitive functions with asymptotically smallest block sensitivity
- Quantum query complexity of almost all functions with fixed on-set size
- New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
- Block sensitivity of weakly symmetric functions
- Improved direct product theorems for randomized query complexity
- Does looking inside a circuit help?
- Randomized versus deterministic decision tree size
- Collectively canalizing Boolean functions
- Quantum lower bounds by quantum arguments
- On the decisional complexity of problems over the reals
- Complexity measures and decision tree complexity: a survey.
- Extended learning graphs for triangle finding
- scientific article; zbMATH DE number 1369845 (Why is no real title available?)
- Separation between deterministic and randomized query complexity
- On read-once threshold formulae and their randomized decision tree complexity
- Certificate complexity of elementary symmetric Boolean functions
- scientific article; zbMATH DE number 4003532 (Why is no real title available?)
- Separating the power of EREW and CREW PRAMs with small communication width
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
This page was built for publication: CREW PRAM<scp>s</scp> and Decision Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3985804)
