Search Results

Documents authored by Beniamini, Gal

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.24
Counting Permutation Patterns with Multidimensional Trees

Authors: Gal Beniamini and Nir Lavee

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the well-studied pattern-counting problem: given a permutation π ∈ 𝕊_n and an integer k > 1, count the number of order-isomorphic occurrences of every pattern τ ∈ 𝕊_k in π. Our first result is an 𝒪̃(n²)-time algorithm for k = 6 and k = 7. The proof relies heavily on a new family of graphs that we introduce, called pattern-trees. Every such tree corresponds to an integer linear combination of permutations in 𝕊_k, and is associated with linear extensions of partially ordered sets. We design an evaluation algorithm for these combinations, and apply it to a family of linearly-independent trees. For k = 8, we show a barrier: the subspace spanned by trees in the previous family has dimension exactly |𝕊₈| - 1, one less than required. Our second result is an 𝒪̃(n^{7/4})-time algorithm for k = 5. This algorithm extends the framework of pattern-trees by speeding-up their evaluation in certain cases. A key component of the proof is the introduction of pair-rectangle-trees, a data structure for dominance counting.
Cite as

Gal Beniamini and Nir Lavee. Counting Permutation Patterns with Multidimensional Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beniamini_et_al:LIPIcs.ICALP.2025.24,
  author =	{Beniamini, Gal and Lavee, Nir},
  title =	{{Counting Permutation Patterns with Multidimensional Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.24},
  URN =		{urn:nbn:de:0030-drops-234018},
  doi =		{10.4230/LIPIcs.ICALP.2025.24},
  annote =	{Keywords: Pattern counting, patterns, permutations}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.16
Algebraic Representations of Unique Bipartite Perfect Matching

Authors: Gal Beniamini

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.
Cite as

Gal Beniamini. Algebraic Representations of Unique Bipartite Perfect Matching. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2022.16},
  URN =		{urn:nbn:de:0030-drops-168140},
  doi =		{10.4230/LIPIcs.MFCS.2022.16},
  annote =	{Keywords: Bipartite Perfect Matching, Boolean Functions, Partially Ordered Sets}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.1
The Approximate Degree of Bipartite Perfect Matching

Authors: Gal Beniamini

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

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)).
Cite as

Gal Beniamini. The Approximate Degree of Bipartite Perfect Matching. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CCC.2022.1},
  URN =		{urn:nbn:de:0030-drops-165634},
  doi =		{10.4230/LIPIcs.CCC.2022.1},
  annote =	{Keywords: Bipartite Perfect Matching, Boolean Functions, Approximate Degree}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact