Our proof of lem:hardness-amplification combines existing XOR lemmas for distributional query complexity [1]}, [2]}, [3]}. Specifically, we first use one due to Brody, Kim, Lerdputtipongporn, and Srinivasulu [3]} to amplify from \(= O(\frac{1}{n})\)  to \(\Theta (1)\) , and then one due to Drucker [1]} to amplify from \(\Theta (1)\)  to exponentially close to \(\frac{1}{2}\) . The quantitative parameters of these lemmas are incomparable, and we show how they can be applied in tandem in our setting.

Наше доказательство леммы "увеличение сложности" объединяет существующие леммы XOR для распределительной сложности запросов [1], [2], [3]. Конкретно, мы сначала используем лемму Brody, Kim, Lerdputtipongporn и Srinivasulu [3], чтобы увеличить от \(= O(\frac{1}{n})\) до \(\Theta (1)\), а затем лемму Drucker [1], чтобы увеличить от \(\Theta (1)\) до экспоненциально близкого к \(\frac{1}{2}\). Количественные параметры этих лемм нельзя сравнивать, и мы показываем, как их можно применять совместно в нашей ситуации.