Negative weights makes adversaries stronger

Peter Høyer, Troy Lee, and Robert Špalek

The numerical results of the paper were obtained using the following software packages:

Enclosed you can find definitions of some Boolean functions that achieve good separations:

Name #Bits ADV ADV± Power
Ambainis function (input bits are sorted) 4 2.5 2.5135 1.0058
Two adjacent ones (one at 1100, 0110, and 0011) 4 2.6708 2.7030 1.0122
Monotone two adjacent ones (minterms 1100, 0110, and 0011) 4 2 2.0714 1.0506
Cyclic two adjacent ones (one at 11000, 01100, 00110, 00011, and 10001) 5 3.1824 3.2206 1.0102
Monotone cyclic two adjacent ones (minterms 11000, 01100, 00110, 00011, and 10001) 5 2.4495 2.5616 1.0500
Monotone version of the Kushilevitz function 6 3 3.3416 1.0981

Finally, a table of all 222 4-bits functions (up to permutations of input bits and negation of input and output bits) follows. They are numbered by 16-bit numbers according to their truth table, and sorted first by their polynomial degree and then by their ADV± bound.

Function number Degree ADV ADV± Power
Polynomial degree up to 2
0 0 0.00000 0.00000 1.00000
255 1 1.00000 1.00000 1.00000
15 2 1.41421 1.41421 1.00000
4080 2 2.00000 2.00000 1.00000
975 2 2.00000 2.00000 1.00000
960 2 2.12132 2.12132 1.00000
7128 2 2.50000 2.51353 1.00589
Polynomial degree 3
3 3 1.73205 1.73205 1.00000
63 3 1.73205 1.73205 1.00000
831 3 2.00000 2.00000 1.00000
863 3 2.00000 2.07136 1.05058
963 3 2.17533 2.17533 1.00000
427 3 2.18398 2.20814 1.01408
27 3 2.23607 2.23607 1.00000
60 3 2.23607 2.23607 1.00000
393 3 2.30940 2.30940 1.00000
383 3 2.30278 2.34406 1.02130
126 3 2.34521 2.34521 1.00000
24 3 2.34521 2.34521 1.00000
303 3 2.35829 2.35829 1.00000
1020 3 2.41421 2.41421 1.00000
495 3 2.41421 2.41421 1.00000
989 3 2.41421 2.41421 1.00000
965 3 2.41531 2.42653 1.00525
987 3 2.43128 2.44711 1.00730
424 3 2.44949 2.44949 1.00000
2034 3 2.47323 2.48653 1.00592
429 3 2.48837 2.50826 1.00874
490 3 2.52207 2.52326 1.00051
281 3 2.51464 2.54019 1.01097
2022 3 2.55719 2.58189 1.01024
1968 3 2.58199 2.58199 1.00000
1782 3 2.56155 2.59040 1.01191
984 3 2.58539 2.60282 1.00707
1973 3 2.61704 2.63510 1.00715
1910 3 2.64575 2.64575 1.00000
317 3 2.64575 2.64575 1.00000
828 3 2.64575 2.64575 1.00000
858 3 2.64575 2.64658 1.00032
300 3 2.69932 2.70595 1.00247
6030 3 2.70928 2.70928 1.00000
894 3 2.70808 2.71982 1.00434
1714 3 2.75018 2.75944 1.00332
1980 3 2.75779 2.77469 1.00602
1719 3 2.76916 2.78319 1.00496
366 3 2.76569 2.80341 1.01332
6042 3 2.84104 2.84923 1.00275
1716 3 2.86854 2.88186 1.00440
15555 3 3.00000 3.00000 1.00000
1680 3 3.00000 3.00000 1.00000
1695 3 3.00000 3.00000 1.00000
5790 3 3.00000 3.00000 1.00000
7140 3 3.00000 3.00000 1.00000
1683 3 3.00283 3.01009 1.00220
5766 3 3.02533 3.03595 1.00317
6627 3 3.01470 3.04933 1.01035
5783 3 3.03917 3.07294 1.00994
6375 3 3.12132 3.12132 1.00000
Polynomial degree 4
1 4 2.00000 2.00000 1.00000
127 4 2.00000 2.00000 1.00000
31 4 2.00000 2.00000 1.00000
7 4 2.00000 2.00000 1.00000
855 4 2.00000 2.00000 1.00000
319 4 2.17533 2.20453 1.01716
431 4 2.20635 2.20721 1.00049
23 4 2.23607 2.23607 1.00000
399 4 2.22595 2.25274 1.01495
287 4 2.28825 2.28825 1.00000
384 4 2.30940 2.30940 1.00000
447 4 2.30278 2.31707 1.00742
385 4 2.32078 2.32078 1.00000
395 4 2.29062 2.32499 1.01797
2032 4 2.35829 2.35829 1.00000
426 4 2.35829 2.35829 1.00000
967 4 2.36698 2.37004 1.00150
25 4 2.39417 2.39417 1.00000
61 4 2.39417 2.39417 1.00000
981 4 2.39489 2.40490 1.00478
283 4 2.40091 2.42364 1.01076
983 4 2.42266 2.42424 1.00074
409 4 2.39120 2.42693 1.01701
961 4 2.43531 2.43869 1.00156
111 4 2.44949 2.44949 1.00000
1638 4 2.44949 2.44949 1.00000
279 4 2.44949 2.44949 1.00000
6 4 2.44949 2.44949 1.00000
387 4 2.48662 2.50251 1.00699
859 4 2.49857 2.50575 1.00313
988 4 2.53791 2.53835 1.00019
411 4 2.52192 2.54009 1.00776
1654 4 2.51758 2.54347 1.01108
445 4 2.53019 2.55017 1.00847
425 4 2.55654 2.55654 1.00000
494 4 2.55654 2.55654 1.00000
2018 4 2.54502 2.55711 1.00507
2016 4 2.55128 2.55874 1.00312
2033 4 2.56155 2.56155 1.00000
491 4 2.56388 2.57901 1.00625
879 4 2.57641 2.58289 1.00265
415 4 2.57096 2.58436 1.00550
428 4 2.59386 2.60618 1.00497
430 4 2.60716 2.60975 1.00104
30 4 2.61313 2.61313 1.00000
2019 4 2.61439 2.62037 1.00238
488 4 2.62705 2.62705 1.00000
1639 4 2.64575 2.64575 1.00000
1969 4 2.64898 2.65285 1.00150
1778 4 2.66716 2.66873 1.00060
985 4 2.65949 2.67406 1.00558
980 4 2.67345 2.67735 1.00148
1650 4 2.67869 2.68369 1.00189
391 4 2.68828 2.70027 1.00450
878 4 2.68845 2.70057 1.00455
1918 4 2.70131 2.70131 1.00000
386 4 2.67082 2.70300 1.01219
966 4 2.70246 2.70500 1.00095
367 4 2.70387 2.70585 1.00074
1662 4 2.69544 2.70815 1.00475
1776 4 2.71519 2.71519 1.00000
280 4 2.71411 2.71639 1.00084
408 4 2.69951 2.71811 1.00691
301 4 2.71328 2.71856 1.00195
1647 4 2.73205 2.73205 1.00000
2040 4 2.73205 2.73205 1.00000
510 4 2.73205 2.73205 1.00000
1634 4 2.74013 2.74148 1.00049
856 4 2.73510 2.74171 1.00240
892 4 2.72608 2.74205 1.00582
316 4 2.74228 2.74790 1.00203
862 4 2.74628 2.75157 1.00190
829 4 2.75490 2.76384 1.00320
990 4 2.76066 2.76706 1.00228
1651 4 2.75952 2.76736 1.00280
1715 4 2.76490 2.77389 1.00319
489 4 2.78575 2.78575 1.00000
6040 4 2.77499 2.79246 1.00615
1914 4 2.79485 2.79485 1.00000
282 4 2.80369 2.80369 1.00000
1972 4 2.79678 2.80499 1.00285
893 4 2.79694 2.80607 1.00317
444 4 2.80787 2.81297 1.00176
874 4 2.81477 2.81815 1.00116
107 4 2.82843 2.82843 1.00000
1632 4 2.82843 2.82843 1.00000
22 4 2.82843 2.82843 1.00000
6014 4 2.82843 2.82843 1.00000
854 4 2.82843 2.82843 1.00000
6060 4 2.82034 2.83150 1.00381
875 4 2.83428 2.83570 1.00048
2017 4 2.83417 2.83655 1.00081
1712 4 2.84346 2.84354 1.00000
857 4 2.82909 2.85105 1.00743
1718 4 2.84413 2.85900 1.00499
382 4 2.87999 2.87999 1.00000
362 4 2.88004 2.88205 1.00066
5758 4 2.89586 2.89586 1.00000
876 4 2.89815 2.90403 1.00190
318 4 2.90163 2.90404 1.00078
407 4 2.89638 2.90417 1.00253
410 4 2.90592 2.91505 1.00294
446 4 2.91254 2.91560 1.00098
1974 4 2.91560 2.91835 1.00088
363 4 2.92040 2.92652 1.00196
1658 4 2.92940 2.93141 1.00064
5774 4 2.92267 2.93717 1.00461
1717 4 2.93360 2.94668 1.00413
1777 4 2.96176 2.96176 1.00000
982 4 2.96425 2.96696 1.00084
1635 4 2.98641 2.98673 1.00010
6120 4 3.00000 3.00000 1.00000
1713 4 2.99622 3.00474 1.00259
1912 4 3.02045 3.02045 1.00000
286 4 3.02045 3.02045 1.00000
5786 4 3.01265 3.02051 1.00236
1687 4 3.01018 3.02207 1.00358
1681 4 3.02473 3.02629 1.00047
360 4 3.04017 3.04042 1.00007
1659 4 3.04139 3.04288 1.00044
6625 4 3.02185 3.04627 1.00728
5820 4 3.03542 3.04710 1.00346
1725 4 3.04048 3.05100 1.00310
877 4 3.04498 3.05270 1.00228
390 4 3.03755 3.05354 1.00473
872 4 3.06480 3.06823 1.00100
5782 4 3.06111 3.07244 1.00330
5784 4 3.07314 3.07400 1.00025
5742 4 3.09004 3.09058 1.00016
1686 4 3.11060 3.11060 1.00000
5804 4 3.11134 3.11717 1.00165
2025 4 3.12714 3.12849 1.00038
6038 4 3.12842 3.12999 1.00044
414 4 3.12805 3.13416 1.00171
5767 4 3.13610 3.13705 1.00026
361 4 3.14864 3.14864 1.00000
5787 4 3.14761 3.15425 1.00184
105 4 3.16228 3.16228 1.00000
278 4 3.16228 3.16228 1.00000
1656 4 3.16284 3.16420 1.00037
6630 4 3.17533 3.17533 1.00000
1721 4 3.19509 3.19570 1.00016
1913 4 3.19640 3.19640 1.00000
5763 4 3.21393 3.21633 1.00064
5771 4 3.21305 3.21888 1.00155
1643 4 3.21930 3.21930 1.00000
1633 4 3.23607 3.23607 1.00000
1785 4 3.23607 3.23607 1.00000
873 4 3.26876 3.27185 1.00080
5785 4 3.27183 3.27189 1.00000
5738 4 3.28207 3.28207 1.00000
5805 4 3.34542 3.34781 1.00059
5761 4 3.36028 3.36028 1.00000
406 4 3.36637 3.37384 1.00183
1657 4 3.39009 3.39051 1.00010
5769 4 3.39400 3.39400 1.00000
7905 4 3.41421 3.41421 1.00000
5736 4 3.46410 3.46410 1.00000
5801 4 3.51041 3.51129 1.00020
5739 4 3.51414 3.51414 1.00000
1641 4 3.56995 3.56995 1.00000
5865 4 3.64575 3.64575 1.00000
5737 4 3.78478 3.78478 1.00000
27030 4 4.00000 4.00000 1.00000