Bibliographic record
Abstract
Finding the Minimum Spanning Tree or Forest (MSF) of a weighted graph is one of the most fundamental graph problems. It has many applications, and there are various algorithms to solve it in quasi-linear time. However, in a secure computation setting where the graph is shared between multiple parties, there are no fully satisfactory solutions. Any prior work on this problem either builds a circuit that is fed into a generic multi-party computation protocol, or is limited to graphs that have a unique MSF. In this work, we first identify privacy and fairness issues that arise when the MSF is not necessarily unique, i.e., there exist duplicate edge weights. Subsequently, we consider the notion of a Random Minimum Spanning Forest, which defines a distribution of the desired output in the case where multiple MSFs exist. We carefully design a protocol for this problem in the semi-honest security model. The main insight of our protocol is that we may reveal certain intermediate results over the entire course of the protocol execution (provably without impacting security), which are then used to make decisions that optimize efficiency. No party learns anything about the inputs of other parties except for the produced MSF, not even the number of input edges. Furthermore, the number of communication rounds is low for many typical graphs, which allows running the protocol even when the network latency is high. Our evaluation shows that, depending on the graph structure and its weight distribution, our protocol can outperform the previous baseline by Laud (PoPETs 2015) by up to 2-3 orders of magnitude in terms of running time. From another perspective, this work exposes some disadvantages of using generic compilers to obtain MPC protocols, as their efficiency always equal that of the worst-case input. Our techniques show that even within the context of MPC, it is possible to obtain a secure protocol whose running time is not fixed a-priori, but instead determined by the output that is not known in advance. By carefully studying the desired functionality, this allows for significant efficiency improvements for any realistic inputs.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.003 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.001 | 0.001 |
| Open science | 0.003 | 0.002 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".