Gal Beniamini
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Gal Beniamini has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Nir Lavee
The Hebrew University of Jerusalem, Jerusalem, Israel
2 shared publications - Elaye Karstadt1 shared publication
- Nathan Cheng1 shared publication
- Nathan Linial
The Hebrew University of Jerusalem
1 shared publication - Noam Nisan
School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel
1 shared publication - Oded Schwartz
Hebrew University of Jerusalem, Jerusalem, Israel
1 shared publication
Latest Publications
- Open Access
- 2 January 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (1) , 1-31
How Balanced Can Permutations Be?
A permutation $$\pi \in \mathbb {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$$ , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ , every n-element permutation is at least $$\Omega _n(n^{k-1})$$ far from being k-balanced. This lower bound is matched for $$k=4$$ , by a construction based on the Erdős–Szekeres permutation.- 2 January 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (1) , 1-31
Open AccessHow Balanced Can Permutations Be?
A permutation $$\pi \in \mathbb {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$$ , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ , every n-element permutation is at least $$\Omega _n(n^{k-1})$$ far from being k-balanced. This lower bound is matched for $$k=4$$ , by a construction based on the Erdős–Szekeres permutation. - Open Access
Counting Permutation Patterns with Multidimensional Trees
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.Open AccessCounting Permutation Patterns with Multidimensional Trees
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. - 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (1) , 91-131
Bipartite perfect matching as a real polynomial
- 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (1) , 91-131
Bipartite perfect matching as a real polynomial
- Open Access
The Approximate Degree of Bipartite Perfect Matching
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 AccessThe Approximate Degree of Bipartite Perfect Matching
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
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.
Open AccessSparsifying the Operators of Fast Matrix Multiplication Algorithms
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.