Search Results

Documents authored by Reyzin, Lev

Document
DOI: 10.4230/LIPIcs.MFCS.2024.42
Applications of Littlestone Dimension to Query Learning and to Compression

Authors: Hunter Chase, James Freitag, and Lev Reyzin

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In this paper we give several applications of Littlestone dimension. The first is to the model of [Angluin and Dohrn, 2017], where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend that model to infinite concept classes with an additional source of randomness. Third, we give improved results on the relationship of Littlestone dimension to classes with extended d-compression schemes, proving the analog of a conjecture of [Floyd and Warmuth, 1995] for Littlestone dimension.
Cite as

Hunter Chase, James Freitag, and Lev Reyzin. Applications of Littlestone Dimension to Query Learning and to Compression. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chase_et_al:LIPIcs.MFCS.2024.42,
  author =	{Chase, Hunter and Freitag, James and Reyzin, Lev},
  title =	{{Applications of Littlestone Dimension to Query Learning and to Compression}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{42:1--42:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.42},
  URN =		{urn:nbn:de:0030-drops-205988},
  doi =		{10.4230/LIPIcs.MFCS.2024.42},
  annote =	{Keywords: compression scheme, query learning, random queries, Littlestone dimension}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.34
Network Construction with Ordered Constraints

Authors: Yi Huang, Mano Vikash Janardhanan, and Lev Reyzin

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
In this paper, we study the problem of constructing a network by observing ordered connectivity constraints, which we define herein. These ordered constraints are made to capture realistic properties of real-world problems that are not reflected in previous, more general models. We give hardness of approximation results and nearly-matching upper bounds for the offline problem, and we study the online problem in both general graphs and restricted sub-classes. In the online problem, for general graphs, we give exponentially better upper bounds than exist for algorithms for general connectivity problems. For the restricted classes of stars and paths we are able to find algorithms with optimal competitive ratios, the latter of which involve analysis using a potential function defined over PQ-trees.
Cite as

Yi Huang, Mano Vikash Janardhanan, and Lev Reyzin. Network Construction with Ordered Constraints. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.FSTTCS.2017.34,
  author =	{Huang, Yi and Janardhanan, Mano Vikash and Reyzin, Lev},
  title =	{{Network Construction with Ordered Constraints}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-84090},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.34},
  annote =	{Keywords: subgraph connectivity, network construction, ordered connectivity constraints, PQ-trees}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact