We investigate the computational complexity of the discrete logarithm, the computational Diffie-Hellman and the decisional Diffie-Hellman problems in some identity black-box groups $G_{p,t}$, where $p$ is a prime number and $t$ is a positive integer. These are defined as quotient groups of vector space $Z_p^{t+1}$ by a hyperplane $H$ given through an identity oracle. While in general black-box groups that have unique encoding of their elements these computational problems are classically all hard and quantumly all easy, we find that in the groups $G_{p,t}$ the situation is more contrasted. We prove that while there is a polynomial time probabilistic algorithm to solve the decisional Diffie-Hellman problem in $G_{p,1}$, the probabilistic query complexity of all the other problems is $\Omega(p)$, and their quantum query complexity is $\Omega(\sqrt{p})$. Our results therefore provide a new example of a group where the computational and the decisional Diffie-Hellman problems have widely different complexity.

We give a family of dictatorship tests with perfect completeness and low-soundness for 2–to–2 constraints. The associated 2–to–2 conjecture has been the basis of a few inapproximability results with perfect completeness. Our result provides some indication of the expressiveness and non-triviality of 2–to–2 constraints, given the close connections between dictatorship tests and satisfiability and approximability of CSPs.

The ε-approximate degree of a function $f\colon X \to $∞ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \l eq \epsilon$ for all $x \in X$. We determine the ε-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are $\Theta(n^{2/3} \log^{1/3}(1/\epsilon))$, $\tilde\Theta(n^{3/4} \log^{1/4}(1/\epsilon))$, and $\Theta(n^{1/3} \log^{2/3}(1/\epsilon))$, respectively. Previously, these bounds we re known only for constant $\epsilon.$

We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is $\Omega(n^{1/4})$. This improves on the previous best lower bound of $\Omega(n^{1/6})$ due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of $O(n^{1/3})$.