3 citations · 6 across the 7 of their papers we have counts for
10 papers
FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
Gal Beniamini, Yuval Dor, Alon Vinnikov +10
Frontier AI models demonstrate formidable breadth of knowledge. But how close are they to true human -- or superhuman -- expertise? Genuine experts can tackle the hardest problems…
Artificial Expert Intelligence through PAC-reasoning
Shai Shalev-Shwartz, Amnon Shashua, Gal Beniamini +6
Artificial Expert Intelligence (AEI) seeks to transcend the limitations of both Artificial General Intelligence (AGI) and narrow AI by integrating domain-specific expertise with cr…
Counting Permutation Patterns with Multidimensional Trees
Gal Beniamini, Nir Lavee
We consider the well-studied pattern counting problem: given a permutation and an integer , count the number of order-isomorphic occurrences of every pat…
The Rank-Ramsey Problem and the Log-Rank Conjecture
Gal Beniamini, Nati Linial, Adi Shraibman
A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our…
How Balanced Can Permutations Be?
Gal Beniamini, Nir Lavee, Nati Linial
A permutation is -balanced if every permutation of order occurs in equally often, through order-isomorphism. In this paper, we explicitly construct $…
The -Rank and Size of Graphs
Gal Beniamini, Asaf Etgar, Yael Kirkpatrick
We consider the extremal family of graphs of order in which no two vertices have identical neighbourhoods, yet the adjacency matrix has rank only over the field of two el…
Algebraic Representations of Unique Bipartite Perfect Matching
Gal Beniamini
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…
Sparsifying the Operators of Fast Matrix Multiplication Algorithms
Gal Beniamini, Nathan Cheng, Olga Holtz +2
Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity need…
The Approximate Degree of Bipartite Perfect Matching
Gal Beniamini
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 tha…
Bipartite Perfect Matching as a Real Polynomial
Gal Beniamini, Noam Nisan
We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and …