close

Вход

Забыли?

вход по аккаунту

?

О статистических свойствах нелинейности сужений булевых функций на случайно выбранное подпространство.

код для вставкиСкачать
?????????? ?????????? ??????????
2012
????????????? ?????? ?????????? ?????????? ??????????
?1(15)
????????????? ??????
?????????? ?????????? ??????????
??? 631.391:519.2
? ?????????????? ????????? ????????????
??????? ??????? ???????
?? ???????? ????????? ???????????????
?. ?. ??????????, ?. ?. ???????
???????? ??????????? ????? ? ?????? ?????????? ????????????? ????????????
???????????? ??????? Ф???????? ??????????????? ????????╗, ?. ????, ???????
E-mail: alex-crypto@mail.ru, 3tooth@mail.ru
????????, ??? ??? ???? ?????????? ??????? ??????????? n ????????????? ???????????? ???????????? ??????? ??????? n ?????????? ????? ???? ????????????? ???????????????? ????????????? ????????????? ?? ??????? ?? ?????????
??????????????? (????????, ? ????????? ??????? ????????), ??????????? ???????? ?? ??????? ?? n.
???????? ?????: ?????? ???????, ????????????, ????????? ???????????????,
?????????????? ??????.
1. ?????????? ?????? ? ???????? ?????????
????? Vn = {0, 1}n , f : Vn ? {0, 1} ? ?????? ??????? n ??????????, f?(?) =
P
= 2?n
(?1)f (x) ? ?x , ? ? Vn , ? ?? ????????????? ???????????? ????? ? ?????x?Vn
??. ???????? (??., ????????, [1, ?. 233]), ??? ???????????? Nf ??????? f ???????????? ??? ?????????? ?? f ?? ????????? ???????? ??????? ??????? n ?????????? ?
????????????? ?????????? ?????????:
Nf = 2n?1 (1 ? f?? ),
???
f?? = max |f?(?)|.
??Vn
(1)
??????? ????? N?f = Nf /2n?1 ????????????? ????????????? ??????? f .
????? ????? X ? ???????? ??????? ??????? t О n, ??? t < n. ????????? f?X (u) =
= f (uX), u ? Vt? = Vt \{0}, ????????? ?????? ???????, ??????, ? ????????? ?? ?????? ?????????? u 7? uX, u ? Vt? , ??????? ??????? f ?? ???????????????, ??????????? ???????? ??????? X (????????, ? ????????? ??????? ????????). ???????
?a (X) =
2t
P
1
?
(?1)fX (u) ? ua , a ? Vt ;
? 1 u?Vt?
?? (X) = max |?a (X)|.
a?Vt
(2)
(3)
6
?. ?. ??????????, ?. ?. ???????
2t ? 1
?? ?????? ??????????? ???????, ??? ???????? Nf?X =
(1 ? ?? (X)) ????? ??????2
???? ?? ??????? f?X ?? ????????? ???????? ??????? t ??????????, ????????????
?? ???????????? Vt? . ??????? ????? N?f?X = 1 ? ?? (X) ????????????? ?????????????
??????? f?X .
??????????? ??????, ??? ??????? X ?????????? ???????? ? ????????????? ??
????????? FtОn ???? t О n-?????? ??? ????? F = GF(2). ????? ????????? ???????? N?f?X ????? ????????????? ??? ?????????????? ?????? ????????? N?f , ? ???????????
????????? ?????? ? ????????? ???? ??????. ???????, ??? ????? ????? ?????????????? ?????????????? ????? ? ??????? ??????? f ? f?X ??????????? ? ??????? [2 ? 4]
? ????? ? ??????????? ????????????? ?????????? ?????????? ???????? ?????????????, ? ????? ???????? ???? ??????? ??????? ???????. ? ?????????, ? [3] ????????,
??? ??? ????????? ?????????????? ?????? ??????? X ?? ????????? FtОn ??? ?????
? ? Vn , ? ? (0, 1) ??????????? ???????????
P{|f?(?) ? ?X? (X)| > ?} 6
??2
.
2t ? 1
(4)
??????????? ??????????? ????????????? ? ????? ?????? ?????? ???????? ? [5], ?????? ? ?????????, ? ????? ? ?????? ????????? ??????? ??????????? ?? ?????????????
?????? ? ????? ????? ?????????? (1) ? (3) ???, ??? ?? ?? ?????, ????? ?????????????? ?????????????? ??????? f ? f?X .
???????? ??????????? ????????? ?????? ???????? ????????? ???????.
???????. ??? ????? ?, ? ? (0, 1) ?????????? ??????????? ????? t0 = t0 (?, ?), ?????,
??? ??? ????? ??????????? n > t > t0 ? ???????????? ??????? f : Vn ? {0, 1}
??????????? ???????????
(5)
P{|N?f ? N?f?X | > ?} 6 ?,
??? X ? ????????? ?????????????? t О n-??????? ??? ????? F .
?????????????? ??????? ??????????, ? ????????, ?? ??????? ???????? ?????????
??????? (2) ? ?????????? ? ?. 2. ??????????? ????????????? ?????????? ???????
? ?????????? ???????????? ??????? ??????? ??????????? ? ?. 3.
2. ?????????????? ???????
??????????? ????? n, t ? N, ??? n > t, ? ? (0, 1), ??????? f : Vn ? {0, 1} ? ??????
?????? ??????????? ??????? {|N?f ? N?f?X | > ?} = {|f?? ? ?? (X)| > ?}.
??????? ??? ??????????????? ???????????.
????? 1. ??????????? ???????????
??2
?
P{f? > ?? (X) + ?} 6 t
.
2 ?1
??????????????. ????????? ?? ?????? ?? ????????? Vn , ?????, ??? f?? = |f?(?? )|.
?? ????????? ??????? (3) ??????? {f?? > ?? (X) + ?} ?????? ??????? {|f?(?? )| >
> |?X?? (X)| + ?}, ???????, ? ???? ???????, ?????? ??????? {|f?(?? ) ? ?X?? (X)| > ?}.
?????? ?? ????????? ??????????? (4) ???????, ???
P{f?? > ?? (X) + ?} 6 P{|f?(?? ) ? ?X?? (X)| > ?} 6
????? ????????.
??2
.
2t ? 1
7
? ?????????????? ????????? ???????????? ??????? ??????? ???????
????????? ??????? ???????????, ??-????????, ?????? ????????, ?????? ???????
?? ??????? ????? ????????, ?????????? ?????? ????????????.
????? 2. ??? ????? l(k, n) ??????? ????????? ??????, ????????? ?? k ????????
???????? ????? n, ??????????? ??????????? l(k, n) < 2nk и 2k?n .
??????????????. ????? ??????? ??????????? ?????? ?? k ???????? ????????
????? n ?????
2nk ? l(k, n) = (2n ? 1)(2n ? 2) и и и (2n ? 2k?1 ) = 2nk (1 ? 2?n )(1 ? 2?(n?1) ) и и и (1 ? 2?(n?(k?1)) ).
?????? ?? ????????? ???????????
???????, ???
N
Q
(1 ? xi ) > 1 ?
i=1
N
P
xi , xi ? (0, 1), i = 1, . . . , N ,
i=1
2nk ? l(k, n) > 2nk 1 ? 2?(n?k+1) (1 + 2?1 + и и и + 2?(k?1) ) >
> 2nk 1 ? 2?(n?k+1) и 2 = 2nk ? 2nk и 2k?n .
????? ????????.
??? ?????? ?????????????? ??????? ????? m 6 t + 1 ?????????
P
?m,t =
E(?a (X))m .
(6)
a?Vt
????????? ????? ?????? ???????? ???? ? ?????????????? ???????.
????? 3. ??????????? ???????????
m
P ? m
1
1
m?t?1
f (?) + 2
1+ t
?m,t 6 1 + t
.
2 ? 1 ??Vn
2 ?1
(7)
??????????????. ??????????? ????????? (6):
?m,t
1
E
= t
(2 ? 1)m
1 P
=
E t
(?1)f (uX)?ua
?
2
?
1
a?Vt
u?Vt
!m
P
=
!
P
P
f (u(1) X)?иии?f (u(m) X)?(u(1) ?иии?u(m) )a
(?1)
u(1) ,...,u(m) ?Vt? a?Vt
=
!
P
(1)
(m?1) X)?f (u(1) X?иии?u(m?1) X)
2t
= t
(?1)f (u X)?иии?f (u
=
mE
(2 ? 1)
u(1) ,...,u(m?1) ?Vt?
P
P
(1)
(m?1) X)?f (u(1) X?иии?u(m?1) X)
2t
= t
2?tn
(?1)f (u X)?иии?f (u
.
m
(2 ? 1) u(1) ,...,u(m?1) ?V ?
X?FtОn
(8)
t
?????????? ????????? ? ?????? ????? (8) ? ???? ????? ???? ?????????
(1)
?m,t =
P(1)
2t
2t
(2)
(и
и
и)
,
?
=
m,t
(2t ? 1)m u(1) ,...,u(m?1) ?V ?
(2t ? 1)m
t
P(2)
(и и и) ,
u(1) ,...,u(m?1) ?Vt?
??? ??????? ?(1) ? ?(2) ?????????? ????? ?? ???? ??????? ??????????? ? ??????? ????????? ???????? ???????? u(1) , . . . , u(m?1) ? Vt? ??????????????. ????????? ????? 2,
(2)
?????? ???????? ?m,t ????????? ???????:
t
P
P
(1)
(m?1)
(1)
(m?1)
2
(2)
(2)
f (u X)?иии?f (u
X)?f (u X?иии?u
X) ?tn
|?m,t | = t
2
(?1)
6
(2 ? 1)m u(1) ,...,u(m?1) ?V ?
X?FtОn
t
8
?. ?. ??????????, ?. ?. ???????
m
P(2)
2t
1
2t
t(m?1)+m?1?t
m?t?1
16 t
2
=2
1+ t
.
6 t
(2 ? 1)m u(1) ,...,u(m?1) ?V ?
(2 ? 1)m
2 ?1
(9)
t
(1)
?????? ?????? ???????? ?m,t . ???????, ??? ???? ??????? u(1) , . . . , u(m?1) ? Vt ??????? ??????????,
?? ??? ?????? ?????? ???????? v (1) , . . . , v (m?1) ? Vn ?????????? ?????
t?(m?1) n
?????? X ? FtОn , ?????, ??? u(i) X = v (i) , i = 1, . . . , m ? 1. ?????????????,
2
(1)
?m,t =
P
P(1)
2t
(1)
(m?1) )?f (v (1) ?иии?v (m?1) )
?tn
tn?(m?1)n
(?1)f (v )?иии?f (v
.
2
и
2
m
t
(2 ? 1) u(1) ,...,u(m?1) ?V ?
v (1) ,...,v (m?1) ?Vn
t
?????, ?????????
P ? m
P ?mn
f (?)
=
2
??Vn
??Vn
= 2?(m?1)n
(?1)f (v
P
(1) )?иии?f (v (m) )??(v (1) ?иии?v (m) )
=
v (1) ,...,v (m) ?Vn
(?1)f (v
P
(1) )?иии?f (v (m?1) )?f (v (1) ?иии?v (m?1) )
,
v (1) ,...,v (m?1) ?Vn
??
P ? m
P(1)
2t
f (?)
1=
m
t
(2 ? 1) ??Vn
u(1) ,...,u(m?1) ?Vt?
m?1
P ? m
P ? m
1
2t (2t ? 1)
f (?)
= 1+ t
f (?) .
=
(2t ? 1)m ??Vn
2 ? 1 ??Vn
(1)
?m,t =
(10)
?? ??????????? (8)?(10) ??????? ??????????? (7).
????? 4. ??? ?????? ?????????????? ??????? ????? m 6 t + 1 ???????????
???????????
m?2
m
1
1
1
?2
?m m?t?1
?
P{f? + ? 6 ?? (X)} 6 ?
1+ t
+? 2
1+ t
.
2 ?1
1+?
2 ?1
??????????????. ?? ??????? (3) ? ??????????? ???????? ???????, ???
!
[
P
P{f?? + ? 6 ?? (X)} = P
{f?? + ? 6 |?a (X)|} 6
P{f?? + ? 6 |?a (X)|} 6
a?Vt
a?Vt
6 (f?? + ?)?m
P
E(?a (X))m = (f?? + ?)?m ?m,t .
a?Vt
?????????????, ?? ????????? ????? 3
m
P ? m ?
1
1
?m
?m m?t?1
?
?
1+ t
f (?) +(f? +?) 2
.
P{f? +? 6 ?? (X)} 6 (f? +?)
1+ t
2 ? 1 ??Vn
2 ?1
?????, ???????? ??????? (1) ? ????????? ?????????,
P ? m ?m?2 P ? 2
f (?)
6f?
f (?) = f??m?2 ,
??Vn
??Vn
?????? ???????, ???
P{f?? + ? 6 ?? (X)} 6
!m?2
m
??
1
f
1
?m
m?t?1
?2
+ (f?? + ?) 2
1+ t
6
6 (f?? + ?)
1+ t
2 ?1
2 ?1
f?? + ?
? ?????????????? ????????? ???????????? ??????? ??????? ???????
6?
?2
1+
1
t
2 ?1
1
1+?
m?2
+?
?m m?t?1
2
1+
1
t
2 ?1
9
m
.
????? ????????.
?????????? ?????????????? ???????. ?? ????????? ????? 1 ? ????? 4 ???
????? n, t, m ? N, ??? n > t > m ? 1, m ?????, ? ? (0, 1) ? f : Vn ? {0, 1}, ???????????
????????? ???????????:
P{|N?f ? N?f?X | > ?} = P{f?? > ?? (X) + ?} + P{f?? + ? 6 ?? (X)} 6
m?2
m
1
1
1
??2
?2
?m m?t?1
1+ t
+?
1+ t
+? 2
6
6 t
2 ?1
2 ? 1 1+ ? 2 ?1
m
m?2
1
??2
1
1
6 m?1
+ ??2 1 + m?1
+ ??m 2m?t?1 1 + m?1
.
2
?1
2
?1
1+?
2
?1
(11)
????? ?????? ? ? (0, 1). ??????? ?????????? ?????? ????? m0 > 0, ?????, ???
m0 ?2
1
1
?
??2
?2
1 + m0 ?1
6 ,
+?
m
?1
0
2
?1
2
?1
1+?
2
(12)
? ?????????? ??????????? ????? t0 > m0 ? 1, ?????, ???
m0
1
?
?m0 m0 ?t0 ?1
?
2
1 + m0 ?1
6 .
2
?1
2
(13)
? ???? ??????????? (11) ??? ????? n > t > t0 ??????????? ??????????? (5), ??? ?
??????????? ????????.
3. ?????????????? ?????????
?????????? ??????? ????????? ?????????? ????????????? ???????? ??????????
???????????? ??????? f : Vn ? {0, 1} ? ????????? 2n?1 ? ? ?????????????? ??
????? 1 ? ?, ?, ? ? (0, 1), ????????? ? ?????????? ???????? ????????? ????????
2n?1 (1 ? ?? (X)), ??? X ? ????????? ?????????????? ??????? ??????? t0 О n ??? ????? F , ? ????? t0 < n ???????????? ?? ??????????? (12), (13). ???????? ??????, ???
??? ?????????? ???? ???????? (2) ? ??????? ???????? ?????????????? ??????? (??.,
????????, [1, ?. 217]) ???????????? ?????????? ????????? ?????????? O(2t0 t0 n) ???????? ????????, ??? t0 ??????? ?????? ?? ? ? ?. ?????? ???????? t0 ?????? ??????
? ??????????? ????????? ?, ??????? ?????????? ????? ????????? ?? ???????? ??????????? ?????????????.
?????? ? ???, ???????? ????? 1, ??? ????? ?, ? ? (0, 1) ? n > t = dlog(1 + ??2 ? ?1 )e
??????????? ???????????
P{2n?1 (1 ? ?? (X)) ? 2n?1 ? 6 Nf } > 1 ? ?,
??? X ? ????????? ?????????????? tОn-??????? ??? ????? F , ?????? ??? ??????????
????????? ?????? ?????? ????????? Nf ?????????? ????????? O(n??2 ? ?1 log(??2 ? ?1 ))
???????? ????????. ?????, ? ???????? ??????? ?????? ???????????? ??????? f ?????
m1
P
m
n?1
?t
,
???????????? ????????? ???????? 2 (1? ??m (X)), ??? ??m (X) = 2
(?a (X))
a?Vt
10
?. ?. ??????????, ?. ?. ???????
m > 4 ? ?????? ?????. ???????? ?? ????? 3 ? ??????? ???????????, ????? ???????? ??????????? ?????????????? ????? 4, ???????? ????????? ? ???, ??? ??? ?????
?, ? ? (0, 1) ? n > t > m ? 1, ??????????????? ???????
?2 ?t
? 2
1+
1
t
2 ?1
1
1+?
m?2
?
6 ,
2
?m m?2t?1
?
2
1+
1
t
2 ?1
m
?
6 ,
2
??????????? ???????????
P{Nf 6 2n?1 (1 ? ??m (X)) + 2n?1 ?} > 1 ? ?,
??? X ? ????????? ?????????????? t О n-??????? ??? ????? F . ??? ????????????? m ? t = d1/2 и log(4m ??m ? ?1 )e ??? ??????????
????????? ???????
?????? ??m
1
m
1
??????? Nf ????????? ????????? O(2t tn) = O n?? 2 ? ? 2 log(?? 2 ? ? 2 ) ???????? ?
m 1
O(2t ) = O ?? 2 ? ? 2 ?????????????? ???????? (???????? ? ?????????? ? ??????? ???????????? ?????), ??? ???????? ? ?????????, ???????????? ???????? ?????????????
??????? ?? n, ??1 ? ? ?1 .
??????????
1. ??????? ?. ?., ????????? ?. ?., ?????? ?. ?. ?????? ??????? ? ?????? ??????????? ?
???????????. ?.: ?????, 2004. 470 ?.
2. Levin L. A. Randomness and non-determinism // J. Symbolic Logic. 1993. V. 58. No. 3.
P. 1102?1103.
3. Bshouty N., Jackson J., and Tamon C. More efficient PAC-learning of DNF with membership
queries under the uniform distribution // Proc. 12th Annual Conf. on Comput. Learning
Theory. NY, USA: ACM,1999. P. 286?295.
4. Gopalan P., O?Donnell R., Servedio A., et al. Testing Fourier dimensionality and sparsity //
SIAM J. Comput. 2011. V. 40(4). P. 1075?1100.
5. ?????????? ?. ?., ?????? ?. ?. ??????? ???????? ??????????????? ?????????? ???????????? ???????????????????? ?????????? ????????????? ??????? ??????????? //
?????????? ?????????? ??????????. 2011. ? 3(13). ?. 5?11.
Документ
Категория
Без категории
Просмотров
4
Размер файла
581 Кб
Теги
булевых, случайное, функции, выбранной, статистический, свойства, нелинейности, сужения, подпространств
1/--страниц
Пожаловаться на содержимое документа