scientific article; zbMATH DE number 3829252

MaRDI QIDQ3674058zbMATH OpenFDO

Authors Hans Ulrich Simon

Publication date 1983

zbMATH Keywords

lower boundparallel RAMnondegenerated function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cited in

(13)

• Pseudorandom generators for low sensitivity functions
• Size of sets with small sensitivity: a generalization of Simon's lemma
• An improved lower bound on the sensitivity complexity of graph properties
• On induced subgraphs of the cube
• Properties of complexity measures for PRAMs and WRAMs
• Rainbow coloring hardness via low sensitivity polymorphisms
• The equivalence of two problems on the cube
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• How low can approximate degree and quantum query complexity be for total Boolean functions?
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Does looking inside a circuit help?
• From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3674058)