2018/11/26 by Dmitry Gavinsky, Gavinsky, Dmitry, Troy Lee +5
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1811.10752
openalex publication_date 2018/11/26 · openalex created_date 2023/04/27 · openalex updated_date 2026/07/28
Let R_\ε(\⋅) stand for the bounded-error randomized query\ncomplexity with error \ε > 0. For any relation f \⊆ 0,1 n\n\× S and partial Boolean function g \⊆ 0,1 m \× 0,1 ,\nwe show that R1/3(f \∘ gn) \∈ \Ω(R4/9(f) \⋅\n\√R1/3(g)), where f \∘ gn \⊆ ( 0,1 m)n \× S is\nthe composition of f and g. We give an example of a relation f and\npartial Boolean function g for which this lower bound is tight.\n We prove our composition theorem by introducing a new complexity measure, the\nmax conflict complexity \χ(g) of a partial Boolean function g. We\nshow \χ(g) \∈ \Ω(\√R1/3(g)) for any (partial) function\ng and R1/3(f \∘ gn) \∈ \Ω(R4/9(f) \⋅ \χ(g)); these\ntwo bounds imply our composition result. We further show that \χ(g) is\nalways at least as large as the sabotage complexity of g, introduced by\nBen-David and Kothari.\n