Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles
Deeparnab Chakrabarty, Hang Liao
We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal -query connectivity algorithms, hypergraphs face…
cs.DS2024
Learning Partitions using Rank Queries
Deeparnab Chakrabarty, Hang Liao
We consider the problem of learning an unknown partition of an element universe using rank queries. Such queries take as input a subset of the universe and return the number of…
cs.DS2023
Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs
Hang Liao, Deeparnab Chakrabarty
In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making queries in expec…