Algorithmic Frontiers of Graph and Hypergraph Problems via Global Queries

In this talk, I will go over some basic examples of "global queries" focusing on the kinds covered in the workshop. After that, the talk will be in three parts: (a) "classical portion" from the 50s, which will be about reconstructing vectors (aka group testing & coin-weighing), (b) "(hyper)-graph reconstruction portion" from the late 90s, early aughts using stuff from (a), and (c) "modern-considerations" portion beginning with the works of Rubinstein et al & Beame et al, both from ITCS 2018, which ask the complexity of algorithmic questions on (hyper)-graphs using global query models. The main goal of the talk is to hopefully serve as an introduction to the remaining tutorial talks of the day, and possibly the rest of the workshop.

In this talk, I will survey recent developments in the use of cut-query algorithms for graph sparsification, computing maximum flows in graphs, and computing minimum cuts in hypergraphs. This will mostly cover the work of Rubinstein, Schramm, and Weinberg and build the foundation for many of the upcoming talks.

In this talk, I will talk about cut query algorithms for edge connectivity, minimum cut and bipartite matching. I will attempt to cover the main ideas from Blikstad et al. (FOCS 2022), Apers et al. (FOCS 2022) and Mukhopadhyay-Nanongkai (STOC 2020).

All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to compute a minimum s,t-cut for every pair of vertices s,t. Recent progress on sequential algorithms for APMC relies on reducing the problem to a small number of exact max-flow computations. I will present a different approach that yields new algorithms for APMC in unweighted graphs across three computational models: the cut-query model, the streaming model, and the fully dynamic model. These algorithms improve over the previous bounds in these models even for the simpler (single-pair) minimum s,t-cut problem. Our main technical contribution is a new APMC sparsifier constructed using approximate, rather than exact, max-flow computations. Based on joint work with Yotam Kenneth-Mordoch, with the main results taken from our STOC 2026 paper, but placed in a broader context that includes our ESA 2025 and SODA 2026 papers.

How many adaptive rounds are needed to find a basis of a matroid using only polynomially many independence queries per round? This question, initiated over 40 years ago in the work of Karp, Upfal, and Wigderson, captures a fundamental challenge in understanding the power of parallelism in the independence-query model. In this talk, I will present recent advances on this problem for both graphic matroids and general matroids. Together, these results resolve long-standing questions about the adaptive round complexity of matroid basis finding. This is based on joint works with Aaron (Louie) Putterman (Harvard) and Junkai Song (NYU).

Suppose you are given the vertices of a graph, but not its edges. The only way to learn the topology is to query the distance between two vertices. How many queries are needed to reconstruct the graph? And if full reconstruction is too expensive, what graph properties can still be inferred with relatively few queries? In this talk, I will survey graph inference from two kinds of distance queries: shortest-path distance and effective resistance. For shortest-path queries, we now know several lower bounds and algorithms: general reconstruction requires quadratically many queries without structural assumptions, while bounded-degree connected graphs admit subquadratic algorithms, and several tree-like graph families admit near-linear algorithms. Effective-resistance inference is much less developed. All pairwise effective resistances determine the graph, giving a quadratic-query reconstruction algorithm. The challenge is to understand what kinds of inference are possible with asymptotically fewer queries. I will discuss known and recent results for reconstruction and property inference, and compare the algorithmic ideas that work in the shortest-path and effective-resistance settings. The talk is based in part on joint works with Mitchell Black, Huck Bennett, Chirag Kaudan, and Evelyn Warton.

No knowledge of quantum is needed for this talk. Instead, we will speak in terms of a restricted form of a matrix-vector product, which can be simulated efficiently with quantum cut queries. We will see how to compute edge connectivity with tilde $O(\sqrt{n})$ applications of these primitives, by means of a technique called star contraction. Like 2-out contraction, star contraction preserves min cuts of a graph $G$ with high probability while reducing the number of vertices to roughly $n / \text{min-degree}(G)$, but star contraction has an advantage of parallelism that allows it to be efficiently implemented by our restricted matrix-vector product query. Finally, we will mention an open problem related to a model of certificate complexity, which has many capabilities similar to quantum cut queries, but for which we do not know an $o(n)$ upper bound for edge connectivity..

We aim to find $S* = \arg\min_{S \in F} \langle w, 1_S \rangle$ for a family $F$ of subsets of a ground set of $n$ elements. Traditionally the weight vector $w$ is available through a value oracle. We study the weaker and more robust comparison oracle, where for any $S, T \in F$, when we make a query we only learn if $w(S) < w(T)$ or $w(S) = w(T)$. We investigate the query complexity and computational efficiency of combinatorial optimization in this model. My talk will be focused on cut problems, in particular, min and max cut, both in weighted and unweighted settings. We use the notion of inference dimension to develop surprisingly query-efficient though time-expensive algorithms in the weighted case. We then give a new global subspace learning algorithm which improves the query complexity of inference-dimension based algorithms when the weights are integers of value at most $n$. Finally in the unweighted case we give query and time efficient algorithms. Based on joint work with my coauthors here: https://arxiv.org/abs/2511.15142

This talk will be a tutorial on several related techniques for proving lower bounds on the query complexity of graph problems, focusing on different types of global queries. These techniques range from reconstruction arguments, (parity) decision trees, communication complexity, and extremal combinatorics arguments.