JTJakub Tětek

Jakub Tětek

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Jakub Tětek has a total of 18 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Fast and Simple Sorting Using Partial Information

    by Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert E. Tarjan, Jakub Tětek

    We consider the problem of sorting n items, given the outcomes of m pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $$\textrm{O}(m+\log T)$$ O ( m + log T ) time and does $$\textrm{O}(\log T)$$ O ( log T ) comparisons, where T is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $$\textrm{O}(\log T)$$ O ( log T ) on the number of comparisons has a time bound of $$\textrm{O}(n^{2.5})$$ O ( n 2.5 ) and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top- k sorting problem: Given k and the outcomes of some pre-existing comparisons, output the smallest k items in sorted order. The modified algorithm solves the top- k sorting problem in minimum time and comparisons, to within constant factors.

  • Open Access

    Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space

    by Christian Janos Lebeda, Jakub Tětek

    Suppose we have a sample from a distribution $D$ and we want to test whether $D = D^*$ for a fixed distribution $D^*$. Specifically, we want to reject with constant probability, if the distance of $D$ from $D^*$ is $\geq \varepsilon$ in a given metric. In the case of continuous distributions, this has been studied thoroughly in the statistics literature. Namely, for the well-studied Kolmogorov metric a test is known that uses the optimal $O(1/\varepsilon^2)$ samples. However, this test naively uses also space $O(1/\varepsilon^2)$, and previous work improved this to $O(1/\varepsilon)$. In this paper, we show that much less space suffices -- we give an algorithm that uses space $O(\log^4 \varepsilon^{-1})$ in the streaming setting while also using an asymptotically optimal number of samples. This is in contrast with the standard total variation distance on discrete distributions for which such space reduction is known to be impossible. Finally, we state 9 related open problems that we hope will spark interest in this and related problems.

  • Open Access

    Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

    by Shyam Narayanan, Václav Rozhoň, Jakub Tětek, Mikkel Thorup

    Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of uniform blocks: either all 1s or all 0s, then sampling a whole block at a time does not reduce the number of samples needed for estimation. On the other hand, if bits are randomly permuted, then getting a block of $B$ bits is as good as getting $B$ independent bit samples. However, we do not want to make any such assumptions on the input. Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we have a probabilistically reliable estimate. We prove our algorithms to be instance-optimal among algorithms oblivious to the order of the blocks, which we argue is the strongest form of instance optimality we can hope for. We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function. We obtain our above results on I/O-efficient sampling by reducing to corresponding problems in the so-called sequential estimation. In this setting, one samples from an unknown distribution until one can provide an estimate with some desired error probability. We then provide non-parametric instance-optimal results for several fundamental problems: mean and quantile estimation, as well as learning mixture distributions with respect to $\ell_\infty$ and the so-called Kolmogorov-Smirnov distance.

  • Open Access

    Smooth Sensitivity Revisited: Towards Optimality

    by Richard Hladík, Jakub Tětek

    Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query $q$ on the given input $D$ and releases $q(D)$ with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from? In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student's T distribution in terms of standard deviation by arbitrarily large factors, depending on a "smoothness parameter" $γ$, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter $γ$, which can lead to significantly better performance. Moreover, we prove that the PolyPlace distribution converges for $γ\rightarrow 0$ to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that out mechanism is in a certain sense optimal for $γ\to 0$.

  • Open Access

    Near-Universally-Optimal Differentially Private Minimum Spanning Trees

    by Richard Hladík, Jakub Tětek

    Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the $\ell_1$ neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the $\ell_\infty$ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the $\ell_1$ and the $\ell_\infty$ neighbor relations.

  • Open Access

    Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private

    by 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 question has been investigated thoroughly under the framework of differential privacy. However, most of the literature has not focused on settings where the amount of data is so large that we are not even able to compute the exact answer in the non-private setting (such as in the streaming setting, sublinear-time setting, etc.). This can often make the use of differential privacy unfeasible in practice. In this paper, we show a general approach for making Monte-Carlo randomized approximation algorithms differentially private. We only need to assume the error $R$ of the approximation algorithm is sufficiently concentrated around $0$ (e.g.\ $\mathbb{E}[|R|]$ is bounded) and that the function being approximated has a small global sensitivity $\Delta$. Specifically, if we have a randomized approximation algorithm with sufficiently concentrated error which has time/space/query complexity $T(n,\rho)$ with $\rho$ being an accuracy parameter, we can generally speaking get an algorithm with the same accuracy and complexity $T(n,\Theta(\epsilon \rho))$ that is $\epsilon$-differentially private.

  • Open Access

    Massively Parallel Computation on Embedded Planar Graphs

    by 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 $o(\log n)$ rounds, unless the 1-vs-2 cycles conjecture is false. This is true even on planar graphs. Such problems include, for example, counting connected components, bipartition, minimum spanning tree problem, (approximate) shortest paths, and (approximate) diameter/radius. In this paper, we show a way to get around this limitation. Specifically, we show that if we have a ``nice'' (for example, straight-line) embedding of the input graph, all the mentioned problems can be solved with $O(n^{2/3+\epsilon})$ space per machine in $O(1)$ rounds. In conjunction with existing algorithms for computing the Delaunay triangulation, our results imply an MPC algorithm for exact Euclidean minimum spanning thee (EMST) that uses $O(n^{2/3 + \epsilon})$ space per machine and finishes in $O(1)$ rounds. This is the first improvement over a straightforward use of the standard Bor\r{u}vka's algorithm with the Dauleanay triangulation algorithm of Goodrich [SODA 1997] which results in $\Theta(\log n)$ rounds. This also partially negatively answers a question of Andoni, Nikolov, Onak, and Yaroslavtsev [STOC 2014], asking for lower bounds for exact EMST. We extend our algorithms to work with embeddings consisting of curves that are not ``too squiggly" (as formalized by the total absolute curvature). We do this via a new lemma which we believe is of independent interest and could be used to parameterize other geometric problems by the total absolute curvature. We also state several open problems regarding massively parallel computation on planar graphs.

  • Open Access

    Estimating the Effective Support Size in Constant Query Complexity

    by 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 distributions can drastically affect the support size) and thus hard to estimate, Goldreich [ECCC 2019] studied the query complexity of estimating the $\epsilon$-\emph{effective support size} $\text{Ess}_\epsilon$ of a distribution ${P}$, which is equal to the smallest support size of a distribution that is $\epsilon$-far in total variation distance from ${P}$. In his paper, he shows an algorithm in the dual access setting (where we may both receive random samples and query the sampling probability $p(x)$ for any $x$) for a bicriteria approximation, giving an answer in $[\text{Ess}_{(1+\beta)\epsilon},(1+\gamma) \text{Ess}_{\epsilon}]$ for some values $\beta, \gamma > 0$. However, his algorithm has either super-constant query complexity in the support size or super-constant approximation ratio $1+\gamma = \omega(1)$. He then asked if this is necessary, or if it is possible to get a constant-factor approximation in a number of queries independent of the support size. We answer his question by showing that not only is complexity independent of $n$ possible for $\gamma>0$, but also for $\gamma=0$, that is, that the bicriteria relaxation is not necessary. Specifically, we show an algorithm with query complexity $O(\frac{1}{\beta^3 \epsilon^3})$. That is, for any $0 < \epsilon, \beta < 1$, we output in this complexity a number $\tilde{n} \in [\text{Ess}_{(1+\beta)\epsilon},\text{Ess}_\epsilon]$. We also show that it is possible to solve the approximate version with approximation ratio $1+\gamma$ in complexity $O\left(\frac{1}{\beta^2 \epsilon} + \frac{1}{\beta \epsilon \gamma^2}\right)$. Our algorithm is very simple, and has $4$ short lines of pseudocode.

  • Open Access

    Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses

    by 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 consider three different settings, differing in the way in which one may access the neighborhood of a given vertex. In previous work, people have considered indexed neighbor access, with a query returning the $i$-th neighbor of a given vertex. Full neighborhood access model, which has a query that returns the entire neighborhood at a unit cost, has recently been considered in the applied community. Between these, we propose hash-ordered neighbor access, inspired by coordinated sampling, where we have a global fully random hash function, and can access neighbors in order of their hash values, paying a constant for each accessed neighbor. For edge sampling and counting, our new lower bounds are in the most powerful full neighborhood access model. We provide matching upper bounds in the weaker hash-ordered neighbor access model. Our new faster algorithms can be provably implemented efficiently on massive graphs in external memory and with the current APIs for, e.g., Twitter or Wikipedia. For triangle counting, we provide a separation: a better upper bound with full neighborhood access than the known lower bounds with indexed neighbor access. The technical core of our paper is our edge-sampling algorithm on which the other results depend.

  • Open Access

    Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

    by Jakub Tětek

    There is a trivial $O(\frac{n^3}{T})$ time algorithm for approximate triangle counting where $T$ is the number of triangles in the graph and $n$ the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time $\tilde{O}(n^\omega)$. Is it possible to get a negative dependency on the number of triangles $T$ while retaining the $n^\omega$ dependency on $n$? We answer this question positively by providing an algorithm which runs in time $O\big(\frac{n^\omega}{T^{\omega - 2}}\big) \cdot \text{poly}(n^{o(1)}/\epsilon)$. This is optimal in the sense that as long as the exponent of $T$ is independent of $n, T$, it cannot be improved while retaining the dependency on $n$; this as follows from the lower bound of Eden and Rosenbaum [APPROX/RANDOM 2018]. Our algorithm improves upon the state of the art when $T = \omega(1)$ and $T = o(n)$. We also consider the problem of approximate triangle counting in sparse graphs, parameterizing by the number of edges $m$. The best known algorithm runs in time $\tilde{O}\big(\frac{m^{3/2}}{T}\big)$ [Eden et al., SIAM Journal on Computing, 2017]. There is also a well known algorithm for exact triangle counting that runs in time $\tilde{O}(m^{2\omega/(\omega + 1)})$. We again get an algorithm that retains the exponent of $m$ while running faster on graphs with larger number of triangles. Specifically, our algorithm runs in time $O\Big(\frac{m^{2\omega/(\omega+1)}}{ T^{2(\omega-1)/(\omega+1)}}\Big) \cdot \text{poly}(n^{o(1)}/\epsilon)$. This is again optimal in the sense that if the exponent of $T$ is to be constant, it cannot be improved without worsening the dependency on $m$. This algorithm improves upon the state of the art when $T = \omega(1)$ and $T = o(\sqrt{m})$.