CREW PRAM<scp>s</scp> and Decision Trees
From MaRDI portal
Publication:3985804
DOI10.1137/0220062zbMATH Open0737.68028OpenAlexW1867758558MaRDI QIDQ3985804FDOQ3985804
Authors: Noam Nisan 
Publication date: 27 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220062
Recommendations
Cited In (61)
- On the (im)possibility of time-lock puzzles in the quantum random oracle model
- A note on the polynomial representation of Boolean functions over \(\mathrm{GF}(2)\)
- Sensitivity, affine transforms and quantum communication complexity
- Cutting planes width and the complexity of graph isomorphism refutations
- Randomized versus deterministic decision tree size
- 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
- Optimal parallel quantum query algorithms
- Arthur-Merlin games in Boolean decision trees
- An improved lower bound on the sensitivity complexity of graph properties
- 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
- Title not available (Why is that?)
- Rainbow coloring hardness via low sensitivity polymorphisms
- Block sensitivity of minterm-transitive functions
- Pseudo-average block sensitivity equals average sensitivity
- Properties of complexity measures for PRAMs and WRAMs
- The equivalence of two problems on the cube
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Helping by unambiguous computation and probabilistic computation
- Maximal sensitivity of Boolean nested canalizing functions
- Computing Boolean functions from multiple faulty copies of input bits
- 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
- On the elusiveness of Hamiltonian property
- Low-sensitivity functions from unambiguous certificates
- Sensitivities and block sensitivities of elementary symmetric Boolean functions
- Laced Boolean functions and subset sum problems in finite fields
- On the P versus NP intersected with co-NP question in communication complexity
- New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
- Minterm-transitive functions with asymptotically smallest block sensitivity
- Block sensitivity of weakly symmetric functions
- Quantum query complexity of almost all functions with fixed on-set size
- Improved direct product theorems for randomized query complexity
- Does looking inside a circuit help?
- Quantum lower bounds by quantum arguments
- Collectively canalizing Boolean functions
- Title not available (Why is that?)
- On the decisional complexity of problems over the reals
- Extended learning graphs for triangle finding
- Complexity measures and decision tree complexity: a survey.
- Separation between deterministic and randomized query complexity
- On read-once threshold formulae and their randomized decision tree complexity
- Title not available (Why is that?)
- Certificate complexity of elementary symmetric Boolean functions
- Separating the power of EREW and CREW PRAMs with small communication width
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- The critical complexity of all (monotone) boolean functions and monotone graph properties
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)
