Przybliżony stopień

EDYCJA (v2): Dodano sekcję na końcu tego, co wiem o problemie.

EDYCJA (v3): Dodano dyskusję na temat stopnia progowego na końcu.

Pytanie

To pytanie jest głównie prośbą o referencję. Nie wiem dużo o tym problemie. Chcę wiedzieć, czy wcześniej pracowano nad tym problemem, a jeśli tak, to czy ktoś może wskazać mi jakieś dokumenty, które mówią o tym problemie? Chciałbym również poznać obecne najlepsze granice przybliżonego stopnia . Wszelkie inne informacje byłyby również mile widziane (np. Informacje historyczne, motywacja, związek z innymi problemami itp.). $\textrm{AC}^0$

Definicje

Niech będzie funkcją logiczną. Niech będzie wielomianem nad zmiennymi do z rzeczywistymi współczynnikami. Stopień wielomianu jest maksymalnym stopniem we wszystkich monomialach. Stopień monomialu jest sumą wykładników różnych które pojawiają się w tym monomialu. Na przykład . $f:\{0,1\}^n \to \{0,1\}$ $p$ $x_1$ $x_n$ $x_i$ $\textrm{deg}(x_1^7x_3^2) = 9$

O wielomianie mówi się, że przybliżone jeśli dla wszystkich . -approximate stopień logiczna funkcja , oznaczoną jako , to stopień najmniej wielomianem że -approximates . Dla zestawu funkcji , jest minimalnym stopniem tak że każda funkcja w może być - aproksymowana przez wielomian stopnia co najwyżej $p$ $\epsilon$ $f$ $|f(x)-p(x)|<\epsilon$ $x$ $\epsilon$ $f$ $\widetilde{\textrm{deg}}_{\epsilon}(f)$ $\epsilon$ $f$ $F$ $\widetilde{\textrm{deg}}_{\epsilon}(F)$ $d$ $F$ $\epsilon$ $d$ .

Zauważ, że każda funkcja może być reprezentowana bezbłędnie przez wielomian stopnia . Niektóre funkcje naprawdę wymagają wielomianu stopnia do przybliżenia dowolnego stałego błędu. Parzystość jest przykładem takiej funkcji. $n$ $n$

Opis problemu

Co to jest ? (Stała 1/3 jest dowolna.) $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$

Notatki

Problem ten spotkałem w artykule Kwantowa złożoność kwerendy AC0 autorstwa Paula Beame'a i Widada Machmouchiego. Mówią

Ponadto nasze wyniki nie robią nic, aby zamknąć lukę w dolnej granicy przybliżonego stopnia funkcji AC0.

W swoich podziękowaniach wspominają również „problem przybliżonego stopnia AC0”.

Więc zakładam, że wcześniej było trochę pracy nad tym problemem? Czy ktoś może wskazać mi artykuł, który mówi o problemie? A jakie są najbardziej znane górne i dolne granice?

Co wiem o problemie (ta sekcja została dodana w v2 pytania)

Najbardziej znaną górną granicą która jest znana, to trywialna górna granica . Najlepsza dolna granica, jaką znam, pochodzi z dolnej granicy Aaronsona i Shi dla problemów kolizji i różnicowania elementów, co daje dolną granicę . (W przypadku poważnie ograniczonych wersji , takich jak formuły rozmiarze formuły lub obwody głębokości-2 z bramkami , możemy udowodnić górną granicę używając kwantowej złożoności zapytań). $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$ $n$ $\tilde{\Omega}(n^{2/3})$ $\textrm{AC}^0$ $o(n^2)$ $o(n^2)$ $o(n)$

Powiązane: stopień progowy (Dodano w v3)

Jak zauważa Tsuyoshi w komentarzach, problem ten związany jest z problemem określania progowego stopnia . Stopień progowy funkcji jest minimalnym stopniem wielomianu tak że a . $\textrm{AC}^0$ $f$ $p$ $f(x)=1 \implies p(x)>0$ $f(x)=0 \implies p(x)<0$

Dolne granice dla progowego stopnia zostały teraz poprawione przez Sherstova. Pokazuje rodzinę formuł o stałej głębokości do jednorazowego odczytu na zmiennych, których stopień progowy zbliża się do gdy głębokość zbliża się do nieskończoności, co jest prawie ciasne, ponieważ formuły raz do odczytu mają próg (a nawet przybliżone ) stopień . Zobacz http://eccc.hpi-web.de/report/2014/009/ . (Sty 2014) $\mathrm{AC}^0$ $n$ $\Omega(\sqrt{n})$ $O(\sqrt{n})$

— Robin Kothari
źródło

Dolna granica Ω (n ^ (1/3)) jest znana nawet dla stopnia progowego (minimalny stopień wielomianu p taki, że f (x) = 1 ⇒ p (x)> 0 oraz f (x) = 0 ⇒ p (x) <0). Patrz koniec sekcji 3.1 „Dolne granice komunikacji za pomocą podwójnych wielomianów” autorstwa Sherstova .

— Tsuyoshi Ito

@Tsuyoshi: Dzięki. Ciekawym pytaniem jest również stopień progowy (który dolna granica przybliżonego stopnia) AC0. Najlepsze dolne granice, jakie znam dla progowego stopnia AC0, to Granice nowego stopnia dla wielomianowych funkcji progowych autorstwa O'Donnella i Servedio. Dolna granica jest lepsza niż Ω (n ^ (1/3)) o współczynnik logarytmiczny, który rośnie wraz z głębokością obwodu.

— Robin Kothari,

Ups, masz rację, dolna granica stopnia przybliżenia dla AC0 jest oczywista z Aaronsona i Shi. Głupi ja. Dzięki za wskaźnik do O'Donnell i Servedio.

\tilde{Ω} (n^{2 / 3})

$\tilde{\Omega}(n^{2/3})$

— Tsuyoshi Ito

Niedawny artykuł Mark Bun i Justina Thalera zatytułowany „Wzmocnienie twardości i przybliżony stopień obwodów o stałej głębokości” również krótko omawia ten problem. Mówią, że dolna granica Aaronsona i Shi jest najlepiej znaną dolną granicą dla funkcji w AC <sup> 0 </sup> i że dolna granica ma nawet nieco bardziej ogólny model.

— Robin Kothari

Artykuł autorstwa Marka Bun i Justina Thalera został opublikowany w ECCC bardzo niedawno (w połowie marca 2017 r.), Który precyzyjnie odpowiada na to pytanie: „Prawie optymalna dolna granica dla przybliżonego stopnia AC0”

Twierdzą, że dla dowolnego istnieje funkcja w taka, że , prawie zamykając lukę z trywialną górną granicą . Osiągają to za pomocą ogólnej metody zwiększenia przybliżonego stopnia funkcji o przybliżonym stopniu sublinearnym, utrzymując liczbę zmiennych quasi-liniowych. Z streszczenia: $\delta > 0$ $f$ $\mathrm{AC}^0$ $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$ $O(n)$

W szczególności pokazujemy, jak przekształcić dowolną funkcję boolowską o przybliżonym stopniu w funkcję na zmiennych o przybliżonym stopniu co najmniej . W szczególności, jeśli , to jest wielomianowo większe niż . Ponadto, jeśli jest obliczany przez wielomian wielkości logicznego obwodu stałej głębokości, a więc jest . $f$ $d$ $F$ $O(n \cdot \mathrm{polylog}(n))$ $D = Ω(n^{1/3} · d^{2/3} )$ $d = n^{1−Ω(1)}$ $D$ $d$ $f$ $F$

Jest to najnowsza aktualizacja w dolnej części tego problemu i jest to znaczący krok naprzód. Sekcje wprowadzenia i zastosowania są również dobrym źródłem informacji na temat wcześniejszych prac i powiązanych problemów.

Oświadczenie: Nie przeczytałem jeszcze dokładnie artykułu.

— NA
źródło

Rzeczywiście, to prawie zamyka problem. Pokazują także DNF wielkości quasipolynomial z przybliżonym stopniem .

Ω (n^{1 - δ})

$\Omega(n^{1-\delta})$

— Robin Kothari,