
-
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 high-dimensional 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 Grimmett-McDiarmid 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 AND-homomorphism if c...
read it
-
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
read it
-
Query-to-communication lifting for BPP using inner product
We prove a new query-to-communication lifting for randomized protocols, ...
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...
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 log-Sobolev 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 Friedgut-Kalai-Naor (FKN) theorem states that if f is a Boolean func...
read it
-
Boolean functions on high-dimensional expanders
We initiate the study of Boolean function analysis on high-dimensional 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