33 citations · 38 across the 4 of their papers we have counts for
7 papers
A Simple Phase-King Protocol with Predictions
Antonia Giannoulea, George Papadoulis, Nikos Leonardos +1
Inspired by recent work (Ben-David, Dzulfikar, Ellen, and Gilbert, , PODC 2025) we study synchronous binary Byzantine Agreement in th…
Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos +5
The Subset Sum Ratio problem (SSR) asks, given a multiset of positive integers, to find two disjoint subsets of such that the largest-to-smallest ratio of their sums is min…
Lower bounds for uniform read-once threshold formulae in the randomized decision tree model
Nikos Leonardos
We investigate the randomized decision tree complexity of a specific class of read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, every in…
Minotaur: Multi-Resource Blockchain Consensus
Matthias Fitzi, Xuechao Wang, Sreeram Kannan +4
Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engage…
Oceanic Games: Centralization Risks and Incentives in Blockchain Mining
Nikos Leonardos, Stefanos Leonardos, Georgios Piliouras
To participate in the distributed consensus of permissionless blockchains, prospective nodes -- or miners -- provide proof of designated, costly resources. However, in contrast to…
Stable Matching with Evolving Preferences
Varun Kanade, Nikos Leonardos, Frédéric Magniez
We consider the problem of stable matching with dynamic preference lists. At each time step, the preference list of some player may change by swapping random adjacent members. The…
Hellinger volume and number-on-the-forehead communication complexity
Troy Lee, Nikos Leonardos, Michael Saks +1
Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party…