- Densest Subgraph with Strong and Weak Signals
- Project Year:
2024
- REU Student (s):
Eli Friedman | Dartmouth College NH
- Student 1 Institution:
Dartmouth College
- Project Mentor:
Shahrzad Haddadan
- Project Mentor Area:
Management Sciences and Information Systems
- Project Abstract:
We consider the problem of identifying the densest subgraph, one with many applications, in a novel computational setting in which we have access to only a noisy graph signal and limited queries to a strong oracle. Our algorithms solve this problem when the density of the densest subgraph is asymptotically larger than the noise of the weak signal. When the noise in the weak signal is small and the maximum density is Ω(log n), we show an algorithm that achieves a constant approximation guarantee. Alternatively, when the noise is large, we are only able to design an algorithm whose additive approximation guarantee deteriorates with the magnitude of noise. We conjecture that no algorithm can be designed to circumvent this difficulty without excessive use of the strong oracle.
