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

8 papers · 1 filter

math.CO2026

Chvátal's conjecture: a proof from The Book

David Ellis, Yuval Filmus, Ehud Friedgut

Chvátal conjectured that every downset has a maximum-size intersecting family which is a star, that is, consists of all members of the downset containing a fixed element. Recently,…

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

Given two $m$ -ary predicates $P, Q$ , an $n$ -ary polymorphism is a tuple $(f_{1}, \dots, f_{m})$ of functions such that $x^{(1)}, \dots, x^{(n)} \in P$ implies $(f_1(y_1),\dots,f_m(y_m)) \in…

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…

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…

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…

cs.LG2026

Optimal Reconstruction from Linear Queries

Yuval Filmus, Shay Moran, Elizaveta Nesterova

We study the problem of reconstructing an unknown point in $R^{d}$ from approximate linear queries. This setting arises naturally in applications ranging from low-dimensiona…