Unambiguous Parity‐Query Complexity
Copyright policy )Unambiguous Parity‐Query Complexity
ABSTRACTWe give a lower bound of on the unambiguous randomized parity‐query complexity of the approximate majority problem—that is, on the lowest randomized parity‐query complexity of any function over whose value is “” if the Hamming weight of the input is at most , is “” if the weight is at least , and may be arbitrary otherwise.
- Institute of Mathematics Czech Republic
- Czech Academy of Sciences Czech Republic
- Academy of Sciences Library Czech Republic
FOS: Computer and information sciences, Computer Science - Computational Complexity, unambiguous complexity, parity queries, query complexity, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Communication complexity, information complexity, Computational Complexity (cs.CC)
FOS: Computer and information sciences, Computer Science - Computational Complexity, unambiguous complexity, parity queries, query complexity, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Communication complexity, information complexity, Computational Complexity (cs.CC)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!