Testing Odd-Cycle-Freeness in Boolean Functions

Arnab Bhattacharyya Elena Grigorescu Prasad Raghavendra Asaf Shapira

Published in: CoRR (2011)

Keyphrases

boolean functions
uniform distribution
relevant variables
threshold functions
multi valued
binary decision diagrams
polynomial size
membership queries
linear threshold
functional properties
prime implicants
statistical queries
read once formulas
upper bound
desirable properties
disjunctive normal form