Photo of Sofya Raskhodnikova

Sofya Raskhodnikova

Adjunct Professor

Affiliation(s):

  • School of Electrical Engineering and Computer Science

W314 Westgate Building

sxr48@psu.edu

814-863-0608

Research Areas:

Interest Areas:

Theoretical computer science: sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, randomized algorithms and complexity theory.

 
 

 

Education

  • BS, Mathematics with Computer Science, Massachusetts Institute of Technology, 1997
  • MS, Computer Science, Massachusetts Institute of Technology, 1999
  • Ph D, Computer Science, Massachusetts Institute of Technology, 2003

Publications

Book, Chapters

  • Sofya Raskhodnikova, 2010, Transitive-Closure Spanners: A Survey, pp. 167–196

Journal Articles

  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2016, "On the Readability of Overlap Diagraphs", Discrete Applied Mathematics, 205, pp. 35-44
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2016, "Testing Lipschitz Functions on Hypergrid Domains", Algorithmica, 74, (3), pp. 1055–1081
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2014, "Limitations of Local Filters of Lipschitz and Monotone Functions", ACM Transactions on Computation Theory, 7, (1), pp. 2
  • Piotr Berman and Sofya Raskhodnikova, 2014, "Approximation Algorithms for Min-Max Generalization Problems", ACM Transactions on Algorithms, 11, (1), pp. 5
  • Vishesh Karwa, Sofya Raskhodnikova, Adam D Smith and Grigory Yaroslavtsev, 2014, "Private Analysis of Graph Structure", ACM Trans. Database Syst., 39, (3), pp. 22
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2014, "Steiner transitive-closure spanners of low-dimensional posets", Combinatorica, 34, (3), pp. 255–277
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2013, "Sublinear Algorithms for Approximating String Compressibility", Algorithmica, 65, (3), pp. 685–709
  • Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Approximation algorithms for spanner problems and Directed SteinerForest", Information and Computation (ICALP 2011 Special Issue), 222, pp. 93–107
  • Madhav Jha and Sofya Raskhodnikova, 2013, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", SIAM Journal on Computing, 42, (2), pp. 700–731
  • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha*, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2012, "Lower Bounds for Local Monotonicity Reconstruction from Transitive-ClosureSpanners", SIAM Journal on Discrete Mathematics, 26, (2), pp. 618–646
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2012, "Transitive-Closure Spanners", SIAM Journal on Computing, 41, (6), pp. 1380–1425
  • Shiva Prasad Kasiviswanathan*, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2011, "What Can We Learn Privately?", SIAM Journal on Computing, 40, (3), pp. 793–826
  • Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam D Smith, 2009, "Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem", SIAM Journal on Computing, 39, (3), pp. 813–842
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2005, "Some 3CNF Properties Are Hard to Test", SIAM Journal on Computing, 35, (1), pp. 1–21

Conference Proceedings

  • Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and Nithin Varma, 2017, "Parameterized Property Testing of Functions"
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2016, "The Power and Limitations of Uniform Samples in Testing Properties of Figures"
  • Sofya Raskhodnikova and Adam D Smith, 2016, "Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism"
  • Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta and Nithin Varma, 2016, "Erasure-Resilient Property Testing"
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2016, "Tolerant Testers of Image Properties"
  • Piotr Berman, M. Murzabulatov and Sofya Raskhodnikova, 2016, "Testing Convexity of Figures Under the Uniform Distribution"
  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2015, "On the Readability of Overlap Digraphs", pp. 124–137
  • Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2014, "Lower Bounds for Testing Properties of Functions over Hypergrid Domains", IEEE, pp. 309–320
  • Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2014, "L_p-testing", ACM, pp. 164–173
  • Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2013, "Analyzing Graphs with Node Differential Privacy", pp. 457–476
  • Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova and Abhradeep Thakurta, 2013, "Testing the Lipschitz Property over Product Distributions with Applicationsto Data Privacy", pp. 418–436
  • Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Learning pseudo-Boolean k-DNF and submodular functions", pp. 1356–1368
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Limitations of Local Filters of Lipschitz and Monotone Functions", pp. 374–386
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Testing Lipschitz Functions on Hypergrid Domains", pp. 387–398
  • Madhav Jha* and Sofya Raskhodnikova, 2011, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", pp. 433–442
  • Vishesh Karwa, Sofya Raskhodnikova, Adam D Smith and Grigory Yaroslavtsev*, 2011, "Private Analysis of Graph Structure", 4, (11), pp. 1146–1157
  • Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev*, 2011, "Improved Approximation for the Directed Spanner Problem", pp. 1–12
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2011, "Steiner Transitive-Closure Spanners of Low-Dimensional Posets", pp. 760–772
  • Piotr Berman, Sofya Raskhodnikova and Ge Ruan*, 2010, "Finding Sparser Directed Spanners", pp. 424–435
  • Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha*, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2010, "Lower Bounds for Local Monotonicity Reconstruction from Transitive-ClosureSpanners", pp. 448–461
  • Piotr Berman and Sofya Raskhodnikova, 2010, "Approximation Algorithms for Min-Max Generalization Problems", pp. 53–66
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2009, "Transitive-closure spanners", pp. 932–941
  • Shiva Prasad Kasiviswanathan*, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2008, "What Can We Learn Privately?", pp. 531–540
  • Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam D Smith, 2007, "Strong Lower Bounds for Approximating Distribution Support Size andthe Distinct Elements Problem", pp. 559–569
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2007, "Sublinear Algorithms for Approximating String Compressibility", pp. 609–623
  • Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2007, "Smooth sensitivity and sampling in private data analysis", pp. 75–84
  • Sofya Raskhodnikova, 2003, "Approximate Testing of Visual Properties", pp. 370–381
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2003, "Some 3CNF properties are hard to test", pp. 345–354
  • Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld and Rahul Sami, 2003, "A sublinear algorithm for weakly approximating edit distance", pp. 316–324
  • Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk and Sofya Raskhodnikova, 2003, "Lower bounds for embedding edit distance into normed spaces", pp. 523–526
  • Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky, 2002, "Monotonicity testing over general poset domains", pp. 474–483
  • Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky, 1999, "Improved Testing Algorithms for Monotonicity", pp. 97–108

Technical Reports

  • Sofya Raskhodnikova and Adam D Smith, 2015, "Efficient Lipschitz Extensions for High-Dimensional Graph Statisticsand Node Private Degree Distributions", CoRR, abs/1504.07912
  • Rayan Chikhi, Paul Medvedev, Martin Milanic and Sofya Raskhodnikova, 2015, "On the readability of overlap digraphs", CoRR, abs/1504.04616
  • Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova, 2015, "Constant-Time Testing and Learning of Image Properties", CoRR, abs/1503.01363
  • Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova, 2012, "Testing Lipschitz Functions on Hypergrid Domains", pp. 22
  • Pranjal Awasthi, Madhav Jha*, Marco Molinaro and Sofya Raskhodnikova, 2012, "Limitations of Local Filters of Lipschitz and Monotone Functions", pp. 16
  • Sofya Raskhodnikova and Grigory Yaroslavtsev, 2012, "Learning pseudo-Boolean k-DNF and Submodular Functions", CoRR, abs/1208.2294
  • Madhav Jha and Sofya Raskhodnikova, 2011, "Testing and Reconstruction of Lipschitz Functions with Applicationsto Data Privacy", pp. 26
  • Piotr Berman, Sofya Raskhodnikova and G. Yaroslavtsev*, 2010, "Approximation for Directed Spanners"
  • Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2010, "What Can We Learn Privately?", CORR, pp. 35
  • Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff and Grigory Yaroslavtsev*, 2010, "Steiner Transitive-Closure Spanners of d-Dimensional Posets", CoRR, abs/1011.6100
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2009, "Transitive-Closure Spanners of the Hypercube and the Hypergrid", Electronic Colloquium on Computational Complexity. TR09-046., pp. 20
  • Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff, 2008, "Transitive-Closure Spanners", CoRR, abs/0808.1787, pp. 33
  • Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam D Smith, 2008, "What Can We Learn Privately?", CoRR, abs/0803.0924
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld and Adam D Smith, 2007, "Sublinear Algorithms for Approximating String Compressibility", CoRR, abs/0706.1084, pp. 25
  • Sofya Raskhodnikova and Adam D Smith, 2006, "A Note on Adaptivity in Testing Properties of Bounded Degree Graphs", Electronic Colloquium on Computational Complexity (ECCC), 13, (089), pp. 6
  • Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka and Adam D Smith, 2005, "Sublinear Algorithms for Approximating String Compressibility andthe Distribution Support Size", Electronic Colloquium on Computational Complexity. TR05-125., pp. 38
  • Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova, 2003, "3CNF Properties are Hard to Test", Electronic Colloquium on Computational Complexity. TR03-006., 10, (006), pp. 23
  • Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky, 1999, "Improved Testing Algorithms for Monotonicity", Electronic Colloquium on Computational Complexity. TR99-017., 6, (17), pp. 19

Encyclopedia Entries

  • Sofya Raskhodnikova and Adam D Smith, 2016, "Differentially Private Analysis of Graphs",, Encyclopedia of Algorithms 2016,
  • Sofya Raskhodnikova and Ronitt Rubinfeld, 2016, "Linearity Testing/Testing Hadamard Codes",, Encyclopedia of Algorithms 2016,
  • Sofya Raskhodnik andva, , 2016, "Testing if an Array Is Sorted",, Encyclopedia of Algorithms 2016,

Other

  • Sofya Raskhodnikova and Ola Svensson, 2015, "Special Issue: APPROX-RANDOM 2013: Guest Editors’ Foreword", Theory of Computing, 11, pp. 237–239
  • Eric Blais, Sofya Raskhodnikova and Grigory Yaroslavtsev, 2013, "Lower Bounds for Testing Properties of Functions over Hypergrid Domains", pp. 14

Research Projects

  • September 2014 - August 2018, "BIGDATA: F: DKA: Scalable, Private Algorithms for Continual Data Analysis," (Sponsor: National Science Foundation).
  • June 2014 - May 2017, "AF: Small: Sublinear Algorithms for Real Data," (Sponsor: National Science Foundation).
  • July 2009 - December 2015, "CAREER: Sublinear Algorithms - Theory and Applications," (Sponsor: National Science Foundation).
  • September 2010 - August 2015, "CDI-Type II: Collaborative Research: Integrating Statistical and Computational Approaches to Privacy," (Sponsor: National Science Foundation).
  • October 2007 - September 2011, "Algorithms for Private Data Analysis," (Sponsor: National Science Foundation).
  • September 2008 - August 2010, "CPATH: CDP: Integrating Biology and Computing: Empowering Future Computer Engineers," (Sponsor: National Science Foundation).

Honors and Awards

  • Computer Science Faculty Marshall, Penn State, CSE Department, May 2016
  • CSE Department Teaching Award, Penn State, CSE Department, 2010
  • Computer Science Faculty Marshall, Penn State, CSE Department, May 2010
  • NSF CAREER Award, National Science Foundation, 2009
  • Ruth and Joel Spira Award for Teaching Excellence, 2007
  • Lady Davis Postdoctoral Fellowship, 2003
  • Award for Excellent Work at RSA, 1999
  • NY Governor's Citation for Academic Excellence, 1994
  • First Place in Belorussian Republican Math Olympiad, 1992

Service

Service to Penn State:

  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, January 2016 - May 2016
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, August 2016 - December 2016
  • Committee Work, Chairperson, Colloquium Committee, August 2016 - July 2017
  • Committee Work, Committee Member, Outreach committee, August 2016 - July 2017
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, August 2015 - December 2015
  • Committee Work, Co-Chairperson, Colloquium Committee, August 2015 - July 2016
  • Committee Work, Member, Promotion and Tenure Committee, August 2014
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, January 2012 - May 2012
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, January 2012 - May 2012
  • Committee Work, Member, Sustainability Committee, August 2012 - July 2013
  • Assistance to Student Organizations, Advisor, Association of Women in Computing at Penn State, 2011
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, August 2011 - December 2011
  • Committee Work, Member, Curriculum/ABET Committee, August 2011 - July 2013
  • Committee Work, Member, Publications Committee, August 2009 - July 2013
  • Committee Work, Organizer, Junior Faculty Lunches, August 2009 - August 2010
  • Committee Work, Chairperson, Theory Lab Equipment Committee, August 2009 - July 2010
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, August 2009 - December 2009
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, January 2008 - May 2008
  • Committee Work, Co-Chairperson, Data Structures and Algorithms Exam, January 2007 - May 2007
  • Committee Work, Member, Graduate Committee, August 2007 - July 2013

Service to External Organizations:

  • Organizing Conferences and Service on Conference Committees, Organizer, SUBLINEAR 2016, Johns Hopkins University, 2015 - January 2016
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, 2015 - June 2016
  • Organizing Conferences and Service on Conference Committees, Co-Organizer, Special Privacy Year (2013-2014), 2013 - 2014
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, December 2009 - September 2010
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, December 2009 - October 2010
  • Organizing Conferences and Service on Conference Committees, Chairperson, Program Committee, August 2013
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, January 2010
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, July 2012
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, October 2012
  • Organizing Conferences and Service on Conference Committees, Co-Organizer, May 2014
  • Organizing Conferences and Service on Conference Committees, Co-Organizer, Sublinear Algorithms 2014, May 2014
  • Organizing Conferences and Service on Conference Committees, Co-Organizer, MIT, Mike Fest, October 2014
  • Organizing Conferences and Service on Conference Committees, Member, Program Committee, August 2007
 


 

About

The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research in fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802

814-863-6740

Department of Computer Science and Engineering

814-865-9505

Department of Electrical Engineering

814-865-7667