Research map / Learning theory and algorithms / Prediction and decision losses
Searching for and Avoiding Hidden Sets Using Queries with Local Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces local feedback and cluster avoidance into non-adaptive group testing, giving polynomial-time constructions of local selectors and local avoiding selectors with near-optimal query lengths plus matching-type lower bounds.
Problem
Non-adaptive group testing with the double-threshold (singleton) feedback where each non-hidden element must learn all hidden elements using only queries it belongs to, and additionally avoid interfering clusters; prior constructions were only existential.
Approach
Defines local selectors (LocS) and local avoiding selectors (LocAS) for group testing, and gives explicit polynomial-based constructions (with prime-number encodings for avoidance) whose lengths are polylogarithmically close to existential bounds and to lower bounds.
Key results
- Polynomial-time (n,k)-LocS of length O(k^3 log^2 n (log_k n + (log log n / log k)^2)), nearly matching the existential O(k^3 log n) bound.
- Polynomial-time (n,k,l)-LocAS of length O((k+l) l k^2 polylog(n)), close to the existential O((k+l) l k^2 log n) bound.
- Lower bounds: Omega(min{k^3 log_k n, kn}) for any (n,k)-LocS and Omega(l·min{k^3 log_k n, kn}) for any (n,k,l)-LocAS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add local learning to classic group testing | Group testing · (n,k)-LocS | number of queries: O(k2 log(n/k)) -> Ω(min{k3 logk n, kn}) | Hurt |
| Add avoidance of ℓ other clusters while requiring local learning | Local group testing · (n,k,ℓ)-LocAS | selector length: O((k + ℓ)ℓk2 log n); Ω(ℓ · min{k3 logk n, kn}) | Mixed |
| Use the polynomial-time construction instead of the probabilistic existence bound | (n,k)-LocS · (n,k)-LocS | selector length: O(k3 log n) -> O(k3 log2 n(logk n + (log log n/ log k)2)) | Hurt |
| Use the polynomial-time construction instead of the probabilistic existence bound | (n,k,ℓ)-LocAS · (n,k,ℓ)-LocAS | selector length: O((k + ℓ)ℓk2 log n) -> O((k + ℓ)k2ℓ · polylog(n, k, ℓ)) | Hurt |
| Increase constant c to tolerate α adversarially altered feedback positions | LocS and LocAS constructions · Fault-prone testing | selector length: ⌈α/(kd)⌉ | Hurt |
| Increase constant c to provide more witnessed columns and decode with beeping feedback | LocS and LocAS constructions · Beeping feedback | selector length | No clear effect |
Surprising findings
- Local learning requires substantially more queries than classic group testing (super-cubic in k versus O(k^2 log n) for classic selectors).
Limitations
- Polylogarithmic gaps remain between the upper and lower bounds.
- Byzantine adversarial settings with more than O(k log_k n) faults remain open.
- Full proofs are deferred to a full version not included here.
Experimental setup
Metrics: query sequence length (asymptotic)
Baselines: existential LocS bound (Jurdzinski et al. 2018) existential LocAS bound (Jurdzinski et al. 2018) product of classic selectors
Builds on: classic group testing selectors witnessed strong selectors (Jurdzinski et al. 2018)
Closest papers by meaning
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.84)
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.84)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.82)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.82)
- Limited Query Graph Connectivity Test (AAAI 2024 · similarity 0.82)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.