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

Srikanth Srinivasan S. Venkitesh

Published in: CoRR (2021)

Keyphrases

boolean functions
uniform distribution
functional properties
relevant variables
truth table
pseudo boolean functions
probabilistic model
polynomial size
membership queries
bi decomposition
read once formulas
binary decision diagrams
disjunctive normal form