39 citations · 180 across the 62 of their papers we have counts for
7 papers · 1 filter
Fast Matrix Multiplication: Limitations of the Laser Method
Andris Ambainis, Yuval Filmus, François Le Gall
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time . Recently, a surge of activity by Stot…
Friedgut--Kalai--Naor theorem for slices of the Boolean cube
Yuval Filmus
The Friedgut--Kalai--Naor theorem states that if a Boolean function is close (in -distance) to an affine function $\ell(x_1,...,x_n) = c_0 + \s…
From Small Space to Small Width in Resolution
Yuval Filmus, Massimo Lauria, Mladen Mikša +2
In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on…
Power Distribution in Randomized Weighted Voting: the Effects of the Quota
Joel Oren, Yuval Filmus, Yair Zick +1
We study the Shapley value in weighted voting games. The Shapley value has been used as an index for measuring the power of individual agents in decision-making bodies and politica…
Orthogonal basis for functions over a slice of the Boolean hypercube
Yuval Filmus
We present an orthogonal basis for functions over a slice of the Boolean hypercube. Our basis is also an orthogonal basis of eigenvectors for the Johnson and Kneser graphs. As an a…
On the sum of the L1 influences of bounded functions
Yuval Filmus, Hamed Hatami, Nathan Keller +1
Let have degree as a multilinear polynomial. It is well-known that the total influence of is at most . Aaronson and Ambainis asked whethe…
A SageTeX Hypermatrix Algebra Package
Edinah K. Gnang, Ori Parzanchevski, Yuval Filmus
We describe here a rudimentary sage implementation of the Bhattacharya-Mesner hypermatrix algebra package.