23 citations · 58 across the 13 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.CC2018★ 8 cited
Streaming Hardness of Unique Games
Venkatesan Guruswami, Runzhou Tao
We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by , the alphabet size of t…
cs.DS2018★ 5 cited
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang +3
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive on…