Krzysztof Onak

Available identifiers

zbMath Open onak.krzysztofMaRDI QIDQ343846

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6147433	2024-01-15	Paper
https://portal.mardi4nfdi.de/entity/Q5002774	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
Sublinear Graph Approximation Algorithms	2010-10-12	Paper
Sublinear Algorithms in the External Memory Model	2010-10-12	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
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

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Krzysztof Onak