research
∙
07/10/2023
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
We prove a characterization of the structural conditions on matrices of ...
share
research
∙
05/04/2023
Testing Convexity of Discrete Sets in High Dimensions
We study the problem of testing whether an unknown set S in n dimensions...
research
∙
04/03/2023
Distribution Testing Under the Parity Trace
Distribution testing is a fundamental statistical task with many applica...
research
∙
02/22/2023
Graphs with minimum fractional domatic number
The domatic number of a graph is the maximum number of vertex disjoint d...
research
∙
06/06/2022
Optimal Adjacency Labels for Subgraphs of Cartesian Products
For any hereditary graph class ℱ, we construct optimal adjacency labelin...
research
∙
02/18/2022
Sketching Distances in Monotone Graph Classes
We study the problems of adjacency sketching, small-distance sketching, ...
research
∙
11/05/2021
Randomized Communication and the Implicit Graph Conjecture
The most basic lower-bound question in randomized communication complexi...
research
∙
12/07/2020
VC Dimension and Distribution-Free Sample-Based Testing
We consider the problem of determining which classes of functions can be...
research
∙
07/15/2020
Downsampling for Testing and Learning in Product Distributions
We study the domain reduction problem of eliminating dependence on n fro...
research
∙
11/09/2019
Universal Communication, Universal Graphs, and Graph Labeling
We introduce a communication model called universal SMP, in which Alice ...
research
∙
10/31/2018