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