From 4e12190e94c4a3e1e5fcd4a59db94bbe4222eae3 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 5 Feb 2015 20:54:06 -0500
Subject: Intro

---
 paper/sections/abstract.tex | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

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

diff --git a/paper/sections/abstract.tex b/paper/sections/abstract.tex
index ad5b893..a07228f 100644
--- a/paper/sections/abstract.tex
+++ b/paper/sections/abstract.tex
@@ -1,10 +1,11 @@
 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.
+and provide the first algorithm which recovers the graph's 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 prove an almost matching lower bound of
-$\Omega(s\log\frac{m}{s})$.
+$\Omega(s\log\frac{m}{s})$ and validate our approach empirically on synthetic
+graphs.
-- 
cgit v1.2.3-70-g09d2

