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 2018Show all

8 papers · 1 filter

cs.DS2018

The entropy of lies: playing twenty questions with a liar

Yuval Dagan, Yuval Filmus, Daniel Kane +1

`Twenty questions' is a guessing game played by two players: Bob thinks of an integer between $1$ and $n$ , and Alice's goal is to recover it using a minimal number of Yes/No questi…

math.PR2018

A log-Sobolev inequality for the multislice, with applications

Yuval Filmus, Ryan O'Donnell, Xinyu Wu

Let $κ \in N_{+}^{ℓ}$ satisfy $κ_{1} + \dots + κ_{ℓ} = n$ and let $U_{κ}$ denote the "multislice" of all strings $u$ in $[ℓ]^{n}$ having exactly $κ_{i}$ coordinates eq…

math.CO2018★ 2 cited

FKN theorem for the multislice, with applications

Yuval Filmus

The Friedgut-Kalai-Naor (FKN) theorem states that if $f$ is a Boolean function on the Boolean cube which is close to degree 1, then $f$ is close to a dictator, a function depending…

cs.DS2018

Online Submodular Maximization: Beating 1/2 Made Simple

Niv Buchbinder, Moran Feldman, Yuval Filmus +1

The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively from both computational and economic per…

math.CO2018

A Sauer-Shelah-Perles Lemma for Lattices

Stijn Cambie, Bogdan Chornomaz, Zeev Dvir +2

We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $…

cs.CC2018★ 5 cited

Boolean functions on high-dimensional expanders

Yotam Dikstein, Irit Dinur, Yuval Filmus +1

We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the ear…

math.CO2018

Boolean constant degree functions on the slice are juntas

Yuval Filmus, Ferdinand Ihringer

We show that a Boolean degree $d$ function on the slice $(k [ n ]) = {(x_{1}, \dots, x_{n}) \in {0, 1} : \sum_{i = 1}^{n} x_{i} = k}$ is a junta, assuming that $k, n - k$ are large eno…

math.CO2018

Boolean degree 1 functions on some classical association schemes

Yuval Filmus, Ferdinand Ihringer

We investigate Boolean degree 1 functions for several classical association schemes, including Johnson graphs, Grassmann graphs, graphs from polar spaces, and bilinear forms graphs…