research
∙
09/19/2023
A tight lower bound on non-adaptive group testing estimation
Efficiently counting or detecting defective items is a crucial task in v...
share
research
∙
03/30/2023
Online Learning and Disambiguations of Partial Concept Classes
In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introd...
research
∙
10/15/2022
On depth-3 circuits and covering number: an explicit counter-example
We give a simple construction of n× n Boolean matrices with Ω(n^4/3) zer...
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
∙
11/29/2020
Approximation algorithms for hitting subgraphs
Let H be a fixed undirected graph on k vertices. The H-hitting set probl...
research
∙
02/20/2019