2 citations · 4 across the 10 of their papers we have counts for
13 papers
Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
Christian Janos Lebeda, Jakub Tětek
We consider the problem of computing differentially private approximate histograms and heavy hitters in a stream of elements. In the non-private setting, this is often done using t…
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…
Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses
Jakub Tětek, Mikkel Thorup
In this paper, we consider the problems from the area of sublinear-time algorithms of edge sampling, edge counting, and triangle counting. Part of our contribution is that we consi…
Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
Jakub Tětek
There is a trivial time algorithm for approximate triangle counting where is the number of triangles in the graph and the number of vertices. At the same…
CountSketches, Feature Hashing and the Median of Three
Kasper Green Larsen, Rasmus Pagh, Jakub Tětek
In this paper, we revisit the classic CountSketch method, which is a sparse, random projection that transforms a (high-dimensional) Euclidean vector to a vector of dimension $(…
Performance of Bounded-Rational Agents With the Ability to Self-Modify
Jakub Tětek, Marek Sklenka, Tomáš Gavenčiak
Self-modification of agents embedded in complex environments is hard to avoid, whether it happens via direct means (e.g. own code modification) or indirectly (e.g. influencing the…
Sampling an Edge Uniformly in Sublinear Time
Jakub Tětek
The area of sublinear algorithms have recently received a lot of attention. In this setting, one has to choose specific access model for the input, as the algorithm does not have t…
Compact I/O-Efficient Representation of Separable Graphs and Optimal Tree Layouts
Tomáš Gavenčiak, Jakub Tětek
Compact and I/O-efficient data representations play an important role in efficient algorithm design, as memory bandwidth and latency can present a significant performance bottlenec…