Yuval Filmus

works on

combinatorial complexity 1 constraint satisfaction 1 polymorphisms 1 promise problems 1 universal algebra 1

From the 1 of 18 linked papers with an AI index.

activity

20242026

collaborators

20 papers

cs.LO2026

Extensions of Courcelle's Theorem without Logic

Yuval Filmus, Johann A. Makowsky

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t (G)$ , graph properties $P$ definable in Monadic Second O…

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…