7 papers
Sharp First-Order Lower Bounds under -Polyak-Lojasiewicz Conditions
Saeed Masiha, Negar Kiyavash, Patrick Thiran
We study first-order oracle complexity under the -Polyak-Lojasiewicz condition for . For , we first show that global -sm…
Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1
We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (…
Neighborhood-Aware Graph Labeling Problem
Mohammad Shahverdikondori, Sepehr Elahi, Patrick Thiran +1
Motivated by optimization oracles in bandits with network interference, we study the Neighborhood-Aware Graph Labeling (NAGL) problem. Given a graph , a label set of siz…
Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics
Maximilien Dreveton, Matthias Grossglauser, Daichi Kuroda +1
Hierarchical clustering seeks to uncover nested structures in data by constructing a tree of clusters, where deeper levels reveal finer-grained relationships. Traditional methods,…
Optimal Graph Clustering without Edge Density Signals
Maximilien Dreveton, Elaine Siyu Liu, Matthias Grossglauser +1
This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the St…
Reducing Sensor Requirements by Relaxing the Network Metric Dimension
Paula Mürmann, Robin Jaccard, Maximilien Dreveton +2
Source localization in graphs involves identifying the origin of a phenomenon or event, such as an epidemic outbreak or a misinformation source, by leveraging structural graph prop…