23 citations · 74 across the 22 of their papers we have counts for
4 papers · 2 filters
Testing -Monotonicity
Clément L. Canonne, Elena Grigorescu, Siyao Guo +2
A Boolean -monotone function defined over a finite poset domain alternates between the values and at most times on any ascending chain in . Ther…
Streaming Weighted Matchings: Optimal Meets Greedy
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph are revealed in a streaming fashion. We analyze a vari…
Local Testing for Membership in Lattices
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota +1
Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study o…
Estimating Weighted Matchings in Space
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of estimating the weight of a maximum weighted matching of a weighted graph whose edges are revealed in a streaming fashion. We develop a reduction…