1. Quadratically Tight Relations for Randomized Query Complexity
- Author
-
Rahul Jain, Miklos Santha, Jevgēnijs Vihrovs, Srijita Kundu, Hartmut Klauck, Swagato Sanyal, Troy Lee, Ming Hsieh Department of Electrical Engineering [Los Angeles], USC Viterbi School of Engineering, University of Southern California (USC)-University of Southern California (USC), Chennai Mathematical Institute [Inde], Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre for Quantum Technologies [Singapore] (CQT), and National University of Singapore (NUS)
- Subjects
Quadratic growth ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,0209 industrial biotechnology ,0102 computer and information sciences ,02 engineering and technology ,Measure (mathematics) ,Upper and lower bounds ,01 natural sciences ,ACM: F.: Theory of Computation ,Square (algebra) ,Computation Theory & Mathematics ,Theoretical Computer Science ,Combinatorics ,Quadratic equation ,020901 industrial engineering & automation ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Information complexity ,[INFO]Computer Science [cs] ,0102 Applied Mathematics, 0802 Computation Theory and Mathematics, 0805 Distributed Computing ,Communication complexity ,Boolean function ,ComputingMilieux_MISCELLANEOUS ,Mathematics - Abstract
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional certificate complexity FC(f) as follows: FC(f) ≤EC(f) = O(FC(f)3/2). This also connects to an open question by Aaronson whether FC(f) is a quadratically tight bound for R0(f), as EC(f) is in fact a relaxation of FC(f). In the second part of the work, we investigate whether the corruption bound corr𝜖(f) quadratically approximates R(f). By Yao’s theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity $\mathsf {D}^{\mu }_{\epsilon }(f)$ for all input distributions μ. Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. (2016), who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open.
- Published
- 2020
- Full Text
- View/download PDF