License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.16
URN: urn:nbn:de:0030-drops-168140
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16814/
Go to the corresponding LIPIcs Volume Portal

Beniamini, Gal

Algebraic Representations of Unique Bipartite Perfect Matching

pdf-format:
LIPIcs-MFCS-2022-16.pdf (0.9 MB)

Abstract

We obtain complete characterizations of the Unique Bipartite Perfect Matching function, and of its Boolean dual, using multilinear polynomials over the reals. Building on previous results [Beniamini, 2020; Beniamini and Nisan, 2021], we show that, surprisingly, the dual description is sparse and has low ?₁-norm - only exponential in Θ(n log n), and this result extends even to other families of matching-related functions. Our approach relies on the Möbius numbers in the matching-covered lattice, and a key ingredient in our proof is Möbius' inversion formula.
These polynomial representations yield complexity-theoretic results. For instance, we show that unique bipartite matching is evasive for classical decision trees, and nearly evasive even for generalized query models. We also obtain a tight Θ(n log n) bound on the log-rank of the associated two-party communication task.

BibTeX - Entry

@InProceedings{beniamini:LIPIcs.MFCS.2022.16,
  author =	{Beniamini, Gal},
  title =	{{Algebraic Representations of Unique Bipartite Perfect Matching}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16814},
  URN =		{urn:nbn:de:0030-drops-168140},
  doi =		{10.4230/LIPIcs.MFCS.2022.16},
  annote =	{Keywords: Bipartite Perfect Matching, Boolean Functions, Partially Ordered Sets}
}

Keywords: Bipartite Perfect Matching, Boolean Functions, Partially Ordered Sets
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI