Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$? The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices.  A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $c$ is adjacent to $a$.
It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in $O(n^{\omega})$ time where $\omega$ is the matrix multiplication exponent.  Also, it is known that $\omega &lt; 2.373$.
My Question: Is the complement of Triangle Finding solvable more efficiently with nondeterminism?  In particular, is Triangle Finding in $coNTIME(\tilde{O}(n^2))$?  If this is not known, would there be any interesting implications if it was true?
Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments.  As a result, the question is still open.
Please let me know if you have any ideas.  :)

Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2.  Then, you check if there is an edge between any of these pairs.
A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph.  We can perform Boolean matrix multiplication for the squaring.  All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.
With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in $\tilde{O}(n^2)$ time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] https://doi.org/10.1007/s00453-012-9742-3 and [2] https://doi.org/10.1109/SFCS.1992.267748).  Finally, we check in $O(n^2)$ time if all of the pairs of vertices do not form edges.  &lt;- This paragraph doesn't quite work.