The value of help bits in randomized and average-case complexity

DOI10.1007/S00037-016-0135-XMaRDI QIDQ2012180zbMATH OpenOpenAlexFDO

Authors Salman Beigi, Omid Etesami, Amin Gohari

Publication date 28 July 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0499

zbMATH Keywords

entropyaverage-case complexityrandomized computationrate-distortionhelp bits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: "Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity. Amir, Beigel, and Gasarch (1990) show that for constant $k$, if $k$ instances of a decision problem can be efficiently solved using less than $k$ bits of help, then the problem is in P/poly. We extend this result to the setting of randomized computation: We show that the decision problem is in P/poly if using $ell$ help bits, $k$ instances of the problem can be efficiently solved with probability greater than $2^{ell-k}$. The same result holds if using less than $k(1-h(alpha))$ help bits (where $h(cdot)$ is the binary entropy function), we can efficiently solve $(1-alpha)$ fraction of the instances correctly with non-vanishing probability. We also extend these two results to non-constant but logarithmic $k$. In this case however, instead of showing that the problem is in P/poly we show that it satisfies "$k$-membership comparability," a notion known to be related to solving $k$ instances using less than $k$ bits of help. Next we consider the setting of average-case complexity: Assume that we can solve $k$ instances of a decision problem using some help bits whose entropy is less than $k$ when the $k$ instances are drawn independently from a particular distribution. Then we can efficiently solve an instance drawn from that distribution with probability better than $1/2$. Finally, we show that in the case where $k$ is super-logarithmic, assuming $k$-membership comparability of a decision problem, one cannot prove that the problem is in P/poly by a "black-box proof."

Recommendations

• Lower bounds for constant-depth circuits in the presence of help bits
• The cost of the missing bit: Communication complexity with help
• scientific article; zbMATH DE number 1775457
• Pseudorandomness and average-case complexity via uniform reductions
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• scientific article; zbMATH DE number 1775407
• Complexity of distributions and average-case hardness
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 1180007
• Strong average-case lower bounds from non-trivial derandomization

Cites work

• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1335874 (Why is no real title available?)
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• Approximable sets
• Enumerative counting is hard
• Hardness amplification within NP
• Lower bounds for constant-depth circuits in the presence of help bits
• On Yao's XOR-lemma
• On the reducibility of sets inside NP to sets with low information content
• Polynomial-Time Membership Comparable Sets
• Products and Help Bits in Decision Trees
• Some connections between bounded query classes and non-uniform complexity.
• The complexity of optimization problems
• Time bounded frequency computations
• Using Nondeterminism to Amplify Hardness

Cited in

(3)

• The cost of the missing bit: Communication complexity with help
• scientific article; zbMATH DE number 1834644 (Why is no real title available?)
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)

This page was built for publication: The value of help bits in randomized and average-case complexity

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