4 papers
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…
WikiKV: Schema-Evolving Path-Indexed Storage for Hierarchical Knowledge Navigation
Feifei Li, Haoliang Ming, Zihan Li +5
LLM-curated hierarchical knowledge bases, namely a tree-structured wiki whose nodes summarize an underlying corpus, have become a dominant substrate for retrieval-augmented applica…
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…
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…