Pytania otagowane jako boolean-functions

Pytania o funkcje boolowskie i ich analiza

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 …
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
Pytanie o dwie matryce: Hadamard przeciwko „magicznej” w dowodzie przypuszczenia wrażliwości
Najnowszy i niezwykle zręczny dowód domniemania wrażliwości opiera się na wyraźnej * konstrukcji macierzy An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , zdefiniowanej rekurencyjnie w następujący sposób: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} oraz dla n≥2n≥2n\geq 2 , n = ( n - 1 mi n - 1 mi n - 1An=(An−1In−1In−1−An−1)An=(An−1In−1In−1−An−1)A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix} W szczególności …
4
Wybór społeczny, twierdzenie strzały i otwarte problemy?
W ostatnich miesiącach zacząłem wykładać na temat wyboru społecznego, twierdzenia strzały i powiązanych wyników. Po przeczytaniu o przełomowych wynikach zadałem sobie pytanie, co dzieje się z częściowymi preferencjami porządku, odpowiedź znajduje się w pracy Pini i in. : Agregowanie częściowo uporządkowanych preferencji: wyniki niemożliwości i możliwości . Następnie zastanawiałem się, …
1
Losowe funkcje niskiego stopnia jako prawdziwy wielomian
Czy istnieje (rozsądny) sposób na pobranie próbki losowo jednakowej funkcji boolowskiej której stopień rzeczywistej wielomianu wynosi co najwyżej ?df:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd EDYCJA: Nisan i Szegedy wykazali, że funkcja stopnia zależy od co najwyżej współrzędnych , więc możemy założyć, że . Problemy, które widzę, są następujące: 1) Z jednej strony, jeśli …
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 …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
2
Zastosowania XORification
XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla …
1
Funkcje boolowskie, w których czułość jest równa czułości bloku
Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między s(f)s(f)s(f) i bs(f)bs(f)bs(f) w celu rozstrzygnięcia przypuszczenia, że bs(f)bs(f)bs(f) jest tylko wielomianowo większy niż s(f)s(f)s(f) . Co z przeciwnym kierunkiem? Co wiadomo o funkcjach, w których s(f)=bs(f)s(f)=bs(f)s(f) = bs(f) ? Trywialnie, …
1
Jakie monotoniczne funkcje boolowskie są reprezentowane jako progi sum?
Przedstawię mój problem na przykładzie. Powiedzmy, że projektujesz egzamin, który składa się z pewnego zestawu niezależnych pytań (że kandydaci mogą mieć rację albo dobrze). Chcesz zdecydować o wyniku dla każdego pytania, z tą regułą, że kandydaci z całkowitą liczbą punktów powyżej pewnego progu przejdą, a pozostałe zawiodą.nnn W rzeczywistości jesteś …
2
O statusie zdolności uczenia się w
Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory odkryłem: Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie …
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.