Sofya Raskhodnikova

• ACM Transactions on Computation Theory;
• Algorithmica.

• CSR 2022 conference, a satellite event for the International Congress of Mathematicians (ICM2022) (June 2022, planed in Saint Petersburg, Russia, but moved online)
• WOLA 2021, June, 2021
• RANDOM 2013 (August 21-23 2013, UC Berkeley, California)

• STOC 2025 (June 23-27, 2025, Prague, Czech Republic)
• TPDP 2024 (August 20-21, 2024, Boston, Massachusetts)
• FORC 2024 (June 12-14, 2024, Boston, Massachusetts)
• FOCS 2023 (November 6-9, 2023, Santa Cruz, California)
• ITCS 2022 (January 31-February 3, 2022, Berkeley, California)
• CSR 2021 (June 28–July 2, 2021, Sochi, Russia or online)
• STOC 2020 (June 22-26, 2020, Chicago, IL or online)
• RANDOM 2019 (September 20-22, 2019, MIT)
• ITCS 2019 (January 10-12, 2019, San Diego, California)
• FOCS 2017 (October 15-17, 2017, Berkeley, California)
• STOC 2016 (June 19-21, 2016, Cambridge, MA)
• FOCS 2012 (October 20-23, 2012, New Brunswick, New Jersey)
• SWAT 2012 (July 4-6, 2012, Helsinki, Finland)
• FOCS 2010 (October 23-26, 2010, Las Vegas, Nevada)
• RANDOM 2010 (September 1-3, 2010, Barcelona)
• SODA 2010 (January 17-19, 2010, Austin,Texas)
• RANDOM 2007 (August 20-22, 2007, Princeton University)

• 4th TCS Women meeting at STOC 2021, June 22, 2021.
• 3rd TCS Women meeting at STOC 2020, June 25, 2020.
• 2nd TCS Women meeting at STOC 2019, June 26, 2019.
• Inaugural TCS Women meeting at STOC 2018 Theory Fest, June 26, 2018.
• Sublinear 2016 workshop at Johns Hopkins University, January 7-9, 2016.
• Mike Fest, a Symposium on Theoretical Computer Science on the occasion of Michael Sipser's 60th Birthday, October 26, 2014.
• Sublinear Algorithms 2014 at Bertinoro, May 25-29, 2014.
• Charles River Workshop on Private Analysis of Social Networks, May 19, 2014.
• Charles River Privacy Day, November 15, 2013.

• Sigma camp: lecture in 2020, faculty in 2021, 2022, 2023, 2024; helping with Problem of the Month (POM) contest in 2021-2024.
• Guest lecturer and panelist at Artemis (CS summer camp at BU) in 2023, 2024.
• Instructor for Berkeley Math Circle, spring 2019.
• First EECS PSU summer camp: Girls Solving Societal Problems Through Computer Science, 2017. Video
• C.A.M.P., 2017.
• Epsilon camp, 2016.

• SICOMP for the Special Issue on FOCS 2017;
• Theory of Computing (an open access journal) for the Special Issue on APPROX-RANDOM 2013.

Postdocs

• Esty Kelman (from January 2023)
• Talya Eden (2021--2022)

Current Ph.D. Students

• Ephraim Linder (co-advised with Adam Smith)
• Debanuj Nayak
• Diptaksho Palit
• Anatoly Zavyalov

Alumni

• Iden Kalemaj (Ph.D. `24, Boston University, now at Meta Research)
• Ludmila Glinskih (Ph.D. `24, Boston University, co-advised with Mark Bun, now at Google)
• Ramesh Krishnan S. Pallavoor (Ph.D. `20, Boston University, now at Google)
• Nithin Varma (Ph.D. `19, Boston University, first position after graduation: postdoc at the University of Haifa, then an Assistant Professor at the Chennai Mathematical Institute, now at Max Planck Institute for Informatics)
• Meiram Murzabulatov (Ph.D. `17, Penn State, was an Assistant Teaching Professor at Penn State, now an Assistant Professor at Nazarbayev University)
• Kashyap Dixit (Ph.D. '15, Penn State, co-advised with Martin Fürer)
• Grigory Yaroslavtsev (Ph.D. '14, Penn State, first position after graduation: postdoc at Brown University, then an Assistant Professor at Indiana University, now faculty at George Mason)
• Madhav Jha (M.S. '10, Ph.D. '13, Penn State, first position after graduation: postdoc at Sandia National Labs, now at Sigma computing)


• Roksana Baleshzar (M.S. `17, Penn State, now at Google)


• Edward Lu (B.S. Honor's Thesis `13, Penn State)
• Ishan Behoora, research intern, Spring '10, Penn State
• Olena Melnychenko, research assistant, B.S. '09, Penn State

Publications

(presented in reverse chronological order of their initial publication)

• Fully Dynamic Graph Algorithms with Edge Differential Privacy, Sofya Raskhodnikova, Teresa Steiner. Manuscript.
  Arxiv version
• Local Lipschitz Filters for Bounded-Range Functions, Jane Lange, Ephraim Linder, Sofya Raskhodnikova, Arsen Vasilyan. Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
  Arxiv version
• Property testing with online adversaries, Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova. Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS), 2024.
  Arxiv version
• Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation, Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Proceedings of 37th Conference on Neural Information Processing Systems, NeurIPS 23, 2023.
  Arxiv version
  Poster
• Testing Connectedness of Images, Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, and Dragos-Florian Ristache. Algorithmica 2024.
  Preliminary version appeared in Proceedings of the 26th RANDOM, 66:1--66:15, 2023.
  Arxiv version
• Triangle Counting with Local Edge Differential Privacy, Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith. Proceedings of 50th International Colloquium on Automata, Languages, and Programming (ICALP),52:1--52:21, 2023.
  Arxiv version
  Slides
• The Price of Differential Privacy under Continual Observation, Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. ICML 2023.
  Arxiv version
  Selected for presentation at ICML and FORC 2023. Selected talk at TPDP 2022.
  Slides
• Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity TestingIsoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing, Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Random Structures and Algorithms, volume 65, 191-219, 2024.
  Preliminary version appeared in Proceedings of 50th International Colloquium on Automata, Languages, and Programming (ICALP), 25:1--25:20, 2023.
  Arxiv version
  Slides
• Node-Differentially Private Estimation of the Number of Connected Components, Iden Kalemaj, Sofya Raskhodnikova, Adam Smith, Charalampos Tsourakakis. Proceedings of the Principles of Database Systems (PODS), 183-194, 2023.
  Arxiv version
  Selected for presentation at FORC 2023.
• Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Outdegree Ordering, and Densest Subgraphs, Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), 754-765, 2022.
  Arxiv version
• Sublinear-Time Computation in the Presence of Online Erasures, Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma. Theory of Computing 19(1), 1--48, 2023.
  Preliminary version appeared in Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), 90:1-90:25, 2022.
  Arxiv version
• Differentially Private Sampling from Distributions, Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, Marika Swanberg. Proceedings of the Advances in Neural Information Processing Systems 34 (NeurIPS 2021), 28983-28994, 2021. Selected talk at TPDP 2021.
• Erasure-Resilient Sublinear-Time Graph Algorithms, Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma. ACM Trans. Comput. Theory 14(1): 1:1-1:22, 2022.
  Preliminary version appeared in Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), 80:1-80:20, 2021.
• Approximating the Distance to Monotonicity of Boolean Functions, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten. Random Structures and Algorithms, volume 60, 233-260, 2022.
  Preliminary version appeared in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995-2009, 2020.
• Erasures vs. Errors in Local Decoding and Property Testing, Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma. Random Structures and Algorithms, volume 59, 640– 670, 2021.
  Preliminary version appeared in the Proceedings of the 10th Innovations in Theoretical Computer Science (ITCS) conference, 63:1-63:21, 2019.
  Slides
  Video of my talk at the Simons Institute workshop on Sublinear Algorithms and Nearest-Neighbor Search
• Bipartite Graphs of Small Readability, Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova and Nithin Varma. Theoretical Computer Science, 806: 402-415, 2020.
  Preliminary version appeared in Proceedings of Computing and Combinatorics -- 24th International Conference (COCOON 2018), 467-479, 2018.
• Brief Announcement: Erasure-Resilience versus Tolerance to Errors, Sofya Raskhodnikova and Nithin Varma. Proceedings of 45th International Colloquium on Automata, Languages, and Programming (ICALP), 111:1-111:3, 2018.
• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps, Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri. Theory of Computing, 16 (3), 1-36, 2020.
  Preliminary version appeared in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 5:1-5:14, 2017.
• A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube, Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri. Arxiv, 2017.
• Parameterized Property Testing of Functions, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma. ACM Transactions on Computation Theory (TOCT) 9(4): 17:1-17:19, 2018.
  Preliminary version appeared in Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) conference, 12:1-12:17, 2017.
• Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism, Sofya Raskhodnikova and Adam Smith. Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 495-504, 2016.
• The Power and Limitations of Uniform Samples in Testing Properties of Figures, Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova. Algorithmica, 2018.
  Preliminary version appeared in Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 45:1-45:14, 2016.
• Erasure-Resilient Property Testing, Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma. SIAM J. Computing, 47(2), 295–329, 2018.
  Preliminary version appeared in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 91:1-91:15, 2016.
  Slides
• Tolerant Testers of Image Properties, Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova. ACM Transactions on Algorithms, 18(4): 37:1-37:39, 2022.
  Preliminary version appeared in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 90:1-90:14, 2016.
• Testing Convexity of Figures Under the Uniform Distribution, Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova. Random Structures and Algorithms, 2018.
  Preliminary version appeared in Proceedings of the 32nd International Symposium on Computational Geometry (SoCG), 17:1-17:15, 2016.
• Testing if an Array Is Sorted, Sofya Raskhodnikova. Encyclopedia of Algorithms, 2015. Springer link
• Differentially Private Analysis of Graphs, Sofya Raskhodnikova and Adam Smith. Encyclopedia of Algorithms, 2015. Springer link
• Linearity and Group Homomorphism Testing / Testing Hadamard Codes, Sofya Raskhodnikova and Ronitt Rubinfeld. Encyclopedia of Algorithms, 2015. Springer link
• On the Readability of Overlap Digraphs, Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova. Descrete Applied Mathematics 205: 35-44, 2016.
  Preliminary version appeared in Proceedings of Combinatorial Pattern Matching--26th Annual Symposium (CPM), 124-137, 2015.
• L_p-testing, Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of 46th ACM Symposium on the Theory of Computing (STOC), 164-173, 2014.
• Lower Bounds for Testing Properties of Functions on Hypergrid Domains, Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of the 29th IEEE Conference on Computational Complexity (CCC), 309-320, 2014.
  Preliminary version appeared in ECCC, TR13-036, 2013.
• Analyzing Graphs with Node Differential Privacy, Shiva Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. Proceedings of the 10th Theory of Cryptography Conference (TCC), 457-476, 2013.
  Slides
• Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy, Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova and Abhradeep Thakurta. Proceedings of the 10th Theory of Cryptography Conference (TCC), 418-436, 2013.
• Learning Pseudo-Boolean k-DNF and Submodular Functions, Sofya Raskhodnikova and Grigory Yaroslavtsev. Proceedings of the 24th ACM-SIAM SODA, 1356-1368, 2013.
• Testing Lipschitz Functions on Hypergrid Domains, Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova. Algorithmica 74(3): 1055-1081, 2016.
  Preliminary version appeared in Proceedings of the 15th RANDOM, Springer-Verlag, 387-398, 2012.
• Limitations of Local Filters of Lipschitz and Monotone Functions, Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova. ACM Transactions on Computation Theory, 7(1): 2:1-2:16, 2014.
  Preliminary version appeared in Proceedings of the 15th RANDOM, Springer-Verlag, 374-386, 2012.
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy, Madhav Jha and Sofya Raskhodnikova. SIAM Journal on Computing, 42(2), 700-731, 2013.
  Preliminary version appeared in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 433-442, 2011.
  Slides
• Private Analysis of Graph Structure, Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev. Proceedings of the Thirty-Seventh International Conference on Very Large Data Bases (VLDB), 1146-1157, 2011.
• Approximation Algorithms for Spanner Problems and Directed Steiner Forest, Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev. Information and Computation, 222, 93-107, 2013. (ICALP 2011 special issue).
  Preliminary version entitled "Improved Approximation for the Directed Spanner Problem" appeared in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 1-12, 2011.
• Steiner Transitive-Closure Spanners of Low-Dimensional Posets, Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, Grigory Yaroslavtsev. Combinatorica 34(3): 255-277 (2014)
  Preliminary version appeared in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 760-772, 2011.
• Transitive-Closure Spanners: a Survey, Sofya Raskhodnikova. In O. Goldreich, editor, Property Testing, LNCS 6390, LNCS State-of-the-Art Surveys, Springer, Heidelberg, 167-196, 2010.
  Slides
• Finding Sparser Directed Spanners, Piotr Berman, Sofya Raskhodnikova, Ge Ruan. Proceedings of the 30th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 424-435, 2010.
• Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners, Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David Woodruff. SIAM J. Discrete Math., 26(2), 618-646, 2012.
  Preliminary version appeared in Proceedings of the 14th RANDOM, Springer-Verlag, 448-461, 2010.
• Approximation Algorithms for Min-Max Generalization Problems, Piotr Berman and Sofya Raskhodnikova. ACM Transactions on Algorithms, 11(1): 5:1-5:23, 2014.
  Preliminary version in Proceedings of the 13th APPROX, Springer-Verlag, 53-66, 2010.
  Slides
• Transitive-Closure Spanners of the Hypercube and the Hypergrid, Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, Electronic Colloquium on Computational Complexity, TR09-046, 2009.
• Transitive-Closure Spanners, Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, SIAM Journal on Computing, 41(6), pp. 1380-1425, 2012.
  Preliminary version appeared in Proceedings of the 20th ACM-SIAM SODA, 531-540, 2009.
  Slides
• What Can We Learn Privately? Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith. SIAM Journal on Computing, 40(3), pp. 793-826, 2011 (FOCS 2008 special issue).
  Preliminary version appeared in Proceedings of the 49th IEEE FOCS, 531-540, 2008.
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem, Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith, SIAM Journal on Computing, 39(3):813-842, 2009.
  Preliminary version appeared in Proceedings of the 48th IEEE FOCS, 559-569, 2007.
• Smooth sensitivity and sampling in private data analysis, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith, Proceedings of the 39th ACM STOC, 75-84, 2007.
  Slides
• Sublinear Algorithms for Approximating String Compressibility, Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith, Algorithmica, Volume 65, Issue 3, pp 685-709, 2013.
  Preliminary version appeared in Proceedings of the 11th RANDOM, Springer-Verlag, 609-623, 2007.
  Slides
• A Note on Adaptivity in Testing Properties of Bounded Degree Graphs, Sofya Raskhodnikova and Adam Smith, Electronic Colloquium on Computational Complexity, TR06-089, 2006.
• Some 3CNF Properties are Hard to Test, Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova, SIAM Journal on Computing, 35(1):1-21, 2005.
  Preliminary version appeared in Proceedings of the 35th ACM STOC, 345-354, 2003.
  Slides
• Property Testing: Theory and Applications, PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, 2003.
• Approximate Testing of Visual Properties, Sofya Raskhodnikova, Proceedings of the 7th RANDOM, Springer-Verlag, 370-381, 2003.
  Slides
• A Sublinear Algorithm for Weakly Approximating Edit Distance, Tugkan Batu, Funda Ergun, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami, Proceedings of the 35th ACM STOC, 316-324, 2003.
• Lower Bounds for Embedding of Edit Distance into Normed Spaces, Alexandr Andoni, Michael Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova, Proceedings of the 14th ACM-SIAM SODA, 523-526, 2003.
• Monotonicity Testing Over General Poset Domains, Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky, Proceedings of the 34th ACM STOC, 474-483, 2002.
• Improved Testing Algorithms for Monotonicity, Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky, Proceedings of the 3rd RANDOM conference, 97-108, 1999.
  Slides
• Monotonicity Testing, Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1999.

Contact Information

• Email: first-name "at" bu.edu

How To Pronounce My Name

• Sofya: There are two syllables.
  • The first one sounds like Soft without the last sound.
  • The second, ya, sounds like German "yes".
  The stress is on the first syllable. Sophia is not a correct pronounciation of my name. (There are both versions in Russian, Sofya and Sophia, but my name is not Sophia.)
• Raskhodnikova: The only tricky part is that the first "k" is silent.
  • Ras
  • hod (stressed, the first sound as in "hat")
  • ni
  • ka (unstressed o is pronounced as a in Russian)
  • va