Sofya Vorotnikova

According to our database, Sofya Vorotnikova authored at least 15 papers between 2014 and 2020.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2020

Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming.

Sofya Vorotnikova

CoRR, 2020

Vertex Ordering Problems in Directed Graph Streams.

Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Triangle and Four Cycle Counting in the Data Stream Model.

Andrew McGregor, Sofya Vorotnikova

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

2019

Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.

Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova

IEEE Trans. Inf. Theory, 2019

Structural Results on Matching Estimation with Applications to Streaming.

Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou

Algorithmica, 2019

The Complexity of Counting Cycles in the Adjacency List Streaming Model.

John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

2018

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.

Andrew McGregor, Sofya Vorotnikova

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

2017

Storage capacity as an information-theoretic analogue of vertex cover.

Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

2016

A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs.

Andrew McGregor, Sofya Vorotnikova

CoRR, 2016

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, Sofya Vorotnikova

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Better Algorithms for Counting Triangles in Data Streams.

Andrew McGregor, Sofya Vorotnikova, Hoa T. Vu

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Planar Matching in Streams Revisited.

Andrew McGregor, Sofya Vorotnikova

Proceedings of the Approximation, 2016

2015

Kernelization via Sampling with Applications to Dynamic Graph Streams.

Rajesh Hemant Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova

CoRR, 2015

Densest Subgraph in Dynamic Graph Streams.

Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

Trace Reconstruction Revisited.

Andrew McGregor, Eric Price, Sofya Vorotnikova

Proceedings of the Algorithms - ESA 2014, 2014