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

6 papers · 1 filter

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…