From 97be51465ace29afdea41e9d80fea7b6c344bdda Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 1 Feb 2015 17:47:12 -0500
Subject: Abstract + first polishing pass over the intro

---
 paper/sections/abstract.tex | 10 ++++++++++
 1 file changed, 10 insertions(+)
 create mode 100644 paper/sections/abstract.tex

(limited to 'paper/sections/abstract.tex')

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})$.
-- 
cgit v1.2.3-70-g09d2

