Yuval Filmus | DeepAI

DeepAI

Featured Co-authors

Shay Moran
46 publications
Elchanan Mossel
44 publications
Oren Salzman
28 publications
Toniann Pitassi
21 publications
Prahladh Harsha
20 publications
Ryan O'Donnell
20 publications
Xinyu Wu
18 publications
Yuval Dagan
17 publications
Daniel Kane
15 publications
Irit Dinur
13 publications
Dor Minzer
13 publications

∙ 06/09/2022

A Resilient Distributed Boosting Algorithm

Given a learning task where the data is distributed among several partie...

Yuval Filmus, et al. ∙

∙ 03/09/2022

Junta threshold for low degree Boolean functions on the slice

We show that a Boolean degree d function on the slice [n]k is a junta if...

Yuval Filmus, et al. ∙

∙ 01/08/2022

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems

We give simpler algebraic proofs of uniqueness for several Erdős-Ko-Rado...

Yuval Filmus, et al. ∙

∙ 07/16/2021

Almost linear Boolean functions on S_n are almost unions of cosets

We show that if f S_n →{0,1} is ϵ-close to linear in L_2 and 𝔼[f] ≤ 1/2 ...

Yuval Filmus, et al. ∙

∙ 06/03/2021

Optimal sets of questions for Twenty Questions

In the distributional Twenty Questions game, Bob chooses a number x from...

Yuval Filmus, et al. ∙

∙ 05/31/2021

Approximate polymorphisms

For a function g{0,1}^m→{0,1}, a function f{0,1}^n→{0,1} is called a g-p...

Gilad Chase, et al. ∙

∙ 04/18/2021

Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds

The problem of Multi-Agent Path Finding (MAPF) calls for finding a set o...

Ofir Gordon, et al. ∙

∙ 12/03/2020

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for 𝐀𝐂^0

Håstad showed that any De Morgan formula (composed of AND, OR and NOT ga...

Yuval Filmus, et al. ∙

∙ 10/14/2020

Complexity Measures on the Symmetric Group and Beyond

We extend the definitions of complexity measures of functions to domains...

Neta Dafni, et al. ∙

∙ 09/11/2020

Hypercontractivity on the symmetric group

The hypercontractive inequality is a fundamental result in analysis, wit...

Yuval Filmus, et al. ∙

∙ 09/11/2020

Explicit SoS lower bounds from high-dimensional expanders

We construct an explicit family of 3XOR instances which is hard for O(√(...

Irit Dinur, et al. ∙

∙ 05/23/2020

MaxSAT Resolution and Subcube Sums

We study the MaxRes rule in the context of certifying unsatisfiability. ...

Yuval Filmus, et al. ∙

∙ 12/10/2019

Asymptotic performance of the Grimmett-McDiarmid heuristic

Grimmett and McDiarmid suggested a simple heuristic for finding stable s...

Yuval Filmus, et al. ∙

∙ 11/01/2019

AND Testing and Robust Judgement Aggregation

A function f{0,1}^n→{0,1} is called an approximate AND-homomorphism if c...

Yuval Filmus, et al. ∙

∙ 04/30/2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Lifting theorems are theorems that relate the query complexity of a func...

Arkadev Chattopadhyay, et al. ∙

∙ 04/30/2019

Query-to-communication lifting for BPP using inner product

We prove a new query-to-communication lifting for randomized protocols, ...

Arkadev Chattopadhyay, et al. ∙

∙ 02/20/2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

The seminal result of Kahn, Kalai and Linial shows that a coalition of O...

Yuval Filmus, et al. ∙

∙ 11/06/2018

The entropy of lies: playing twenty questions with a liar

`Twenty questions' is a guessing game played by two players: Bob thinks ...

Yuval Dagan, et al. ∙

∙ 09/10/2018

A log-Sobolev inequality for the multislice, with applications

Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...

Yuval Filmus, et al. ∙

∙ 09/10/2018

FKN theorem for the multislice, with applications

The Friedgut-Kalai-Naor (FKN) theorem states that if f is a Boolean func...

Yuval Filmus, et al. ∙

∙ 04/22/2018

Boolean functions on high-dimensional expanders

We initiate the study of Boolean function analysis on high-dimensional e...

Irit Dinur, et al. ∙

∙ 01/19/2018

Boolean constant degree functions on the slice are juntas

We show that a Boolean degree d function on the slice [n]k = { (x_1,...,...

Yuval Filmus, et al. ∙

∙ 01/19/2018

Boolean constant degree functions on the slice are junta

We show that a Boolean degree d function on the slice [n]k = { (x_1,...,...

Yuval Filmus, et al. ∙

∙ 11/26/2017

Low degree almost Boolean functions are sparse juntas

Nisan and Szegedy showed that low degree Boolean functions are juntas. K...

Irit Dinur, et al. ∙

∙ 11/26/2017

Agreement tests on graphs and hypergraphs

Agreement tests are a generalization of low degree tests that capture a ...

Irit Dinur, et al. ∙