Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G = (V, E) and sensitivity parameter f such that, for any set F V E of up to f link or node failures, it can report the solution of Π in G F. We study three network problems Π. ... Our main technical contribution is a new construction of (L, f)-replacement path coverings ((L, f)-RPC)... From this construction, we derive oracles for L-HOP SHORTEST PATH, k-PATH, and k-CLIQUE. Notably, our solution for k-PATH improves the query time of the one by Bil o et al. (2022a) for f = o(log k). ... This proves Theorem 1 for the case of link failures. |
| Researcher Affiliation | Academia | Davide Bil o1, Keerti Choudhary2, Sarel Cohen3, Tobias Friedrich4, Martin Schirneck5 1Department of Information Engineering, Computer Science and Mathematics, University of L Aquila, Italy 2Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India 3School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel 4Hasso Plattner Institute, University of Potsdam, Germany 5Faculty of Computer Science, University of Vienna, Austria |
| Pseudocode | Yes | Algorithm 1: Query algorithm. 2 for i = 0 to K 1 do 3 x root of Ti; 4 while x is not a leaf do 5 no Child Found TRUE; 6 forall children y of x do 7 if F Ay then 9 no Child Found FALSE; 10 break inner for-loop; 11 if no Child Found then 12 continue outer for-loop; 13 GF GF {Gx}; |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide a link to a code repository. It focuses on theoretical contributions. |
| Open Datasets | No | The paper does not mention using any specific public or open datasets for empirical evaluation. It describes theoretical algorithms for network problems. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running experiments, as its focus is on theoretical algorithmic contributions. |
| Software Dependencies | No | The paper discusses algorithms and theoretical concepts without mentioning specific software libraries or their version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper is a theoretical work focusing on algorithm design and analysis, and therefore does not provide details regarding experimental setup, hyperparameters, or training configurations. |