Sofya Vorotnikova

Publication Activity (10 Years)

Years Active: 2014-2021
Publications (10 Years): 17

Top Topics

General Conditions

Storage Capacity

Top Venues

IEEE Trans. Inf. Theory

Publications

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