We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of $(1/2-delta) cdot 2.57143^h$ for the two-sided-error randomized decision tree complexity of evaluating height $h$ formulae with error
$delta in [0,1/2)$. This improves the lower bound of $(1-2delta)(7/3)^h$ given by Jayram, Kumar, and Sivakumar (STOC03), and the one of $(1-2delta) cdot 2.55^h$ given by Leonardos (ICALP13). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) cdot 2.65622^h$. The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel interleaving of two recursive algorithms.
We show that the quantum query complexity of detecting if an $n$-vertex graph contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an operation $circ
: S times S rightarrow S$ is associative, we give an algorithm making $O(|S|^{10/7})$ queries, the first improvement to the trivial $O(|S|^{3/2})$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.
Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d >0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O
(n^{2-2/k-t})$, where $ t = max{frac{k^2- 2(m+1)}{k(k+1)(m+1)}, frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $widetilde O(n^{2-2/k})$.
