Sofya Vorotnikova

18 papers A* 5A 1B 1Journal 8Unranked 3
YearRankTypeTitle / Venue / Authors
2021 J jnl
Vertex Ordering Problems in Directed Graph Streams.
CoRR
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
2020 J jnl
Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming.
CoRR
Sofya Vorotnikova
2020 A* conf
Triangle and Four Cycle Counting in the Data Stream Model.
PODS
Andrew McGregor, Sofya Vorotnikova
2020 A* conf
Vertex Ordering Problems in Directed Graph Streams.
SODA
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
2019 J jnl
Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.
IEEE Trans. Inf. Theory
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2019 J jnl
Structural Results on Matching Estimation with Applications to Streaming.
Algorithmica
Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou
2019 A* conf
The Complexity of Counting Cycles in the Adjacency List Streaming Model.
PODS
John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova
2018 — conf
A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.
SOSA
Andrew McGregor, Sofya Vorotnikova
2017 J jnl
Storage Capacity as an Information-Theoretic Analogue of Vertex Cover.
CoRR
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2017 B conf
Storage capacity as an information-theoretic analogue of vertex cover.
ISIT
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2016 J jnl
A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs.
CoRR
Andrew McGregor, Sofya Vorotnikova
2016 A* conf
Better Algorithms for Counting Triangles in Data Streams.
PODS
Andrew McGregor, Sofya Vorotnikova, Hoa T. Vu
2016 A* conf
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.
SODA
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova
2016 — conf
Planar Matching in Streams Revisited.
APPROX-RANDOM
Andrew McGregor, Sofya Vorotnikova
2015 — conf
Densest Subgraph in Dynamic Graph Streams.
MFCS (2)
Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu
2015 J jnl
Densest Subgraph in Dynamic Graph Streams.
CoRR
Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu
2015 J jnl
Kernelization via Sampling with Applications to Dynamic Graph Streams.
CoRR
Rajesh Hemant Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova
2014 A conf
Trace Reconstruction Revisited.
ESA
Andrew McGregor, Eric Price, Sofya Vorotnikova