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

DOI10.1007/S00037-016-0135-XzbMATH Open1371.68102arXiv1408.0499OpenAlexW3105100487MaRDI QIDQ2012180FDOQ2012180

Authors: Salman Beigi, Omid Etesami, Amin Gohari 

Publication date: 28 July 2017

Published in: Computational Complexity (Search for Journal in Brave)

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."

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

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

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)

Cites Work

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

Cited In (3)

• The cost of the missing bit: Communication complexity with help
• Title not available (Why is that?)
• Title not available (Why is that?)

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)