Influence vs Nondeterministic Degree
Is Inf[f] ≤ O(sqrt(n) · ndeg(f)) for all Boolean functions? A computational investigation.
56
Functions Tested
100%
Conjecture Holds
0.577
Max Ratio (ndeg)
33%
Tighter than sdeg
Comparison: ndeg vs sdeg Conjecture Ratios
Statistic
R
ndeg
R
sdeg
Max ratio
0.577
0.866
Mean ratio
0.281
0.422
Median ratio
0.267
0.433
Std deviation
0.148
0.196
95th percentile
0.540
0.830
ndeg vs sdeg Ratios by Family
Ratio Distribution (ndeg version)
Tightening Factor by Family
Max Ratio Scaling with n