Pytania otagowane jako boolean-functions

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 …

16 boolean-functions  fourier-analysis 

Mówimy, że funkcja boolowska f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} jest k-kk junta, jeśli fff ma co najwyżej kkk zmiennych wpływających. Niech f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} …

16 co.combinatorics  boolean-functions  fourier-analysis  property-testing 

Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do zmiennych.x1,…,xnx1,…,xnx_1,\dots,x_n∧∧\wedge∨∨\veee1≡e2e1≡e2e_1 …

16 cc.complexity-theory  time-complexity  boolean-functions  monotone 

W artykule „ Naturalne dowody” Razborova-Rudicha , strona 6, w części, w której dyskutują, że istnieją „silne dowody dolnej granicy na modele obwodów monotonicznych ” i to, jak pasują do zdjęcia, są następujące zdania: Tutaj nie chodzi o konstruktywność - wszystkie właściwości użyte w tych dowodach są wykonalne - ale …

15 cc.complexity-theory  circuit-complexity  randomness  natural-proofs  boolean-functions 

Solwery SAT dają potężny sposób na sprawdzenie poprawności formuły logicznej za pomocą jednego kwantyfikatora. Na przykład, aby sprawdzić poprawność , możemy użyć solwera SAT, aby ustalić, czy φ ( x ) jest zadowalające. Aby sprawdzić ważność ∀ x . φ ( x ) , możemy użyć solwera SAT do ustalenia, …

15 ds.algorithms  lo.logic  sat  boolean-functions 

Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która jest …

14 cc.complexity-theory  co.combinatorics  complexity-classes  circuit-complexity  boolean-functions 

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 …

14 cc.complexity-theory  circuit-complexity  boolean-functions  fourier-analysis 

f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi⁡[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)] \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] x⊕ix⊕ix^{\oplus i}iiixxxfffMinInf[f]=defmini∈[n]Infi[f].MinInf⁡[f]=defmini∈[n]Infi⁡[f].\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f]. Biorąc pod uwagę parametr p∈[0,1]p∈[0,1]p\in[0,1] , wybieramy funkcję ppp losową fff , wybierając jej wartość na każdym z 2n2n2^n wejść niezależnie losowo, aby była równa 111 z prawdopodobieństwem ppp , a −1−1-1 z prawdopodobieństwem …

14 reference-request  pr.probability  boolean-functions 

Niech będzie funkcją większościową, tj. F ( x ) = 1 wtedy i tylko wtedy, gdy ∑ n i = 1 x i > n / 2 . Zastanawiałem się, czy istnieje prosty dowód na następujący fakt (przez „prosty” mam na myśli to, że nie polegałem na metodzie probabilistycznej, jak …

13 cc.complexity-theory  circuit-complexity  boolean-functions  circuit-families  circuit-depth 

Niech będzie funkcją boolowską zmiennych boolowskich. Niech będzie oczekiwaną wartością gdy jest uzyskane z poprzez odwrócenie każdej współrzędnej z prawdopodobieństwem .n g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2faffnnnsol( x ) = Tϵ( f) ( x …

13 cc.complexity-theory  circuit-complexity  boolean-functions 

Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla AC0AC0\mathsf{AC^0} )? Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do …

13 cc.complexity-theory  circuit-complexity  lower-bounds  boolean-functions 

Tło: W uczeniu maszynowym często pracujemy z modelami graficznymi reprezentującymi funkcje gęstości prawdopodobieństwa o wysokim wymiarze. Jeśli odrzucimy ograniczenie, które gęstość całkuje (sumuje) do 1, otrzymujemy nienormalizowaną funkcję energii o strukturze grafowej . Załóżmy, że mamy taką funkcję energetyczną zdefiniowaną na wykresie . Na każdy wierzchołek wykresu przypada jedna zmienna …

13 reference-request  machine-learning  lg.learning  boolean-functions 

Niech będzie funkcją logiczną o czułości s ( f ) i czułości bloku b s ( f ) .fafafs ( f)s(fa)s(f)b s ( f)bs(fa)bs(f) Hipoteza domniemania czułości według bloku czułości stwierdza, że ​​istnieje takie, że ∀ f , b s ( f ) ≤ s ( f ) c .c …

12 cc.complexity-theory  big-picture  boolean-functions  survey 

Powiedzmy, że mamy funkcję , taką, że ∑ x ∈ Z n 2 f ( x ) 2 = 1 (więc możemy myśleć o { f ( x ) 2 } x ∈ Z n 2 jako rozkład) . Naturalne jest zdefiniowanie entropii takiej funkcji w następujący sposób: H ( …

12 it.information-theory  boolean-functions  fourier-analysis 

Oto problem o smaku podobnym do nauki junt: Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca .x f ( x )fa: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\}xxxfa( x )f(x)f(x) Cel: Znajdź podmoduł S.SS o wartości { …

11 machine-learning  lg.learning  boolean-functions  sample-complexity