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

78 papers

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…

math.CO2025

Approximate polymorphisms of predicates

Yaroslav Alekseev, Yuval Filmus

A generalized polymorphism of a predicate $P \subseteq {0, 1}^{m}$ is a tuple of functions $f_{1}, \dots, f_{m} : {0, 1}^{n} \to {0, 1}$ satisfying the following property: If $x^{(1)}…

cs.LO2025

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…

math.CO2025

Sensitivity and Hamming graphs

Sara Asensio, Yuval Filmus, Ignacio García-Marco +1

For any $m \geq 3$ we show that the Hamming graph $H (n, m)$ admits an imbalanced partition into $m$ sets, each inducing a subgraph of low maximum degree. This improves previous resul…

cs.CC2025

Catalytic Computing and Register Programs Beyond Log-Depth

Yaroslav Alekseev, Yuval Filmus, Ian Mertz +2

In a seminal work, Buhrman et al. (STOC 2014) defined the class $C S P A C E (s, c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$ , which is a tape whose…

math.CO2025

Aggregation of evaluations without unanimity

Yuval Filmus

Dokow and Holzman determined which predicates over ${0, 1}$ satisfy an analog of Arrow's theorem: all unanimous aggregators are dictatorial. Szegedy and Xu, extending earlier wor…

math.CO2025

Effective MC-finiteness

Yuval Filmus, Eldar Fischer, Johann A. Makowsky

An integer sequence $(a_{n})_{n \in N}$ is \emph{MC-finite} if for all $m$ , the sequence $a_{n} mod m$ is eventually periodic. There are MC-finite sequences $(a_n)_{n \in \m…

cs.DS2024

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

Yuval Filmus, Roy Schwartz, Alexander V. Smal

We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy…

cs.LG2024

Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs

Yuval Filmus, Steve Hanneke, Idan Mehalel +1

Consider the domain of multiclass classification within the adversarial online setting. What is the price of relying on bandit feedback as opposed to full information? To what exte…

math.CO2023★ 2 cited

Sparse graph counting and Kelley-Meka bounds for binary systems

Yuval Filmus, Hamed Hatami, Kaave Hosseini +1

In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In thi…

cs.CC2023

Bounded Simultaneous Messages

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus +3

We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function $f (x, y)$ of their inputs by sen…

cs.CC2023

Sampling and Certifying Symmetric Functions

Yuval Filmus, Itai Leigh, Artur Riazanov +1

A circuit $C$ samples a distribution $X$ with an error $ε$ if the statistical distance between the output of $C$ on the uniform input and $X$ …

math.CO2023

Generalized polymorphisms

Gilad Chase, Yuval Filmus

We find all functions $f_{0}, f_{1}, \dots, f_{m} : {0, 1}^{n} \to {0, 1}$ and $g_{0}, g_{1}, \dots, g_{n} : {0, 1}^{m} \to {0, 1}$ satisfying the following identity for all $n \times m$ mat…

cs.LG2023

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

Yuval Filmus, Steve Hanneke, Idan Mehalel +1

A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an an…

math.CO2023★ 1 cited

MC-finiteness of restricted set partition functions

Yuval Filmus, Eldar Fischer, Johann A. Makowsky +1

A sequence $s (n)$ of integers is MC-finite if for every $m \in N^{+}$ the sequence $s^{m} (n) = s (n) mod m$ is ultimately periodic. We discuss various ways of proving and di…

cs.CC2023

Proving Unsatisfiability with Hitting Formulas

Yuval Filmus, Edward A. Hirsch, Artur Riazanov +2

Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultane…

math.CO2022★ 5 cited

Irreducible subcube partitions

Yuval Filmus, Edward Hirsch, Sascha Kurz +4

A \emph{subcube partition} is a partition of the Boolean cube ${0, 1}^{n}$ into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are…