I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to construct a hard function for the class of circuits of the form Majority-of-two-layers-of-Threshold-gates.

I was wondering if there is any past work where this object epsilon-biased-sets have been used as a proof technique for showing circuit lower bounds. (..I would be happy to get any reference along these lines that may strike your mind in relation to this...)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.