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

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

Omid Etesami, Amin Gohari, Salman Beigi

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of optimization problems
• Approximable sets
• Polynomial-Time Membership Comparable Sets
• Products and Help Bits in Decision Trees
• On Yao’s XOR-Lemma
• 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.
• Time bounded frequency computations
• Lower bounds for constant-depth circuits in the presence of help bits

Cited In (1)

• The cost of the missing bit: Communication complexity with help

Recommendations

• Pseudorandomness and average-case complexity via uniform reductions 👍 👎
• The cost of the missing bit: Communication complexity with help 👍 👎
• Lower bounds for constant-depth circuits in the presence of help bits 👍 👎
• Stochastic Algorithms: Foundations and Applications 👍 👎
• Complexity of Distributions and Average-Case Hardness 👍 👎
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization 👍 👎
• Strong average-case lower bounds from non-trivial derandomization 👍 👎
• Title not available (Why is that?) 👍 👎
• 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)