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

7 papers · 1 filter

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…