21 citations · 47 across the 19 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
On the hardness of learning sparse parities
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal +1
This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equa…
cs.DS2015
On the Approximability of Digraph Ordering
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit +1
Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling maximizing the number of forward edges, i.e. edges (u,v) such that $\ell…