GBGal Beniamini

Gal Beniamini

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Gal Beniamini has a total of 7 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    How Balanced Can Permutations Be?

    by Gal Beniamini, Nir Lavee, Nati Linial

    A permutation $$\pi \in \mathbb {S}_n$$ π ∈ S n is k-balanced if every permutation of order k occurs in $$\pi $$ π equally often, through order-isomorphism. In this paper, we explicitly construct k-balanced permutations for $$k \le 3$$ k ≤ 3 , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ k ≥ 4 , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ k ≥ 4 , every n-element permutation is at least $$\Omega _n(n^{k-1})$$ Ω n ( n k - 1 ) far from being k-balanced. This lower bound is matched for $$k=4$$ k = 4 , by a construction based on the Erdős–Szekeres permutation.

  • Open Access

    Counting Permutation Patterns with Multidimensional Trees

    by Gal Beniamini, Nir Lavee

    We consider the well-studied pattern counting problem: given a permutation $π\in \mathbb{S}_n$ and an integer $k > 1$, count the number of order-isomorphic occurrences of every pattern $τ\in \mathbb{S}_k$ in $π$. Our first result is an $\widetilde{\mathcal{O}}(n^2)$-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 $\mathbb{S}_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 $|\mathbb{S}_8| - 1$, one less than required. Our second result is an $\widetilde{\mathcal{O}}(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.

  • Bipartite perfect matching as a real polynomial

    by Gal Beniamini, Noam Nisan

  • Open Access

    The Approximate Degree of Bipartite Perfect Matching

    by Gal Beniamini

    The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the $\ell_\infty$-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, is $\widetilde{\Theta}(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 $\ell_1$-norm -- only exponential in $\Theta(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 \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly $\Theta(n^{3/2})$.

  • Open Access

    Sparsifying the Operators of Fast Matrix Multiplication Algorithms

    by Gal Beniamini, Nathan Cheng, Olga Holtz, Elaye Karstadt, Oded Schwartz

    Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity needs to be small. Many sub-cubic algorithms have large leading coefficients, rendering them impractical. Karstadt and Schwartz (SPAA'17, JACM'20) demonstrated how to reduce these coefficients by sparsifying an algorithm's bilinear operator. Unfortunately, the problem of finding optimal sparsifications is NP-Hard. We obtain three new methods to this end, and apply them to existing fast matrix multiplication algorithms, thus improving their leading coefficients. These methods have an exponential worst case running time, but run fast in practice and improve the performance of many fast matrix multiplication algorithms. Two of the methods are guaranteed to produce leading coefficients that, under some assumptions, are optimal.