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.CCC.2022.1
URN: urn:nbn:de:0030-drops-165634
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16563/
Go to the corresponding LIPIcs Volume Portal

Beniamini, Gal

The Approximate Degree of Bipartite Perfect Matching

pdf-format:
LIPIcs-CCC-2022-1.pdf (1 MB)

Abstract

The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the ?_∞-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching of order n, is Θ̃(n^(3/2)).
The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small ?₁-norm - only exponential in Θ(n log n). The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube [Aaronson et al., 2021; Huang, 2019]. We show that the spectral sensitivity of perfect matching is exactly Θ(n^(3/2)).

BibTeX - Entry

@InProceedings{beniamini:LIPIcs.CCC.2022.1,
  author =	{Beniamini, Gal},
  title =	{{The Approximate Degree of Bipartite Perfect Matching}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16563},
  URN =		{urn:nbn:de:0030-drops-165634},
  doi =		{10.4230/LIPIcs.CCC.2022.1},
  annote =	{Keywords: Bipartite Perfect Matching, Boolean Functions, Approximate Degree}
}

Keywords: Bipartite Perfect Matching, Boolean Functions, Approximate Degree
Collection: 37th Computational Complexity Conference (CCC 2022)
Issue Date: 2022
Date of publication: 11.07.2022

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