Czy nastąpił jakiś postęp w zaostrzaniu wykładnika, w wyniku którego niezależność ?

Braverman wykazały, że rozkład które -wise niezależnie -fool głębokość obwody wielkości o "sklejanie" The Smolensky aproksymacja i aproksymacja Fouriera funkcji logicznych . Autor i ci, którzy przypuszczali, że to pierwotnie przypuszczają, że wykładnik tam można zredukować do$(log \frac{m}{\epsilon})^{O(d^2)}$$\epsilon$$d$ $AC^0$$m$$AC^0$$O(d)$i jestem ciekawy, czy poczyniono postępy w tym kierunku, ponieważ wyobrażam sobie, że wiązałoby się to z wytworzeniem wielomianu, który jest bliski odległości korelacji, a także z faktyczną zgodnością z funkcją na dużej liczbie danych wejściowych, i myślę, że tak być bardzo interesującym przybliżeniem do znalezienia bez sklejenia tych dwóch razem. Czy jest jakiś powód, by oczekiwać, że takie przybliżenie musi mieć stopień który nie był znany, kiedy Braverman napisał swój artykuł w 2010 roku?$O(d^2)$

Innym pytaniem dotyczącym tego artykułu jest to, że oryginalna hipoteza przypomina zależność Boppany od wrażliwości, chociaż była zawarta w dokumencie napisanym przed tym ograniczeniem. To oczywiście nie jest przypadek, ponieważ ta granica odpowiadałaby koncentracji Fouriera, którą można wyprowadzić z granicy Boppany, jeśli wielomian Fouriera działał, ale czy istnieje jakaś lepsza intuicja, o której wiesz, że „jeśli zadziałałby wielomian Fouriera , to właśnie dostaniesz „jeden”?

W swoim artykule CCC'17 [1] Avishay Tal poprawił ograniczenie do Możesz zajrzeć na str. 15: 4 w celu przeprowadzenia dyskusji. Odnosi się także do (patrz przypis 30 do dokumentu Harsha i Srinivasan , który poprawia (1)) i odpowiada przypuszczeniu Tala: -niezależny, dla wystarcza do -fool size- głębokość- obwody AC0.

$$\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}$$ $k$ $$k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2}$$ $\varepsilon$$m$$d$

---

[1] Tight Bounds na spektrum Fouriera$\mathsf{AC}_0$ , A. Tal. CCC'17.

[2] O przybliżeniach wielomianowych do$\mathsf{AC}_0$ , P. Harsha i S. Srinivasan. RANDOM 2016,