2 citations · 4 across the 10 of their papers we have counts for
6 papers · 1 filter
Estimating the Effective Support Size in Constant Query Complexity
Shyam Narayanan, Jakub Tětek
Estimating the support size of a distribution is a well-studied problem in statistics. Motivated by the fact that this problem is highly non-robust (as small perturbations in the d…
Sampling an Edge in Sublinear Time Exactly and Optimally
Talya Eden, Shyam Narayanan, Jakub Tětek
Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of…
Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private
Jakub Tětek
The exponential increase in the amount of available data makes taking advantage of them without violating users' privacy one of the fundamental problems of computer science. This q…
Bias Reduction for Sum Estimation
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2
In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution , and that when an element is sampled, the probabil…
A Nearly Tight Analysis of Greedy k-means++
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň +1
The famous -means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the -means problem in practice. The algorithm is very simple: it samp…
Massively Parallel Computation on Embedded Planar Graphs
Jacob Holm, Jakub Tětek
Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and rounds, unless the…