3 papers
math.CO2015
Average case complexity of DNFs and Shannon semi-effect for narrow subclasses of boolean functions
Sergey Granin, Yura Maximov
In this paper we establish some bounds on the complexity of disjunctive normal forms of boolean function from narrow subclasses (e.g. functions takes value 0 in a limited number of…
math.CO2015
Lower bounds on the DNF exception problem for short exception lists and related problems
Yura Maximov
In this paper we prowide lower bounds on the complexity of the DNF exception problem for short exception lists and hypercube covering problem. The method proposed is based on the r…
math.CO2015
DNF complexity of complete boolean functions
Yura Maximov
In this paper we analyse the complexity of boolean functions takes value 0 on a sufficiently small number of points. For many functions this leads to the analysis of a single funct…