Algorithmic Frontiers of Graph and Hypergraph Problems via Global Queries

About the Workshop

This workshop explores the algorithmic landscape of graph and hypergraph problems under query access models. We study settings where the vertex set is known, but the underlying edge structure is hidden and accessible only via global aggregate queries—such as the CUT query, which returns the number or total weight of edges crossing a given cut. Our central objective is to map the query complexity of fundamental problems in this regime.

Core Themes & Goals

• Practical APIs & Implicit Graphs: Navigating real-world networks that are massive or hidden behind subset-based probing APIs.
• Theoretical Bridges: Connecting combinatorial search with broader optimization theory, mapping problems like minimum cut to submodular function minimization (SFM).
• Technique Unification: Bridging algorithmic techniques with distributed computing, sublinear algorithms, and beyond.
• The Lower Bound Frontier: Understanding and advancing existing frameworks for proving information-theoretic lower bounds via communication complexity and other methods.

Tentative Speakers

Detailed Schedule

The full schedule will be announced closer to the workshop date.