2 citations · 3 across the 6 of their papers we have counts for
7 papers
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…
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…