Welcome to the CS Theory Group at Penn State!
Our faculty and students have diverse research interests in core areas of theoretical computer science, as well as in closely connected fields such as machine learning, biology, and statistical physics.
We are a traditionally strong research group and are currently growing!
Ph.D. students: We solicit applications to our Ph.D. program from students interested in all areas of theory. Research assistantships are available for strong candidates. Information about how to apply can be found at:
https://www.eecs.psu.edu/students/graduate/EECSHowtoapplyCSE.aspx
Antonio Blanca
Randomized Algorithms, Markov Chain Monte Carlo, Learning, Statistical Physics.
Martin Fürer
Graph Algorithms, Approximation Algorithms, Computational Molecular Biology, Computational Complexity, Graph Isomorphism Problem.
Sean Hallgren
Quantum Computing, Computational Complexity.
Associated faculty:
Viveck Cadambe
Information Theory, Coding Theory, Theory of Distributed Systems.
Computational Biology, Graph Theory.
Computational Biology, Machine Learning, Combinatorial Optimization.
Largescale Machine Learning, Statistical Learning Theory, Adversarial Learning Theory, Convex
 Approximation Algorithms
 Coding Theory
 Computational Molecular Biology
 Computational Complexity
 Cryptography
 Distributed Algorithms
 Graph Algorithms
 Information Theory
 Markov chain Monte Carlo
 Probabilistic Models
 Quantum Computing
 Randomized Algorithms
Current Ph.D. Students:

Ishan Behoora (Ph.D., advisor: Piotr Berman)

Mahdi Belbasi (Ph.D., advisor: Martin Fürer)

Eunou Lee (Ph.D., advisor: Sean Hallgren)

Jianqiang Li (Ph.D., advisor: Sean Hallgren)

Michael Meehan (Ph.D., advisor: Sean Hallgren)
Recent Ph.D. Graduates:

NaiHui Chia (Ph.D. 2018, current position: Postdoc at Texas at Austin)

Meiram Murzabulatov (Ph.D. 2017, current position: Assistant Teaching Professor at Penn State)

Audra McMillan (Visiting Student in Summer 2015, current position: Postdoc at Boston University)

Kashyap Dixit (Ph.D. 2015, current position: Software Engineer at Jet.com)

Ye Zhang (Ph.D. 2015)

Grigory Yaroslavtsev (Ph.D. 2015, current position: Assistant Professor at Indiana University)

Huiwen Yu (Ph.D. 2014, current position: Software Engineer at Google)

Abhradeep Guha Thakurta (Ph.D. 2013, current position: Assistant Professor at UCSC)

Fang Song (Ph.D. 2013, current position: Assistant Professor at Texas A&M)

Madhav Jha (Ph.D. 2013, current position: Applied Scientist at Amazon AI)

Sandeep Narayanaswami (Ph.D. 2013, cuurent position: Data Scientist at Captical One)

Shiva Kasiviswanathan (Ph.D. 2008, current position: Senior Applied Scientist at Amazon)
Recent M.Sc. Graduates:

Roksana Baleshzar (M.Sc. 2017, current position: Software Engineer at Google)

Megan Heysham (M.Sc. 2013)

T.K. Ramesh (MS 2011)

Youngtae Youn

Ngai Lam Ho
Recent Postdocs:

Jalaj Upadhyay (current position: Postdoc at Johns Hopkins University)

Raef Bassily (current position: Assistant Professor at Ohio State University)
Theory Courses at Penn State
Spring 2019:
 Probabilistic Algorithms (Antonio Blanca)
 Quantum Computation (Sean Hallgren)
 Graph Algorithms, Width Parameters (Martin Fürer)
 Algorithms and Data Structures in Bioinformatics (Paul Medvedev)
Fall 2018:
 PostQuantum Cryptography (Sean Hallgren)
 Algorithm Design and Analysis (Martin Fürer)
Spring 2018:
 Data Structures and Algorithms in Bioinformatics (Paul Medvedev)
 Introduction to the Theory of Computation (Sean Hallgren)
 Complexity of Combinatorial Problem (Martin Fürer)
 Theory Seminar (Piotr Berman)
Fall 2015:
 Algorithm Design and Analysis (Adam Smith)
 Computational Geometry (Piotr Berman)
 Introduction to the Theory of Computation (Sean Hallgren)
 Sublinear Algorithms(Sofya Raskhodnikova)
 Theory seminar (Adam Smith)
Spring 2015:
 Data Privacy (Adam Smith)
 Data Structures and Algorithms (Piotr Berman)
 Discrete Mathematics for Computer Science (Sofya Raskhodnikova)
 Introduction to the Theory of Computation (Martin Fürer)
 Quantum Computation (Sean Hallgren)
 Theory seminar (Piotr Berman)
Fall 2014:
 Algorithm Design and Analysis (Adam Smith)
 Introduction to the Theory of Computation (Sean Hallgren)
 Parameterized Algorithms and Complexity (Martin Fürer)
 Theory seminar (Sofya Raskhodnikova)
Spring 2014:
Fall 2013:
Spring 2013:
Fall 2012:
 Data Privacy, Learning and Games (Adam Smith)
 Algorithm Design and Analysis (Sean Hallgren)
 Data Structures and Algorithms (Piotr Berman)
 Introduction to the Theory of Computation (Sofya Raskhodnikova)
 Theory seminar (Adam Smith)
 Algebraic Graph Theory (Martin Fürer)
Spring 2012:
 Quantum Computation (Sean Hallgren)
 Sublinear Algorithms (Sofya Raskhodnikova)
 Data Structures and Algorithms (Adam Smith)
 Introduction to the Theory of Computation (Martin Fürer)
Fall 2011:
 Pseudorandomness (Adam Smith)
 Algorithm Design and Analysis (Sofya Raskhodnikova)
 Data Structures and Algorithms (Piotr Berman)
 Introduction to the Theory of Computation (Sean Hallgren)
 Theory seminar (Martin Fürer)
Spring 2011:
 Cryptography (Adam Smith)
 Data Structures and Algorithms (Martin Fürer)
 Approximation Algorithms (Piotr Berman)
 Introduction to the Theory of Computation (Sean Hallgren)
 Theory seminar (Piotr Berman)
Fall 2010:
 Data Structures and Algorithms (Martin Fürer)
 Algorithm Design and Analysis (Adam Smith)
 Computational Complexity (Martin Fürer, Sean Hallgren)
 Introduction to the Theory of Computation (Sofya Raskhodnikova)
 Theory seminar (Adam Smith)
Spring 2010:
 Data Structures and Algorithms (Martin Fürer)
 Discrete Mathematics (Piotr Berman)
 Algorithmic Challenges in Data Privacy (Sofya Raskhodnikova, Adam Smith)
 Quantum Computation (Sean Hallgren)
 Theory seminar (Sean Hallgren)
Fall 2009:
 Data Structures and Algorithms (Adam Smith)
 Introduction to the Theory of Computation (Sofya Raskhodnikova)
 Algorithm Design and Analysis (Sean Hallgren)
 Randomized Algorithms (Piotr Berman)
 Approximation Algorithms (Martin Fürer)
 Theory seminar (Sofya Raskhodnikova)
Spring 2009:
 Data Structures and Algorithms (Piotr Berman)
 Algorithms for Graphs and Networks (Piotr Berman)
 Introduction to Modern Cryptography (Adam Smith)
 Theory seminar
Fall 2008:
 Data Structures and Algorithms
 Introduction to the Theory of Computation (Sofya Raskhodnikova)
 Algorithm Design and Analysis (Adam Smith)
 Combinatorial Optimization (Piotr Berman)
 Discrete Mathematics (Sean Hallgren)
 Theory seminar
Spring 2008:
 Data Structures and Algorithms
 Theory of Computation (Sofya Raskhodnikova)
 Computational Geometry (Piotr Berman)
 Discrete Mathematics (Sean Hallgren)
 Complexity in Computer Algebra (Martin Fürer)
 Theory seminar (Adam Smith)
Fall 2007:
 Data Structures and Algorithms (Martin Fürer)
 Algorithm Design and Analysis (Sofya Raskhodnikova)
 Introduction to Cryptography (Adam Smith)
 Privacy in Statistical Databases (Aleksandra Slavkovic, Adam Smith)
 Quantum Computation (Sean Hallgren)
 Theory seminar (Sofya Raskhodnikova)
Spring 2007:
 Data Structures and Algorithms (Sofya Raskhodnikova, Adam Smith)
 Algebraic Graph Theory (Martin Fürer)
 Theory seminar
Theory Seminar Schedule for Spring 2017
The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.
Date  Speaker  Title 

January 20  Martin Furer (PSU)  MultiCliqueWidth, a Powerful New Width Parameter 
January 27  No seminar  
February 3  No seminar  
February 10  Jalaj Upadhyay (PSU)  Fast and SpaceOptimal DifferentiallyPrivate LowRank Factorization in the General Turnstile Update Model 
February 17  Eunou Lee (PSU)  Quantum Lovasz Local Lemma 
February 24  Ramesh Krishnan (PSU)  Parameterized Property Testing of Functions 
March 3  Roksana Baleshzar (PSU)  Optimal Unateness Testers 
March 10  Spring break, no seminar  
March 17, 1011 a.m. in 223B IST  Jiayu Zhang (PSU)  CSS codes for quantum error correction 
March 24  Nithin Varma (PSU)  A polylogarithmic space deterministic streaming algorithm for estimating the distance to sortedness 
March 31  Meiram Murzabulatov (PSU)  An Improved Distributed Algorithm for the Maximal Independent Set Problem 
April 6, 1011:30 a.m. in 222 IST  Tim Roughgarden (Stanford)  How Computer Science Informs Modern Auction Design 
April 7  Mahdi Belbasi (PSU)  Saving Space by Algebraization 
April 14  Om Thakkar (PSU)  A brief introduction to Concentrated Differential Privacy 
April 21  No seminar  
April 21  Ishan Behoora (PSU)  Near straight line trajectories 
 Talks will generally be held on Fridays from 12:101:10 p.m. in 118 Earth and Eng Sciences Building (unless they are part of the departmental colloquium, in which case they will be held from 23 p.m. in 113 IST Building (Cybertorium)). Any unusual date/time/location is highlighted in the schedule.
 If you would like to speak, please email us at: theory [at] cse [dot] psu [dot] edu.
 If you want to receive announcements of upcoming talks, please join the theory mailing list.