Yuval Filmus

activity

20102026

most citedOrthogonal basis for functions over a slice of the Boolean hypercube

39 citations · 180 across the 62 of their papers we have counts for

collaborators

Showing 2019Show all

5 papers · 1 filter

cs.DS2019

Asymptotic performance of the Grimmett-McDiarmid heuristic

Yuval Filmus

Grimmett and McDiarmid suggested a simple heuristic for finding stable sets in random graphs. They showed that the heuristic finds a stable set of size $\sim lo g_{2} n$ (with high pr…

math.CO2019

High dimensional Hoffman bound and applications in extremal combinatorics

Yuval Filmus, Konstantin Golubev, Noam Lifshitz

One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of…

cs.DM2019

AND Testing and Robust Judgement Aggregation

Yuval Filmus, Noam Lifshitz, Dor Minzer +1

A function $f : {0, 1}^{n} \to {0, 1}$ is called an approximate AND-homomorphism if choosing $x, y \in {0, 1}^{n}$ randomly, we have that $f({\bf x}\land {\bf y}) = f({\b…

cs.CC2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2

Lifting theorems are theorems that relate the query complexity of a function $f : {0, 1}^{n} \to {0, 1}$ to the communication complexity of the composed function $f \circ g^{n}$ , for…

cs.DM2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami +2

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O (\frac{n}{l o g n})$ players can bias the outcome of any Boolean function ${0, 1}^{n} \to {0, 1}$ with respe…