Ronitt Rubinfeld | DeepAI

DeepAI AI Chat

Featured Co-authors

David P. Woodruff
105 publications
Ilias Diakonikolas
73 publications
Mohsen Ghaffari
35 publications
Merav Parter
33 publications
Ravi Kumar
29 publications
Piotr Indyk
29 publications
Shyam Narayanan
24 publications
Christoph Grunau
23 publications
Aditya Parameswaran
22 publications
Sandeep Silwal
22 publications
Slobodan Mitrović
21 publications

∙ 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...

0 Anders Aamand, et al. ∙

∙ 04/25/2022

Properly learning monotone functions via local reconstruction

We give a 2^Õ(√(n)/ε)-time algorithm for properly learning monotone Bool...

0 Jane Lange, et al. ∙

∙ 04/14/2022

Testing distributional assumptions of learning algorithms

There are many important high dimensional function classes that have fas...

6 Ronitt Rubinfeld, et al. ∙

∙ 03/17/2022

Triangle and Four Cycle Counting with Predictions in Graph Streams

We propose data-driven one-pass streaming algorithms for estimating the ...

2 Justin Y. Chen, et al. ∙

∙ 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...

0 Amartya Shankha Biswas, et al. ∙

∙ 06/15/2021

Learning-based Support Estimation in Sublinear Time

We consider the problem of estimating the number of distinct elements in...

9 Talya Eden, et al. ∙

∙ 02/15/2021

Local Access to Random Walks

For a graph G on n vertices, naively sampling the position of a random w...

0 Amartya Shankha Biswas, et al. ∙

∙ 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...

0 Spencer Compton, et al. ∙

∙ 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...

0 Maryam Aliakbarpour, et al. ∙

∙ 08/18/2020

Amortized Edge Sampling

We present a sublinear time algorithm that allows one to sample multiple...

0 Talya Eden, et al. ∙

∙ 08/10/2020

Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees

Aggregating data is fundamental to data analytics, data exploration, and...

0 Stephen Macke, et al. ∙

∙ 06/09/2020

Online Page Migration with ML Advice

We consider online algorithms for the page migration problem that use pr...

0 Piotr Indyk, et al. ∙

∙ 02/19/2020

Parallel Algorithms for Small Subgraph Counting

Subgraph counting is a fundamental problem in analyzing massive graphs, ...

0 Amartya Shankha Biswas, et al. ∙

∙ 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...

0 Ronitt Rubinfeld, et al. ∙

∙ 10/30/2019

Improved Local Computation Algorithm for Set Cover via Sparsification

We design a Local Computation Algorithm (LCA) for the set cover problem....

0 Christoph Grunau, et al. ∙

∙ 07/06/2019

Testing Mixtures of Discrete Distributions

There has been significant study on the sample complexity of testing pro...

3 Maryam Aliakbarpour, et al. ∙

∙ 07/06/2019

Towards Testing Monotonicity of Distributions Over General Posets

In this work, we consider the sample complexity required for testing the...

1 Maryam Aliakbarpour, et al. ∙

∙ 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 ...

0 Ronitt Rubinfeld, et al. ∙

∙ 02/21/2019

Local Computation Algorithms for Spanners

A graph spanner is a fundamental graph structure that faithfully preserv...

0 Merav Parter, et al. ∙

∙ 02/10/2019

Set Cover in Sub-linear Time

We study the classic set cover problem from the perspective of sub-linea...

0 Piotr Indyk, et al. ∙

∙ 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 ...

0 Mohsen Ghaffari, et al. ∙

∙ 11/29/2017

Local-Access Generators for Basic Random Graph Models

Consider a computation on a massive random graph: Does one need to gener...

0 Amartya Shankha Biswas, et al. ∙

∙ 07/18/2017

Differentially Private Identity and Closeness Testing of Discrete Distributions

We investigate the problems of identity and closeness testing over a dis...

0 Maryam Aliakbarpour, et al. ∙