Yuval Filmus

verfied profile

0 followers
Technion

Complexity Measures on the Symmetric Group and Beyond

We extend the definitions of complexity measures of functions to domains...
10/14/2020 ∙ by Neta Dafni, et al. ∙ 0 ∙ share

read it
Hypercontractivity on the symmetric group

The hypercontractive inequality is a fundamental result in analysis, wit...
09/11/2020 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Explicit SoS lower bounds from high-dimensional expanders

We construct an explicit family of 3XOR instances which is hard for O(√(...
09/11/2020 ∙ by Irit Dinur, et al. ∙ 0 ∙ share

read it
MaxSAT Resolution and Subcube Sums

We study the MaxRes rule in the context of certifying unsatisfiability. ...
05/23/2020 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Asymptotic performance of the Grimmett-McDiarmid heuristic

Grimmett and McDiarmid suggested a simple heuristic for finding stable s...
12/10/2019 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
AND Testing and Robust Judgement Aggregation

A function f{0,1}^n→{0,1} is called an approximate AND-homomorphism if c...
11/01/2019 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Lifting theorems are theorems that relate the query complexity of a func...
04/30/2019 ∙ by Arkadev Chattopadhyay, et al. ∙ 0 ∙ share

read it
Query-to-communication lifting for BPP using inner product

We prove a new query-to-communication lifting for randomized protocols, ...
04/30/2019 ∙ by Arkadev Chattopadhyay, et al. ∙ 0 ∙ share

read it
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...
02/20/2019 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
The entropy of lies: playing twenty questions with a liar

`Twenty questions' is a guessing game played by two players: Bob thinks ...
11/06/2018 ∙ by Yuval Dagan, et al. ∙ 0 ∙ share

read it
A log-Sobolev inequality for the multislice, with applications

Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...
09/10/2018 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
FKN theorem for the multislice, with applications

The Friedgut-Kalai-Naor (FKN) theorem states that if f is a Boolean func...
09/10/2018 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Boolean functions on high-dimensional expanders

We initiate the study of Boolean function analysis on high-dimensional e...
04/22/2018 ∙ by Irit Dinur, et al. ∙ 0 ∙ share

read it
Boolean constant degree functions on the slice are juntas

We show that a Boolean degree d function on the slice [n]k = { (x_1,...,...
01/19/2018 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Boolean constant degree functions on the slice are junta

We show that a Boolean degree d function on the slice [n]k = { (x_1,...,...
01/19/2018 ∙ by Yuval Filmus, et al. ∙ 0 ∙ share

read it
Low degree almost Boolean functions are sparse juntas

Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
11/26/2017 ∙ by Irit Dinur, et al. ∙ 0 ∙ share

read it
Agreement tests on graphs and hypergraphs

Agreement tests are a generalization of low degree tests that capture a ...
11/26/2017 ∙ by Irit Dinur, et al. ∙ 0 ∙ share

read it

Yuval Filmus

Featured Co-authors

Elchanan Mossel

Shay Moran

Toniann Pitassi

Prahladh Harsha

Ryan O'Donnell

Xinyu Wu

Irit Dinur

Yuval Dagan

Daniel Kane

Arkadev Chattopadhyay

Sajin Koroth

Complexity Measures on the Symmetric Group and Beyond

Hypercontractivity on the symmetric group

Explicit SoS lower bounds from high-dimensional expanders

MaxSAT Resolution and Subcube Sums

Asymptotic performance of the Grimmett-McDiarmid heuristic

AND Testing and Robust Judgement Aggregation

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Query-to-communication lifting for BPP using inner product

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

The entropy of lies: playing twenty questions with a liar

A log-Sobolev inequality for the multislice, with applications

FKN theorem for the multislice, with applications

Boolean functions on high-dimensional expanders

Boolean constant degree functions on the slice are juntas

Boolean constant degree functions on the slice are junta

Low degree almost Boolean functions are sparse juntas

Agreement tests on graphs and hypergraphs