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

DOI10.1007/s00037-016-0135-xzbMath1371.68102arXiv1408.0499OpenAlexW3105100487MaRDI QIDQ2012180

Omid Etesami, Amin Gohari, Salman Beigi

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

entropyrandomized computationaverage-case complexityrate-distortionhelp bits

Mathematics Subject Classification ID

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

Cites Work

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

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