Krzysztof Onak

Available identifiers

zbMath Open onak.krzysztofMaRDI QIDQ343846

List of research outcomes

Publication	Date of Publication	Type
Adversarially robust streaming via dense-sparse trade-offs	2024-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q6147433	2024-01-15	Paper
Fully dynamic MIS in uniformly sparse graphs	2021-07-28	Paper
Fully Dynamic MIS in Uniformly Sparse Graphs	2021-05-03	Paper
Walking randomly, massively, and efficiently	2021-01-19	Paper
Round Compression for Parallel Matching Algorithms	2020-10-29	Paper
Planar graphs: Random walks and bipartiteness testing	2019-10-16	Paper
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time	2019-10-15	Paper
The query complexity of graph isomorphism: bypassing distribution testing lower bounds	2019-08-22	Paper
Round compression for parallel matching algorithms	2019-08-22	Paper
Fully dynamic maximal independent set with sublinear update time	2019-08-22	Paper
https://portal.mardi4nfdi.de/entity/Q5743463	2019-05-10	Paper
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond	2019-03-28	Paper
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond	2017-10-05	Paper
Fat polygonal partitions with applications to visualization and embeddings	2017-03-09	Paper
Superlinear lower bounds for multipass graph processing	2016-11-29	Paper
Parallel algorithms for geometric graph problems	2015-06-26	Paper
Approximating edit distance in near-linear time	2015-02-04	Paper
https://portal.mardi4nfdi.de/entity/Q2934716	2014-12-18	Paper
Maintaining a large matching and a small vertex cover	2014-08-13	Paper
Streaming Algorithms via Precision Sampling	2014-07-30	Paper
Planar Graphs: Random Walks and Bipartiteness Testing	2014-07-30	Paper
Local Graph Partitions for Approximation and Testing	2014-07-25	Paper
Approximating Edit Distance in Near-Linear Time	2013-03-19	Paper
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs	2011-08-17	Paper
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity	2010-10-12	Paper
Dynamic Approximate Vertex Cover and Maximum Matching	2010-10-12	Paper
Sublinear Graph Approximation Algorithms	2010-10-12	Paper
Sublinear Algorithms in the External Memory Model	2010-10-12	Paper
https://portal.mardi4nfdi.de/entity/Q3579429	2010-08-06	Paper
The Oil Searching Problem	2009-10-29	Paper
External Sampling	2009-07-14	Paper
https://portal.mardi4nfdi.de/entity/Q3602898	2009-02-12	Paper
Testing Properties of Sets of Points in Metric Spaces	2008-08-28	Paper

Research outcomes over time

This page was built for person: Krzysztof Onak