# Computational Complexity (cs.CC)

• We give an adaptive algorithm which tests whether an unknown Boolean function $f\colon \{0, 1\}^n \to\{0, 1\}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-increasing, or $\epsilon$-far from unate with one-sided error using $\widetilde{O}(n^{3/4}/\epsilon^2)$ queries. This improves on the best adaptive $O(n/\epsilon)$-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri when $1/\epsilon \ll n^{1/4}$. Combined with the $\widetilde{\Omega}(n)$-query lower bound for non-adaptive algorithms with one-sided error of [CWX17, BCPRS17], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.
• We present an algorithm that ensures in finite time the gathering of two robots in the non-rigid ASYNC model. To circumvent established impossibility results, we assume robots are equipped with 2-colors lights and are able to measure distances between one another. Aside from its light, a robot has no memory of its past actions, and its protocol is deterministic. Since, in the same model, gathering is impossible when lights have a single color, our solution is optimal with respect to the number of used colors.
• In this note we construct a series of small subsets containing a non-d-th power element in a finite field by applying certain bounds on incomplete character sums. Precisely, let $h=\lfloor q^{\delta}\rfloor>1$ and $d\mid q^h-1$. If $q^h-1$ has a prime divisor $r$ with $r=O((h\log q)^c)$, then there is a constant $0<\epsilon<1$ such that for a ratio at least $\frac 1 {q^{\epsilon h}}$ of $\alpha\in \mathbb{F}_{q^{h}} \backslash\mathbb{F}_{q}$, the set $S=\{ \alpha-x^t, x\in\mathbb{F}_{q}\}$ of cardinality $O(q^{\frac 12 +\delta_c})$ contains a non-d-th power in $\mathbb{F}_{q^{\lfloor q^\delta\rfloor}}$, where $t$ is the largest power of $r$ such that $t<\sqrt{q}/h$. For odd $q$, the choice of $\delta=\frac 12-d, d=o(1)>0$ shows that there exists an explicit subset of cardinality $q^{1-d}=O(\log^{2+\epsilon'}(q^h))$ containing a non-quadratic element in $\mathbb{F}_{q^h}$. On the other hand, the choice of $h=2$ shows that for any odd prime power $q$, there is an explicit subset of cardinality $O(\sqrt{q})$ containing a non-quadratic element in $\mathbb{F}_{q^2}$, essentially improving a $O(q)$ construction by Coulter and Kosick \citeCK. In addition, we obtain a similar construction for small sets containing a primitive element. The construction works well provided $\phi(q^h-1)$ is very small, where $\phi$ is the Euler's totient function.
• This article constructs a Turing Machine which can solve for $\beta^{'}$ which is RE-complete. Such a machine is only possible if there is something wrong with the foundations of computer science and mathematics. We therefore check our work by looking very closely at Cantor's diagonalization and construct a novel formal language as an Abelian group which allows us, through equivalence relations, to provide a non-trivial counterexample to Cantor's argument. As if that wasn't enough, we then discover that the impredicative nature of Gödel's diagonalization lemma leads to logical tautology, invalidating any meaning behind the method, leaving no doubt that diagonalization is flawed. Our discovery in regards to these foundational arguments opens the door to solving the P vs NP problem.

Robin Blume-Kohout Apr 07 2017 20:30 UTC

Zak, David: thanks! So (I think) this is a relation problem, not a decision problem (or even a partial function). Which is fine -- I'm happier with relation problems than with sampling problems, and the quantum part of Shor's algorithm is solving a relation problem, which is a pretty good pedigre

...(continued)
David Gosset Apr 06 2017 20:11 UTC

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak Webb Apr 06 2017 17:15 UTC

You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guaran

...(continued)
Robin Blume-Kohout Apr 06 2017 15:05 UTC

Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allo

...(continued)
Steve Flammia Apr 04 2017 13:13 UTC

I would like to publicly thank the authors for using the term "advantage" instead of the tainted word "supremacy" that makes me cringe every time I hear it.

Also, great result!

Ashley Apr 04 2017 08:35 UTC

A provable separation between analogous quantum and classical circuit classes!

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

...(continued)
Jānis Iraids Jan 25 2017 11:35 UTC

You are correct, that is a mistake -- it should be $\\{0,1\\}^n\rightarrow\\{0,1\\}$. Thank you for spotting it!

Christopher Thomas Chubb Jan 25 2017 02:27 UTC

In the abstract, should the domain of $f$ be $\lbrace0,1\rbrace^n$ instead of just $\lbrace0,1\rbrace$?

Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html