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 (in alphabetical order):

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)

Heehyun Park (Ph.D., advisor: Antonio Blanca)

Xusheng Zhang (Ph.D., advisor: Antonio Blanca)
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
Fall 2019:
 Introduction to Cryptography (Sean Hallgren)
 Introduction to the Theory of Computation (Martin Fürer)
 Algorithms and Analysis (Mingfu Shao)
 Data Structure and Algorithms (Antonio Blanca, David Koslicki)
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)
 Data Structure and Algorithms (Mingfu Shao)
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 Fall 2019
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 

September 3  Borrowed from TCS+, Lior Kamma (Aarhus University)  Lower Bounds for Multiplication via Network Coding. 
September 10  Ojas Parekh (Sandia National Labs)  Quantum Discrete Optimization and Approximation Algorithms 
September 17  Martin Fürer (PSU)  A SpaceEfficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization 
September 24  Eunou Lee (PSU)  A Classical Approximation Algorithm for A Quantum Generalization of MAX2CSP 
October 1  Mahdi Belbasi (PSU)  TBD 
 Talks will generally be held on Tuesdays from 10:3511:50 a.m. in 112 Sackett Building (unless they are part of the departmental colloquium). 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.
Quantum Discrete Optimization and Approximation Algorithms (Ojas Parekh, Sep 10)
A SpaceEfficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization (Martin Fürer, Sep 17)
An NPhard graph problem may be intractable for general graphs but it could be efficiently solvable using dynamic programming for graphs with bounded treewidth. Employing dynamic programming on a tree decomposition usually uses exponential space. In 2010, Lokshtanov and Nederlof introduced an elegant framework to avoid exponential space by algebraization. Later, Fürer and Yu modified the framework in a way that even works when the underlying set is dynamic, thus applying it to tree decompositions.
In this work, we design spaceefficient algorithms to count the number of Hamiltonian cycles and furthermore solve the Traveling Salesman problem, using polynomial space while the time complexity is only slightly increased. This might be inevitable since we are reducing the space usage from an exponential amount (in dynamic programming solutions) to polynomial. We give an algorithm to count the number of Hamiltonian cycles in time $O((4k)^{d} nM(n log n))$ using $O(kdn log n)$ space, where $M(r)$ is the time complexity to multiply two integers, each of which being represented by at most $r$ bits. Then, we solve the more general Traveling Salesman problem in time $O((4k)^{d}poly(n))$ using space $O(Wkdn log n)$, where $k$ and $d$ are the width and the depth of the given tree decomposition and $W$ is the sum of weights. Furthermore, this algorithm counts the number of Hamiltonian Cycles.
___________________________________________________________________________________________________________
A Classical Approximation Algorithm for A Quantum Generalization of MAX2CSP (Eunou Lee, Sep 24)
We present a classical approximation algorithm for the MAX2Local Hamiltonian Problem. This problem generalizes MAX2CSPs, so is NPhard. It is an optimization version of the QMAcomplete Local Hamiltonian problem in quantum computing, with the additional assumption that the local terms are complex positive semidefinite. We work in the product state space, and extend Goemans and Williamson’s framework for approximating MAX2CSPs. The analysis for rounding does not naturally extend because we round to a set of normalized vectors, not boolean numbers, and we use Grothendieck inequalities for different special cases. For general MAX2Local Hamiltonions, we achieve an approximation ratio of 0.564 relative to the best product state.In general, the best product state might be worse than the best entangled state by a factor of two, so our overall approximation ratio is 0.282. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.