Darya Melnyk

Darya Melnyk

Auto-generated profile, based on publicly available information

Darya Melnyk

TU Berlin, Berlin, Germany

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 June 2025
Verified
Conference Paper
Open access
AAAmirreza Akbari
Amirreza Akbari
XCXavier Coiteux-Roy
Xavier Coiteux-Roy
FDFrancesco D'AMore
Francesco D'AMore
François Le GallFrançois Le Gall
François Le Gall
HLHenrik Lievonen
Henrik Lievonen
JSJukka Suomela
Jukka Suomela

25 June 2022
Verified
Book Chapter
Closed access
PDF file
ABAlkida Balliu
Alkida Balliu
JHJuho Hirvonen
Juho Hirvonen
DMDarya Melnyk
Darya Melnyk
DODennis Olivetti
Dennis Olivetti
JRJoel Rybicki
Joel Rybicki
JSJukka Suomela
Jukka Suomela

24 August 2025
Verified
Conference Paper
Open access
MCMelanie Cambus
Melanie Cambus
DMDarya Melnyk
Darya Melnyk
TMTijana Milentijevic
Tijana Milentijevic
SSStefan Schmid
Stefan Schmid

4 March 2026 in SSRN Electronic Journal
Verified
Preprint
Open access
MCMelanie Cambus
Melanie Cambus
DMDarya Melnyk
Darya Melnyk
In this paper, we present distributed fault-tolerant algorithms that approximate the centroid (i.e., the average) of a set of n data points in R d . Our work falls into the broader area of multidimensional Byzantine approximate agreement. We show that state-of-the-art algorithms, such as agreeing inside the convex hull of all non-faulty vectors, or minimum-diameter averaging (MDA), in the worst case either prevent us from agreeing on a vector close to the centroid (in terms of approximation quality), or allow Byzantine parties to influence the output considerably (in terms of validity). To design better approximation algorithms, we propose a novel concept of defining an approximation ratio of the centroid by including the vectors of the Byzantine adversaries in the definition. We analyze the algorithms in the synchronous and asynchronous models of communication with public communication channels. We show that the standard agreement algorithms based on agreeing inside the convex hull of all non-faulty vectors do not allow us to compute a better approximation than 2d of the centroid. On the other hand, MDA can be used to achieve constant approximation at the cost of only satisfying strong validity. As a trade-off, we develop an approach that reaches a 2 √ d-approximation of the centroid, while satisfying box validity. Our approach provides optimal resilience, allowing up to t < n/3 faulty nodes.

16 July 2025
Verified
Conference Paper
Open access
MCMélanie Cambus
Mélanie Cambus
DMDarya Melnyk
Darya Melnyk
TMTijana Milentijević
Tijana Milentijević
SSStefan Schmid
Stefan Schmid

14 September 2021 in arXiv
Verified
Preprint
Open access
PDF file
ABAlkida Balliu
Alkida Balliu
JHJuho Hirvonen
Juho Hirvonen
DMDarya Melnyk
Darya Melnyk
DODennis Olivetti
Dennis Olivetti
JRJoel Rybicki
Joel Rybicki
JSJukka Suomela
Jukka Suomela
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to "patch a hole." We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(\log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $\Pi$ can be solved in $O(\log^* n)$, there is always a restriction $\Pi' \subseteq \Pi$ that is still efficiently solvable but that is also $O(1)$-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $\Theta(\log n)$, or $\Theta(n)$, while in general graphs the structure is much more diverse.