Yuval Filmus

collaborators

16 papers

cs.CC2026

An FKN Theorem for the Binary Grassmann Scheme

Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f : {0, 1}^{n} \to {- 1, 1}$ close to a degree $1$ function, then either $f$ or $- f$ is close to ei…

math.CO2026

Triviality of promise polymorphisms

Yuval Filmus

The paper extends previous work on when all polymorphisms between two predicates are trivial, showing that checking only low-arity (1- or 2-ary) polymorphisms suffices even in the…

math.CO2026

Boolean degree one functions on the Grassmann scheme

Yuval Filmus

Ferdinand Ihringer proved that Boolean degree one functions on the Grassmann scheme $J_{q} (n, k)$ are trivial when $min (k, n - k) \geq 2$ and $n$ is large enough. We provide a mostly sel…

math.CO2026

Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings

Gilad Chase, Neta Dafni, Yuval Filmus +1

We give a characterization of the largest $2$ -intersecting families of permutations of ${1, 2, \dots, n}$ and of perfect matchings of the complete graph $K_{2 n}$ for all $n \geq 2$ …

cs.LG2026

Strategic PAC Learnability via Geometric Definability

Yuval Filmus, Shay Moran, Elizaveta Nesterova +2

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is…

cs.GT2026

Classification aggregation: a quantitative impossibility theorem

Yuval Filmus

A group of individuals wishes to classify $m$ objects into $n$ categories in such a way that no class is left empty, a condition known as surjectivity. The opinions of the individu…