On the Probabilistic Degree of an n-Variate Boolean Function.

Srikanth Srinivasan S. Venkitesh

Published in: APPROX-RANDOM (2021)

Keyphrases

boolean functions
uniform distribution
relevant variables
probabilistic model
multi valued
pseudo boolean functions
functional decomposition
read once formulas
membership queries
probabilistic databases
dnf formulas
polynomial size
rule base
bi decomposition