Search Results

Documents authored by Liao, Hang


Document
Learning Partitions Using Rank Queries

Authors: Deeparnab Chakrabarty and Hang Liao

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)


Abstract
We consider the problem of learning an unknown partition of an n element universe using rank queries. Such queries take as input a subset of the universe and return the number of parts of the partition it intersects. We give a simple O(n)-query, efficient, deterministic algorithm for this problem. We also generalize to give an O(n + klog r)-rank query algorithm for a general partition matroid where k is the number of parts and r is the rank of the matroid.

Cite as

Deeparnab Chakrabarty and Hang Liao. Learning Partitions Using Rank Queries. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.FSTTCS.2024.16,
  author =	{Chakrabarty, Deeparnab and Liao, Hang},
  title =	{{Learning Partitions Using Rank Queries}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.16},
  URN =		{urn:nbn:de:0030-drops-222051},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.16},
  annote =	{Keywords: Query Complexity, Hypergraph Learning, Matroids}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail