Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Quadratically Tight Relations for Randomized Query Complexity   Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate
complexity $C(f)$ is a complexity measure that is quadratically tight for the
zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq
C(f)^2$. In this paper we study a new complexity measure that we call
expectational certificate complexity $EC(f)$, which is also a quadratically
tight bound on $R_0(f)$: $EC(f) \leq R_0(f) = O(EC(f)^2)$. We prove that $EC(f)
\leq C(f) \leq EC(f)^2$ and show that there is a quadratic separation between
the two, thus $EC(f)$ gives a tighter upper bound for $R_0(f)$. The measure is
also related to the fractional certificate complexity $FC(f)$ as follows:
$FC(f) \leq 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 $R_0(f)$, as
$EC(f)$ is in fact a relaxation of $FC(f)$.
  In the second part of the work, we upper bound the distributed query
complexity $D^\mu_\epsilon(f)$ for product distributions $\mu$ by the square of
the query corruption bound ($\mathrm{corr}_\epsilon(f)$) which improves upon a
result of Harsha, Jain and Radhakrishnan [2015]. A similar statement for
communication complexity is open.

34
The categories of this paper are: chem-ph
9
The categories of this paper are: nlin
36
The categories of this paper are: cmp-lg
7
The categories of this paper are: hep-th
25
The categories of this paper are: patt-sol
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con
4
The categories of this paper are: cond-mat
27
The categories of this paper are: comp-gas
23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
33
The categories of this paper are: plasm-ph
12
The categories of this paper are: nucl-th
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat