research
∙
05/17/2023
Generalized Polymorphisms
We determine all m-ary Boolean functions f_0,…,f_m and n-ary Boolean fun...
share
research
∙
05/07/2023
Sampling and Certifying Symmetric Functions
A circuit 𝒞 samples a distribution 𝐗 with an error ϵ if the statistical ...
research
∙
02/27/2023
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
A classical result in online learning characterizes the optimal mistake ...
research
∙
02/13/2023
Proving Unsatisfiability with Hitting Formulas
Hitting formulas have been studied in many different contexts at least s...
research
∙
06/09/2022
A Resilient Distributed Boosting Algorithm
Given a learning task where the data is distributed among several partie...
research
∙
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...
research
∙
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...
research
∙
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 ...
research
∙
06/03/2021
Optimal sets of questions for Twenty Questions
In the distributional Twenty Questions game, Bob chooses a number x from...
research
∙
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...
research
∙
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...
research
∙
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...
research
∙
10/14/2020
Complexity Measures on the Symmetric Group and Beyond
We extend the definitions of complexity measures of functions to domains...
research
∙
09/11/2020
Hypercontractivity on the symmetric group
The hypercontractive inequality is a fundamental result in analysis, wit...
research
∙
09/11/2020
Explicit SoS lower bounds from high-dimensional expanders
We construct an explicit family of 3XOR instances which is hard for O(√(...
research
∙
05/23/2020
MaxSAT Resolution and Subcube Sums
We study the MaxRes rule in the context of certifying unsatisfiability. ...
research
∙
12/10/2019
Asymptotic performance of the Grimmett-McDiarmid heuristic
Grimmett and McDiarmid suggested a simple heuristic for finding stable s...
research
∙
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...
research
∙
04/30/2019
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
research
∙
04/30/2019
Query-to-communication lifting for BPP using inner product
We prove a new query-to-communication lifting for randomized protocols, ...
research
∙
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...
research
∙
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 ...
research
∙
09/10/2018
A log-Sobolev inequality for the multislice, with applications
Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...
research
∙
09/10/2018
FKN theorem for the multislice, with applications
The Friedgut-Kalai-Naor (FKN) theorem states that if f is a Boolean func...
research
∙
04/22/2018
Boolean functions on high-dimensional expanders
We initiate the study of Boolean function analysis on high-dimensional e...
research
∙
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,...,...
research
∙
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,...,...
research
∙
11/26/2017
Low degree almost Boolean functions are sparse juntas
Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
research
∙
11/26/2017