Learning Erdos-Renyi Random Graphs via Edge Detecting Queries
Authors: Zihan Li, Matthias Fresacher, Jonathan Scarlett
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complement our theoretical findings with numerical experiments comparing COMP, DD, SSS, and a linear programming (LP) relaxation of SSS (analogous to [34]).5 Figure 2 shows the success probability as a function of the number of tests in two cases: (i) n = 50 and k = 5; (ii) n = 200 and k = 200. In each case, we set ν = 1 and compute the error probability averaged over 2000 trials. |
| Researcher Affiliation | Academia | Zihan Li National University of Singapore lizihan@u.nus.edu Matthias Fresacher University of Adelaide matthias.fresacher@adelaide.edu.au Jonathan Scarlett National University of Singapore scarlett@comp.nus.edu.sg |
| Pseudocode | Yes | Algorithm 1 Combinatorial Orthogonal Matching Pursuit (COMP) Algorithm 2 Definite Defectives (DD) Algorithm 3 Smallest Satisfying Set (SSS) Algorithm 4 Group Testing Quick and Efficient (GROTESQUE) Informal Outline |
| Open Source Code | Yes | 5The code is available at https://github.com/scarlett-nus/er_edge_det. |
| Open Datasets | No | The paper uses the Erd os-Rényi random graph model to generate graphs for its experiments, rather than relying on an external, pre-existing publicly available dataset. Therefore, no specific information about public dataset access is provided. |
| Dataset Splits | No | The numerical experiments are based on simulated data generated from the Erd os-Rényi random graph model with specified parameters (e.g., n=50, k=5). The concept of training/validation/test splits, as typically applied to fixed datasets, is not applicable or mentioned in this simulation context. |
| Hardware Specification | No | The paper mentions numerical experiments but does not provide any specific details about the hardware used to run them. |
| Software Dependencies | No | The paper does not explicitly provide specific version numbers for any software dependencies (e.g., programming languages, libraries, or solvers) used for the experiments. |
| Experiment Setup | Yes | In each case, we set ν = 1 and compute the error probability averaged over 2000 trials. |