66 citations · 126 across the 14 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.CC2009
Are stable instances easy?
Yonatan Bilu, Nathan Linial
We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. Th…
math.GT2009★ 1 cited
The expected genus of a random chord diagram
Nathan Linial, Tahl Nowik
To any generic curve in an oriented surface there corresponds an oriented chord diagram, and any oriented chord diagram may be realized by a curve in some oriented surface. The gen…
math.CO2009
Sum complexes - a new family of hypertrees
Nathan Linial, Roy Meshulam, Mishael Rosenthal
A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k-1)-dimensional skeleton and \binom{n-1}{k} facets such that H_k(X;Q)=0. Here we introduce the fo…