Fetching the paper…
Reading the bibliography…
In the communication problem $\mathbf{UR}$ (universal relation) [KRW95], Alice and Bob respectively receive $x$ and $y$ in $\{0,1\}^n$ with the promise that $x\neq y$.
Composition of the universal relation
Johan Håstad and Avi Wigderson · 1990
Earlier work this paper cites.
Monotone circuits for connectivity require super-logarithmic depth
Mauricio Karchmer and Avi Wigderson · 1990
Earlier work this paper cites.
Communication complexity towards lower bounds on circuit depth
Jack Edmonds, Russell Impagliazzo, Steven Rudich, and Jiri Sgall · 1991
Earlier work this paper cites.
Super-logarithmic depth lower bounds via the direct sum in communication complexity
Mauricio Karchmer, Ran Raz, and Avi Wigderson · 1995
Earlier work this paper cites.
The communication complexity of the universal relation
Gábor Tardos and Uri Zwick · 1997
Earlier work this paper cites.
An improved data stream algorithm for frequency moments
Don Coppersmith and Ravi Kumar · 2004
Earlier work this paper cites.
Summarizing and mining inverse distributions on data streams via dynamic inverse sampling
Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum · 2005
Earlier work this paper cites.
Sampling in dynamic data streams and applications
Gereon Frahling, Piotr Indyk, and Christian Sohler · 2005
Earlier work this paper cites.
Data Streams: Algorithms and Applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
Finding a duplicate and a missing item in a stream
Jun Tarui · 2007
Earlier work this paper cites.
Finding duplicates in a data stream
Parikshit Gopalan and Jaikumar Radhakrishnan · 2009
Earlier work this paper cites.
An optimal algorithm for the distinct elements problem
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Earlier work this paper cites.
1-pass relative-error l p l_{p} -sampling with applications
Morteza Monemizadeh and David P. Woodruff · 2010
Earlier work this paper cites.
Streaming algorithms via precision sampling
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak · 2011
Cited alongside, same era.
Tight bounds for Lp samplers, finding duplicates in streams, and related problems
Hossein Jowhari, Mert Sağlam, and Gábor Tardos · 2011
Cited alongside, same era.
Analyzing graph structure via linear measurements
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Cited alongside, same era.
Graph sketches: sparsification, spanners, and subgraphs
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Cited alongside, same era.
Spectral sparsification in dynamic graph streams
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2013
Cited alongside, same era.
A unifying framework for ℓ 0 \ell_{0} -sampling algorithms
Graham Cormode and Donatella Firmani · 2013
Cited alongside, same era.
Dynamic graph connectivity with improved worst case update time and sublinear space
David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn · 2015
Later among the works it cites.
Vertex and hyperedge connectivity in dynamic graph streams
Sudipto Guha, Andrew McGregor, and David Tench · 2015
Later among the works it cites.
Toward optimal bounds in the congested clique: Graph connectivity and MST
James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato · 2015
Later among the works it cites.
Maximum matching in turnstile streams
Christian Konrad · 2015
Later among the works it cites.
Densest subgraph in dynamic graph streams
Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu · 2015
Later among the works it cites.
An improved randomized data structure for dynamic graph connectivity
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Dynamic graph connectivity in polylogarithmic worst case time
Bruce M. Kapron, Valerie King, and Ben Mountjoy · 2013
Cited alongside, same era.
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson · 2014
Cited alongside, same era.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Cited alongside, same era.
Graph stream algorithms: a survey
Andrew McGregor · 2014
Cited alongside, same era.
Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis · 2015
Cited alongside, same era.
Sublinear estimation of weighted matchings in dynamic data streams
Marc Bury and Chris Schwiegelshohn · 2015
Cited alongside, same era.
Zhengyu Wang · 2015
Later among the works it cites.
Maximum matchings in dynamic graph streams and the simultaneous communication model
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev · 2016
Later among the works it cites.
Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova · 2016
Later among the works it cites.
Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity
Irit Dinur and Or Meir · 2016
Later among the works it cites.
Brief announcement: Applications of uniform sampling: Densest subgraph and beyond
Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff · 2016
Later among the works it cites.
Tight approximations of degeneracy in large graphs
Martin Farach-Colton and Meng-Tsung Tsai · 2016
Later among the works it cites.
Fast distributed algorithms for connectivity and MST in large graphs
Gopal Pandurangan, Peter Robinson, and Michele Scquizzato · 2016
Later among the works it cites.
On estimating maximum matching size in graph streams
Sepehr Assadi, Sanjeev Khanna, and Yang Li · 2017
Closest in time.