
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...
read it

Complexity Measures on the Symmetric Group and Beyond
We extend the definitions of complexity measures of functions to domains...
read it

Hypercontractivity on the symmetric group
The hypercontractive inequality is a fundamental result in analysis, wit...
read it

Explicit SoS lower bounds from highdimensional expanders
We construct an explicit family of 3XOR instances which is hard for O(β(...
read it

MaxSAT Resolution and Subcube Sums
We study the MaxRes rule in the context of certifying unsatisfiability. ...
read it

Asymptotic performance of the GrimmettMcDiarmid heuristic
Grimmett and McDiarmid suggested a simple heuristic for finding stable s...
read it

AND Testing and Robust Judgement Aggregation
A function f{0,1}^nβ{0,1} is called an approximate ANDhomomorphism if c...
read it

QuerytoCommunication Lifting Using LowDiscrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
read it

Querytocommunication lifting for BPP using inner product
We prove a new querytocommunication lifting for randomized protocols, ...
read it

Biasing Boolean Functions and Collective CoinFlipping Protocols over Arbitrary Product Distributions
The seminal result of Kahn, Kalai and Linial shows that a coalition of O...
read it

The entropy of lies: playing twenty questions with a liar
`Twenty questions' is a guessing game played by two players: Bob thinks ...
read it

A logSobolev inequality for the multislice, with applications
Let ΞΊβN_+^β satisfy ΞΊ_1 + ... + ΞΊ_β = n and let U_ΞΊ denote the "multisli...
read it

FKN theorem for the multislice, with applications
The FriedgutKalaiNaor (FKN) theorem states that if f is a Boolean func...
read it

Boolean functions on highdimensional expanders
We initiate the study of Boolean function analysis on highdimensional e...
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,...,...
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,...,...
read it

Low degree almost Boolean functions are sparse juntas
Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
read it

Agreement tests on graphs and hypergraphs
Agreement tests are a generalization of low degree tests that capture a ...
read it
Yuval Filmus
verfied profile