research
∙
03/30/2023
Online Learning and Disambiguations of Partial Concept Classes
In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introd...
share
research
∙
11/25/2021
The Implicit Graph Conjecture is False
An efficient implicit representation of an n-vertex graph G in a family ...
research
∙
11/19/2021
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, a...
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
∙
04/24/2018
On Multilinear Forms: Bias, Correlation, and Tensor Rank
In this paper, we prove new relations between the bias of multilinear fo...
research
∙
01/25/2018