Pytania otagowane jako fourier-analysis

3
Dlaczego analiza Fouriera funkcji boolowskich „działa”?
Przez lata przyzwyczaiłem się do tego, że wiele twierdzeń TCS zostało udowodnionych przy użyciu dyskretnej analizy Fouriera. Transformacja Walsha-Fouriera (Hadamarda) jest przydatna w praktycznie każdym podpolu TCS, w tym w testowaniu właściwości, pseudolosowości, złożoności komunikacji i obliczeniach kwantowych. Podczas gdy czułem się dobrze, stosując analizę Fouriera funkcji boolowskich jako bardzo …
12
Zastosowania teorii reprezentacji grupy symetrycznej
Zainspirowany tym pytaniem, a w szczególności ostatnim akapitem odpowiedzi Or, mam następujące pytanie: Czy znasz jakieś zastosowania teorii reprezentacji grupy symetrycznej w TCS? Grupa symetryczna SnSnS_n jest grupą wszystkich permutacji {1,…,n}{1,…,n}\{1, \ldots, n\} o składzie operacji grupowych. Przedstawienie SnSnS_n jest homomorfizmem z SnSnS_n ogólnej grupy liniowego odwracalnych n×nn×nn \times n …
1
Współczynniki Fouriera Funkcje boolowskie opisane przez obwody o ograniczonej głębokości z bramkami AND OR i XOR
Niech faff będzie funkcją boolowską i pomyślmy o f jako funkcji od {−1,1}n{−1,1}n\{-1,1\}^n do {−1,1}{−1,1}\{ -1,1 \} . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te 2n2n2^n monomialów stanowią podstawę dla przestrzeni funkcji rzeczywistych na {−1,1}n{−1,1}n\{-1,1\}^n . Suma kwadratów współczynników wynosi …
2
Jaka jest złożoność odróżnienia prawdziwego widma Fouriera od fałszywego?
PHPHPH urządzenie ma dostęp oracle losowej logicznej funkcji f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} , a dwa Fouriera widma ggg i hhh . Widma Fouriera funkcji fff są zdefiniowane jako F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R : F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x) Jedno z ggg lub hhh to prawdziwe …
2
Liniowo niezależne współczynniki Fouriera
Podstawową właściwością przestrzeni wektorowych jest to, że przestrzeń wektorowa V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n o wymiarze n−dn−dn-d można scharakteryzować ddd liniowo niezależnymi wiązaniami liniowymi - to znaczy istnieją ddd liniowo niezależne wektory w1,…,wd∈Fn2w1,…,wd∈F2nw_1, \ldots, w_d \in \mathbb{F}_2^n , które są prostopadłe do VVV . Z punktu widzenia Fouriera jest to równoważne ze …
2
Rozszerzenie operatora hałasu
W przypadku problemu, nad którym obecnie pracuję, naturalnie pojawia się rozszerzenie operatora hałasu i byłem ciekawy, czy były wcześniejsze prace. Najpierw pozwól mi zrewidować podstawowy operator hałasu na funkcjach boolowskich o wartościach rzeczywistych. Biorąc pod uwagę funkcję i , st , \ varepsilon = 1 - 2p , definiujemy T …
1
Czy można udowodnić za pomocą twierdzenia Linial-Mansour-Nisan i znajomości czteroczęściowego spektrum ?
Wynik 1: Twierdzenie Linial-Mansour-Nisan mówi, że czteroliniowa waga funkcji obliczonych przez obwody jest skoncentrowana na podzbiorach małych rozmiarów z dużym prawdopodobieństwem.AC0AC0\mathsf{AC}^0 Wynik 2: ma czterokierunkową wagę skoncentrowaną na współczynniku stopnia .PARITYPARITY\mathsf{PARITY}nnn Pytanie: Czy istnieje sposób, aby udowodnić (jeśli można udowodnić), że nie jest obliczalny przez obwody przez / przy użyciu …
1
Najlepsza złożoność zapytań algorytmu uczenia się Goldreich-Levin / Kushilevitz-Mansour
Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!O ( 1 / ϵ4n logn )O(1/ϵ4nlog⁡n)O(1/\epsilon^4 n \log n)nnn …
1
Górna granica stopnia funkcji boolowskiej pod względem jej czułości
Bardzo interesującym otwartym problemem w badaniu miar złożoności funkcji boolowskiej jest tak zwana hipoteza wrażliwości vs. blokowa. Informacje na temat wrażliwości kontra czułości bloków można znaleźć na następującym blogu S. Aaronsona na stronie http://www.scottaaronson.com/blog/?p=453 . Według mojej najlepszej wiedzy, najlepszą górną granicą znaną na w kategoriach s ( f ) …
1
Czy ten polytop „podgrupy” jest integralny?
Niech będzie skończoną grupą abelową, i niech będzie polytopem w zdefiniowanym jako punkty spełniające następujące nierówności:P R Γ xΓΓ\GammaP.PPRΓRΓ\mathbb{R}^\Gammaxxx ∑sol∈ G.xsol≤ | G |xsol≥ 0∀ G ≤ Γ∀ g∈ Γ∑g∈Gxg≤|G|∀G≤Γxg≥0∀g∈Γ\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\ x_g \ge 0 & \forall g \in \Gamma \end{array} …
1
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( l o gmϵ)O (re2))(losolmϵ)O(re2))(log \frac{m}{\epsilon})^{O(d^2)}ϵϵ\epsilonrered ZAdo0ZAdo0AC^0mmmZAdo0ZAdo0AC^0O ( d)O(re)O(d)i jestem ciekawy, czy poczyniono postępy …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.