Let’s further investigate how random restrictions can simplify DNF formulas.
[...]


Let’s further investigate how random restrictions can simplify DNF formulas. [...] In this section we describe the method of applying random restrictions. This is a very “Fourierfriendly” way of simplifying a boolean function. [...] Perhaps the commonest way of representing a boolean function $f : \{0,1\}^n \to \{0,1\}$ is by a DNF formula: [...] 

Copyright © 2017 Ryan O'Donnell  All Rights Reserved 
Recent comments