Hardness Amplification Proofs Require Majority
From MaRDI portal
Publication:5390590
DOI10.1137/080735096zbMath1214.68175OpenAlexW2027665018MaRDI QIDQ5390590
Emanuele Viola, Ronen Shaltiel
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.6716
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Lower bound on SNARGs in the random oracle model ⋮ Query complexity in errorless hardness amplification ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Randomness buys depth for approximate counting ⋮ The communication complexity of addition ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Natural Proofs versus Derandomization ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Query Complexity in Errorless Hardness Amplification ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Advice Lower Bounds for the Dense Model Theorem
