Krzysztof Onak

SODA Conference 2021 Conference Paper

Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model

• Krzysztof Nowicki 0002
• Krzysztof Onak

We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions. We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest, 2-Edge Connected Components, and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle efficiently would improve on the round complexity of known static algorithms on sparse graphs. Our algorithms can process batches of updates of size Θ( S ), for Minimum Spanning Forest and 2-Edge Connected Components, and Θ( S 1– ∊ ), for Maximal Matching, in O (1) rounds, where S is the local memory of a single machine.

STOC Conference 2020 Conference Paper

Walking randomly, massively, and efficiently

• Jakub Lacki
• Slobodan Mitrovic
• Krzysztof Onak
• Piotr Sankowski

We introduce a set of techniques that allow for efficiently generating many independent random walks in the Massively Parallel Computation (MPC) model with space per machine strongly sublinear in the number of vertices. In this space-per-machine regime, many natural approaches to graph problems struggle to overcome the Θ(log n ) MPC round complexity barrier, where n is the number of vertices. Our techniques enable achieving this for PageRank—one of the most important applications of random walks—even in more challenging directed graphs, as well as for approximate bipartiteness and expansion testing. In the undirected case, we start our random walks from the stationary distribution, which implies that we approximately know the empirical distribution of their next steps. This allows for preparing continuations of random walks in advance and applying a doubling approach. As a result we can generate multiple random walks of length l in Θ(log l ) rounds on MPC. Moreover, we show that under the popular 1-vs.-2-Cycles conjecture, this round complexity is asymptotically tight. For directed graphs, our approach stems from our treatment of the PageRank Markov chain. We first compute the PageRank for the undirected version of the input graph and then slowly transition towards the directed case, considering convex combinations of the transition matrices in the process. For PageRank, we achieve the following round complexities for damping factor equal to 1 − є: in O (log log n + log 1 / є) rounds for undirected graphs (with Õ( m / є 2 ) total space), in Õ(log 2 log n + log 2 1/є) rounds for directed graphs (with Õ(( m + n 1+ o (1) ) / poly (є)) total space). The round complexity of our result for computing PageRank has only logarithmic dependence on 1/є. We use this to show that our PageRank algorithm can be used to construct directed length- l random walks in O (log 2 log n + log 2 l ) rounds with Õ(( m + n 1+ o (1) ) poly ( l )) total space. More specifically, by setting є = Θ(1 / l ), a length- l PageRank walk with constant probability contains no random jump, and hence is a directed random walk.

SODA Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

• Sepehr Assadi
• Krzysztof Onak
• Baruch Schieber
• Shay Solomon

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al. , STOC’18]. The algorithm is deterministic and its update time is O ( m 3/4 ), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O ( m 2/3 ) and O ( m 2/3 ), respectively. Du and Zhang also gave a randomized algorithm with update time. Moreover, they provided some partial (conditional) hardness results hinting that the update time of m 1/2– ε, and in particular n 1– ε for n -vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Õ ( m 1/3 ) expected amortized update time, which results in an improved performance over our update time algorithm for sufficiently sparse graphs, and breaks the m 1/2 barrier of Du and Zhang for all values of m.

ICML Conference 2019 Conference Paper

Scalable Fair Clustering

• Arturs Backurs
• Piotr Indyk
• Krzysztof Onak
• Baruch Schieber
• Ali Vakilian
• Tal Wagner

We study the fair variant of the classic k-median problem introduced by (Chierichetti et al. , NeurIPS 2017) in which the points are colored, and the goal is to minimize the same average distance objective as in the standard $k$-median problem while ensuring that all clusters have an “approximately equal” number of points of each color. (Chierichetti et al. , NeurIPS 2017) proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

STOC Conference 2018 Conference Paper

Fully dynamic maximal independent set with sublinear update time

• Sepehr Assadi
• Krzysztof Onak
• Baruch Schieber
• Shay Solomon

A maximal independent set (MIS) can be maintained in an evolving m -edge graph by simply recomputing it from scratch in O ( m ) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O (min{Δ, m 3/4 }), where Δ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O (min{Δ, m 3/4 }) amortized message complexity, and O (1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

STOC Conference 2018 Conference Paper

Round compression for parallel matching algorithms

• Artur Czumaj
• Jakub Lacki
• Aleksander Madry
• Slobodan Mitrovic
• Krzysztof Onak
• Piotr Sankowski

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms?

STOC Conference 2018 Conference Paper

The query complexity of graph isomorphism: bypassing distribution testing lower bounds

• Krzysztof Onak
• Xiaorui Sun

We study the query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n 1+ o (1) queries, improving on the previous best bound of Õ( n 5/4 ). Since the problem is known to require Ω( n ) queries, our algorithm is optimal up to a subpolynomial factor. While trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the Ω( n 2/3 )-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an n 1+Ω(1) barrier for Fischer and Matsliah’s approach. We circumvent this and other limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.

NeurIPS Conference 2017 Conference Paper

Communication-Efficient Distributed Learning of Discrete Distributions

• Ilias Diakonikolas
• Elena Grigorescu
• Jerry Li
• Abhiram Natarajan
• Krzysztof Onak
• Ludwig Schmidt

We initiate a systematic investigation of distribution learning (density estimation) when the data is distributed across multiple servers. The servers must communicate with a referee and the goal is to estimate the underlying distribution with as few bits of communication as possible. We focus on non-parametric density estimation of discrete distributions with respect to the l1 and l2 norms. We provide the first non-trivial upper and lower bounds on the communication complexity of this basic estimation task in various settings of interest. Specifically, our results include the following: 1. When the unknown discrete distribution is unstructured and each server has only one sample, we show that any blackboard protocol (i. e. , any protocol in which servers interact arbitrarily using public messages) that learns the distribution must essentially communicate the entire sample. 2. For the case of structured distributions, such as k-histograms and monotone distributions, we design distributed learning algorithms that achieve significantly better communication guarantees than the naive ones, and obtain tight upper and lower bounds in several regimes. Our distributed learning algorithms run in near-linear time and are robust to model misspecification. Our results provide insights on the interplay between structure and communication efficiency for a range of fundamental distribution estimation tasks.

SODA Conference 2015 Conference Paper

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

• Hossein Esfandiari
• MohammadTaghi Hajiaghayi
• Vahid Liaghat
• Morteza Monemizadeh
• Krzysztof Onak

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o ( n 1/2 ) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o ( n ) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

STOC Conference 2014 Conference Paper

Parallel algorithms for geometric graph problems

• Alexandr Andoni
• Aleksandar Nikolov
• Krzysztof Onak
• Grigory Yaroslavtsev

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + ε )-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years.

SODA Conference 2012 Conference Paper

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size

• Krzysztof Onak
• Dana Ron
• Michal Rosen
• Ronitt Rubinfeld

FOCS Conference 2011 Conference Paper

Planar Graphs: Random Walks and Bipartiteness Testing

• Artur Czumaj
• Morteza Monemizadeh
• Krzysztof Onak
• Christian Sohler

We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O(√n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded- degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i. e. , bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

FOCS Conference 2011 Conference Paper

Streaming Algorithms via Precision Sampling

• Alexandr Andoni
• Robert Krauthgamer
• Krzysztof Onak

A technique introduced by Indyk and Woodruff (STOC 2005) has inspired several recent advances in data-stream algorithms. We show that a number of these results follow eas- ily from the application of a single probabilistic method called Precision Sampling. Using this method, we obtain simple data- stream algorithms that maintain a randomized sketch of an input vector x = (x 1, x 2, .. ., x n ), which is useful for the following applications: 1) Estimating the F k -moment of x, for k >; 2. 2) Estimating the ℓ p -norm of x, for p ϵ [1, 2], with small update time. 3) Estimating cascaded norms ℓp(ℓq) for all p, q >; 0. 4) ℓ 1 sampling, where the goal is to produce an element i with probability (approximately) |x i |/||x|| 1. It extends to similarly defined ℓ p -sampling, for p ϵ [1, 2]. For all these applications the algorithm is essentially the same: scale the vector x entry-wise by a well-chosen random vector, and run a heavy-hitter estimation algorithm on the resulting vector. Our sketch is a linear function of x, thereby allowing general updates to the vector x. Precision Sampling itself addresses the problem of estimating a sum Σ i=1 n a i from weak estimates of each real a i ϵ [0, 1]. More precisely, the estimator first chooses a desired precision u i ϵ (0, 1] for each i ϵ [n], and then it receives an estimate of every a i within additive u i. Its goal is to provide a good approximation to Σa i while keeping a tab on the "approximation cost" Σ i (1/u i )- Here we refine previous work (Andoni, Krauthgamer, and Onak, FOCS 2010) which shows that as long as Σa i = Ω(1), a good multiplicative approximation can be achieved using total precision of only O(n log n).

STOC Conference 2010 Conference Paper

Maintaining a large matching and a small vertex cover

• Krzysztof Onak
• Ronitt Rubinfeld

We consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of K updates in K*polylog(n) time, where n is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.

FOCS Conference 2010 Conference Paper

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

• Alexandr Andoni
• Robert Krauthgamer
• Krzysztof Onak

We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed ε >; 0, the algorithm computes a (log n) O(1/ε) approximation in n 1+ε time. This is an exponential improvement over the previously known approximation factor, 2 Õ (√log n), with a comparable running time [Ostrovsky and Rabani, J. ACM 2007; Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being “repetitive”, which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance.

STOC Conference 2009 Conference Paper

Approximating edit distance in near-linear time

• Alexandr Andoni
• Krzysztof Onak

We show how to compute the edit distance between two strings of length n up to a factor of 2 (O-tilde(sqrt(log n))) in n (1+o(1)) time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n (1/3+o(1)) approximation. Previously, approximation of 2 Õ √log n) was known only for embedding edit distance into l 1 , and it is not known if that embedding can be computed in less than a quadratic time.

FOCS Conference 2009 Conference Paper

Local Graph Partitions for Approximation and Testing

• Avinatan Hassidim
• Jonathan A. Kelner
• Huy N. Nguyen
• Krzysztof Onak

We introduce a new tool for approximation and testing algorithms called partitioning oracles. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only local computation to consistently answer queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges. We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance: 1. We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor. 2. We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model. 3. We prove that it is possible to approximate the distance to almost any hereditary property in any bounded degree hereditary families of graphs. Hereditary properties of interest include bipartiteness, k-colorability, and perfectness.

FOCS Conference 2008 Conference Paper

Constant-Time Approximation Algorithms via Local Improvements

• Huy N. Nguyen
• Krzysztof Onak

We present a technique for transforming classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. Our technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. The technique is based on greedily considering local improvements in random order. The problems amenable to our technique include Vertex Cover, Maximum Matching, Maximum Weight Matching, Set Cover, and Minimum Dominating Set. For example, for Maximum Matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by $d$, computes the maximum matching size to within $\eps n$, for any $\eps ≫ 0$, where $n$ is the number of nodes in the graph. The running time of the algorithm is independent of $n$, and only depends on $d$ and $\eps$.

SODA Conference 2008 Conference Paper

Finding an optimal tree searching strategy in linear time

• Shay Mozes
• Krzysztof Onak
• Oren Weimann

FOCS Conference 2008 Conference Paper

Sketching and Streaming Entropy via Approximation Theory

• Nicholas J. A. Harvey
• Jelani Nelson
• Krzysztof Onak

We give near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertions and deletions. This improves on prior results that obtain suboptimal space bounds in the general model, and near-optimal bounds in the insertion-only model without sketching. Our high-level approach is simple: we give algorithms to estimate Tsallis entropy, and use them to extrapolate an estimate of Shannon entropy. The accuracy of our estimates is proven using approximation theory arguments and extremal properties of Chebyshev polynomials. Our work also yields the best-known and near-optimal additive approximations for entropy, and hence also for conditional entropy and mutual information.

SODA Conference 2007 Conference Paper

Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems

• David R. Karger
• Krzysztof Onak

FOCS Conference 2007 Conference Paper

Testing for Concise Representations

• Ilias Diakonikolas
• Homin K. Lee
• Kevin Matulef
• Krzysztof Onak
• Ronitt Rubinfeld
• Rocco A. Servedio
• Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. 16 with ideas from learning theory, and yields property testers that make po! y(s/epsiv) queries (independent of n) for Boolean function classes such as s-term DNF formulas (answering a question posed by Parnas et al. [12]), sizes. decision trees, sizes Boolean formulas, and sizes Boolean circuits. The method can be applied to non-Boolean valued function classes as well. This is achieved via a generalization of the notion of van at ion/row Fischer et al. to non-Boolean functions. Using this generalization we extend the original junta test of Fischer et al. to work for non-Boolean functions, and give poly(s/e)-query testing algorithms for non-Boolean valued function classes such as sizes algebraic circuits and s-sparse polynomials over finite fields. We also prove an Omega(radic(s)) query lower bound for nonadaptively testing s-sparse polynomials over finite fields of constant size. This shows that in some instances, our general method yields a property tester with query complexity that is optimal (for nonadaptive algorithms) up to a polynomial factor.

FOCS Conference 2006 Conference Paper

Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders

• Krzysztof Onak
• Pawel Parys

We extend the binary search technique to searching in trees. We consider two models of queries: questions about vertices and questions about edges. We present a general approach to this sort of problem, and apply it to both cases, achieving algorithms constructing optimal decision trees. In the edge query model the problem is identical to the problem of searching in a special class of tree-like posets stated by Ben-Asher et al. (1999). Our upper bound on computation time, O(n 3 ), improves the previous best known O(n 4 log 3 n). In the vertex query model we show how to compute an optimal strategy much faster, in O(n) steps. We also present an almost optimal approximation algorithm for another class of tree-like (and forest-like) partial orders