In general it's not easy to design the map with those properties.One special case is the local intersection property.For that we need to mention concepts of 1-term and 0-term for monotone functions.For any x with f(x)=1,there is a I-term(of this value)defined as a minimal subset S of fi e [n]:xi=1}s.t.if we fix the subset,then no matter how we change the variables xj outsideS, the function value remains 1.If we have more than one min-1-certificate,take one with the minimum size.Similarly we can define the 0-termas a subset S of fiE [n]:xi=1)with the minimum sizes.t. fixing variables to be 0 on the subset guarantees the function value to be 0.Note that a simple but crucial property of certificates is that for any 1-term a and 0-term b we have anb0.Indeed,if they are disjoint,then consider the input with all 1's at positions in a and all 0's at positions in b,then what are you gonna assign the function value?(No matter howyou do it,it'll violate the definition of one of the 0-and 1-term. Take a set A{1-terms;and B 0-terms).A and B locally intersect if for any bE B,there is a partition b bo Ub so that for all a E A,a intersects with exactly one of bo and bi.Definea Disjointness matrix D of dimension IAl xIBl,with rows and columns indexed by A and B, respectively.The (a,b)-entry is defined as l if anb and o if anbo0. Theorem 2.1.If A (1-terms)and B (0-terms;locally intersect,then L (f)>rank(D). Proof.It's enough to show that any 1-monochromatic subrectangle hashas rank 1.Fix a l-monochromatic subrectangle R'=A'×B,with an index is..t.any a'∈A'andb'∈B',i∈a'n b'.Partition B'into Bo UB,where Bo ={b'E B':i E bo},and B=(b'E B':iE b).Now for any a'E A'and b'E Bo,since A and B locally intersect,a'and b'intersect at exactly one ofthe bo and bi.But since iea'nb'and ie bo,we know that D(a',b)=0.Similarly,for any a'A' and b'E B,it holds that D(a',b')=1.So rank(Mg)=1. References [HJKP10]P.Hrubes,S.Jukna,A.Kulikov,and P.Pudlak.On convex complexity mesures, Theoretical Computer Science 411,1842-1854,2010. [KKN95]M.Karchmer,E.Kushilevitz,and N.Nisan:Fractional covers and communication complexity,SIAMJournal on Discrete Mathematics 8(1),76-92,1995.In general it’s not easy to design the map 𝜙 with those properties. One special case is the local intersection property. For that we need to mention concepts of 1-term and 0-term for monotone functions. For any x with 𝑓(𝑥) = 1, there is a 1-term (of this value) defined as a minimal subset S of {𝑖 ∈ [𝑛]: 𝑥𝑖 = 1} s.t. if we fix the subset, then no matter how we change the variables 𝑥𝑗 outside S, the function value remains 1. If we have more than one min-1-certificate, take one with the minimum size. Similarly we can define the 0-term as a subset S of {𝑖 ∈ [𝑛]: 𝑥𝑖 = 1} with the minimum size s.t. fixing variables to be 0 on the subset guarantees the function value to be 0. Note that a simple but crucial property of certificates is that for any 1-term a and 0-term b we have 𝑎 ∩ 𝑏 ≠ ∅. Indeed, if they are disjoint, then consider the input with all 1’s at positions in a and all 0’s at positions in b, then what are you gonna assign the function value? (No matter how you do it, it’ll violate the definition of one of the 0- and 1-term.) Take a set 𝐴 ⊆{1-terms} and 𝐵 ⊆{0-terms}. A and B locally intersect if for any 𝑏 ∈ 𝐵, there is a partition 𝑏 = 𝑏0 ∪ 𝑏1 so that for all 𝑎 ∈ 𝐴, a intersects with exactly one of 𝑏0 and 𝑏1. Define a Disjointness matrix D of dimension |𝐴| × |𝐵|, with rows and columns indexed by A and B, respectively. The (𝑎,𝑏)-entry is defined as 1 if 𝑎 ∩ 𝑏1 ≠ ∅ and 0 if 𝑎 ∩ 𝑏0 ≠ ∅. Theorem 2.1. If 𝐴 ⊆{1-terms} and 𝐵 ⊆{0-terms} locally intersect, then 𝐿+(𝑓) ≥ 𝑟𝑎𝑛𝑘(𝐷). Proof. It’s enough to show that any 1-monochromatic subrectangle has has rank 1. Fix a 1-monochromatic subrectangle 𝑅 ′ = 𝐴 ′ × 𝐵′, with an index is.t. any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵′, 𝑖 ∈ 𝑎 ′ ∩ 𝑏 ′ .Partition B’ into 𝐵0 ′ ∪ 𝐵1 ′ , where 𝐵0 ′ = {𝑏 ′ ∈ 𝐵 ′ :𝑖 ∈ 𝑏0 ′ }, and 𝐵1 ′ = {𝑏 ′ ∈ 𝐵 ′ :𝑖 ∈ 𝑏1 ′ }. Now for any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵0 ′ , since A and B locally intersect, a’ and b’ intersect at exactly one of the 𝑏0 ′ and 𝑏1 ′ . But since 𝑖 ∈ 𝑎 ′ ∩ 𝑏 ′ and 𝑖 ∈ 𝑏0 ′ , we know that 𝐷(𝑎’,𝑏’) = 0. Similarly, for any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵1 ′ , it holds that 𝐷(𝑎’,𝑏’) = 1. So 𝑟𝑎𝑛𝑘(𝑀𝑅 ′) = 1. □ References [HJKP10] P. Hrubes, S. Jukna, A. Kulikov, and P. Pudlak. On convex complexity mesures, Theoretical Computer Science 411, 1842–1854, 2010. [KKN95] M. Karchmer, E. Kushilevitz, and N. Nisan: Fractional covers and communication complexity, SIAM Journal on Discrete Mathematics 8(1), 76–92, 1995