  We study the problem of estimating the number of edges in an $n$-vertex
graph, accessed via the Bipartite Independent Set query model introduced by
Beame et al. (ITCS '18). In this model, each query returns a Boolean,
indicating the existence of at least one edge between two specified sets of
nodes. We present a non-adaptive algorithm that returns a $(1\pm \epsilon)$
relative error approximation to the number of edges, with query complexity
$\tilde O(\epsilon^{-5}\log^{5} n )$, where $\tilde O(\cdot)$ hides
$\textrm{poly}(\log \log n)$ dependencies. This is the first non-adaptive
algorithm in this setting achieving $\textrm{poly}(1/\epsilon,\log n)$ query
complexity. Prior work requires $\Omega(\log^2 n)$ rounds of adaptivity. We
avoid this by taking a fundamentally different approach, inspired by work on
single-pass streaming algorithms. Moreover, for constant $\epsilon$, our query
complexity significantly improves on the best known adaptive algorithm due to
Bhattacharya et al. (STACS '22), which requires $O(\epsilon^{-2} \log^{11} n)$
queries. Building on our edge estimation result, we give the first non-adaptive
algorithm for outputting a nearly uniformly sampled edge with query complexity
$\tilde O(\epsilon^{-6} \log^{6} n)$, improving on the works of Dell et al.
(SODA '20) and Bhattacharya et al. (STACS '22), which require $\Omega(\log^3
n)$ rounds of adaptivity. Finally, as a consequence of our edge sampling
algorithm, we obtain a $\tilde O(n\log^ 8 n)$ query algorithm for connectivity,
using two rounds of adaptivity. This improves on a three-round algorithm of
Assadi et al. (ESA '21) and is tight; there is no non-adaptive algorithm for
connectivity making $o(n^2)$ queries.
