research
∙
11/06/2022
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Recent work shows that the expressive power of Graph Neural Networks (GN...
share
research
∙
04/25/2022
Properly learning monotone functions via local reconstruction
We give a 2^Õ(√(n)/ε)-time algorithm for properly learning monotone Bool...
research
∙
04/14/2022
Testing distributional assumptions of learning algorithms
There are many important high dimensional function classes that have fas...
research
∙
03/17/2022
Triangle and Four Cycle Counting with Predictions in Graph Streams
We propose data-driven one-pass streaming algorithms for estimating the ...
research
∙
07/14/2021
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
We consider the problem of sampling and approximately counting an arbitr...
research
∙
06/15/2021
Learning-based Support Estimation in Sublinear Time
We consider the problem of estimating the number of distinct elements in...
research
∙
02/15/2021
Local Access to Random Walks
For a graph G on n vertices, naively sampling the position of a random w...
research
∙
12/30/2020
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
Interval scheduling is a basic problem in the theory of algorithms and a...
research
∙
10/06/2020
Testing Tail Weight of a Distribution Via Hazard Rate
Understanding the shape of a distribution of data is of interest to peop...
research
∙
08/18/2020
Amortized Edge Sampling
We present a sublinear time algorithm that allows one to sample multiple...
research
∙
08/10/2020
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees
Aggregating data is fundamental to data analytics, data exploration, and...
research
∙
06/09/2020
Online Page Migration with ML Advice
We consider online algorithms for the page migration problem that use pr...
research
∙
02/19/2020
Parallel Algorithms for Small Subgraph Counting
Subgraph counting is a fundamental problem in analyzing massive graphs, ...
research
∙
02/09/2020
Monotone probability distributions over the Boolean cube can be learned with sublinear samples
A probability distribution over the Boolean cube is monotone if flipping...
research
∙
10/30/2019
Improved Local Computation Algorithm for Set Cover via Sparsification
We design a Local Computation Algorithm (LCA) for the set cover problem....
research
∙
07/06/2019
Testing Mixtures of Discrete Distributions
There has been significant study on the sample complexity of testing pro...
research
∙
07/06/2019
Towards Testing Monotonicity of Distributions Over General Posets
In this work, we consider the sample complexity required for testing the...
research
∙
04/14/2019
Approximating the noise sensitivity of a monotone Boolean function
The noise sensitivity of a Boolean function f: {0,1}^n →{0,1} is one of ...
research
∙
02/21/2019
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure that faithfully preserv...
research
∙
02/10/2019
Set Cover in Sub-linear Time
We study the classic set cover problem from the perspective of sub-linea...
research
∙
02/22/2018
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
We present O( n)-round algorithms in the Massively Parallel Computation ...
research
∙
11/29/2017
Local-Access Generators for Basic Random Graph Models
Consider a computation on a massive random graph: Does one need to gener...
research
∙
07/18/2017