Geodesic
On the complexity of proving that a~Boolean function is not a~binary read-once
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 12-16.

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that it is sufficiently to present a linear number of values of a given Boolean function to prove that it is not read-once over the binary basis.
Keywords: read-once Boolean function, proof complexity. 
@article{PDM_2011_3_a1,
     author = {A. A. Voronenko},
     title = {On the complexity of proving that {a~Boolean} function is not a~binary read-once},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {12--16},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a1/}
}
TY  - JOUR
AU  - A. A. Voronenko
TI  - On the complexity of proving that a~Boolean function is not a~binary read-once
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 12
EP  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a1/
LA  - ru
ID  - PDM_2011_3_a1
ER  - 
%0 Journal Article
%A A. A. Voronenko
%T On the complexity of proving that a~Boolean function is not a~binary read-once
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 12-16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a1/
%G ru
%F PDM_2011_3_a1
A. A. Voronenko. On the complexity of proving that a~Boolean function is not a~binary read-once. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 12-16. http://geodesic.mathdoc.fr/item/PDM_2011_3_a1/

[1] Stetsenko V. A., “O predplokhikh bazisakh v $P_2$”, Matem. voprosy kibernetiki, 4, Fizmatlit, M., 1992, 139–177 | MR

[2] Peryazev N. A., Slabopovtornye bulevy funktsii v binarnom bazise, Diskretnaya matematika i informatika, 4, Izd-vo Irkut. un-ta, Irkutsk, 1998, 12 pp.

[3] Voronenko A. A., “O proveryayuschikh testakh dlya bespovtornykh funktsii”, Matem. voprosy kibernetiki, 11, Fizmatlit, M., 2002, 163–176 | MR