We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal O(n)-query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms. We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using O(n) expected queries, matching the Ω(n) lower bound. This approach bypasses the reconstruction barrier by introducing the notion of "independent families" - vertex subpartitions that do not share hyperedges - and iteratively coarsening them using auxiliary weighted graph connectivity techniques of [Liao and Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For hypergraphs all of whose hyperedges have even cardinality, we show that the structure is reconstructible using a Möbius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining k-connectivity certificates for r-bounded even hypergraphs in Õ_r(kn) queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic Õ(kn^1.5) query complexity for k-connectivity. This significantly improves upon the general Õ(n²) bound derived via symmetric submodular function minimization.

In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation. For weighted graphs, this is optimal due to a result in [Auza and Lee, 2021] which shows an $\Omega(n)$ lower bound for zero-error randomized algorithms. These questions have been extensively studied in the past few years, especially due to the problem’s connections to symmetric submodular function minimization. We also describe a simple polynomial time deterministic algorithm that makes $O(\frac{n\log n}{\log\log n})$ queries on undirected unweighted graphs and returns a maximal spanning forest, thereby (slightly) improving upon the state-of-the-art.

We consider the problem of learning an unknown partition of an $n$ element universe using rank queries. Such queries take as input a subset of the universe and return the number of parts of the partition it intersects. We give a simple $O(n)$-query, efficient, deterministic algorithm for this problem. We also generalize to give an $O(n + k\log r)$-rank query algorithm for a general partition matroid where $k$ is the number of parts and $r$ is the rank of the matroid.

We consider the problem of finding a spanning forest in an unknown {\em weighted} undirected graph when the access to the graph is via CUT queries, that is, one can query a subset $S\subseteq V$ of vertices and get the cut-value $\sum_{e\in \partial S} w(e)$ as the response. It is not too hard to solve this problem using $O(n\log n)$ queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes $O(n\log \log n(\log\log\log n)^2)$ CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for {\em support estimation} of weighted vectors, as in [Stockmeyer, 1983], and {\em weighted graph reconstruction} algorithms, as in [Bshouty and Mazzawi, 2012].

Sketching for speeding up regression problems involves using a sketching matrix $S$ to quickly find the approximate solution to a linear least squares regression (LLS) problem: given $A$ of size $n \times d$, with $n \gg d$, along with $b$ of size $n \times 1$, we seek a vector $y$ with minimal regression error $\lVert A y - b\rVert_2$. This approximation technique is now standard in data science, and many software systems use sketched regression internally, as a component. It is often useful to calculate derivatives (gradients for the purpose of optimization, for example) of such large systems, where sketched LLS is merely a component of a larger system whose derivatives are needed. To support Automatic Differentiation (AD) of systems containing sketched LLS, we consider propagating derivatives through $\textrm{LLS}$: both propagating perturbations (forward AD) and gradients (reverse AD). AD performs accurate differentiation and is efficient for problems with a huge number of independent variables. Since we use $\textrm{LLS}_S$ (sketched LLS) instead of $\textrm{LLS}$ for reasons of efficiency, propagation of derivatives also needs to trade accuracy for efficiency, presumably by sketching. There are two approaches for this: (a) use AD to transform the code that defines $\textrm{LLS}_S$, or (b) approximate exact derivative propagation through $\textrm{LLS}$ using sketching methods. We provide strong bounds on the errors produced due to these two natural forms of sketching in the context of AD, giving the first dimensionality reduction analysis for calculating the derivatives of a sketched computation. Our results crucially depend on the analysis of the operator norm of a sketched inverse matrix product. Extensive experiments on both synthetic and real-world experiments demonstrate the efficacy of our sketched gradients.