Abstract + first polishing pass over the intro

1 files changed, 10 insertions, 0 deletions

diff --git a/paper/sections/abstract.tex b/paper/sections/abstract.tex
new file mode 100644
index 0000000..9136be7
--- /dev/null
+++ b/paper/sections/abstract.tex
@@ -0,0 +1,10 @@
+In the Graph Inference problem, one seeks to recover the edges of an unknown
+graph from the observations of influence cascades propagating over this graph.
+In this paper, we approach this problem from the sparse recovery perspective
+and provide an algorithm which recovers the graph edges with high probability
+provided that the number of measurements is $\Omega(s\log m)$ where $s$ is the
+maximum degree of the graph and $m$ is the number of nodes.
+Furthermore, we show that our algorithm also recovers the edge weights (the
+parameters of the diffusion process) and is robust in the context of
+approximate sparsity. Finally we provide an almost matching lower bound of
+$\Omega(s\log\frac{m}{s})$.