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
Spring 2020:
 Algorithm Design and Analysis (Martin Fürer)
 Introduction to the Theory of Computation (Mahdi Belbasi)
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)  Sampling from Ising Model with Fixed Boundary Condition 
October 8  Antonio Blanca (PSU)  Lower bounds for testing graphical models 
October 15  Jianqiang Li (PSU)  A proof of Sensitivity Conjecture By Hao Huang 
October 22  Ishan Behoora (PSU)  “Terrain guarding is NPhard” by James King and Erik Krohn 
October 29  Michael Meehan (PSU) (canceled)  Canceled 
November 5  Mehrdad Mahdavi (PSU)  Collaborative Learning: sample complexity and robustness 
November 12  Michael Meehan (PSU) (canceled)  Canceled 
November 19  Viveck Cadambe (PSU)  Coded Computing 
 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.
___________________________________________________________________________________________________________
Sampling from Ising Model with Fixed Boundary Condition (Mahdi Belbasi, Oct 1)
In this talk, I will talk about an algorithm to sample from Ising Model defined on a finite lattice with fixed boundary condition. Ising model is a mathematical model of ferromagnetism in statistical physics. Although the problem comes from physics, it has attracted many mathematicians and computer scientists.
In this talk, I will first introduce the Ising model and then we will review the notion of Markov chain. Later, we will show how we can design a Markov chain (in this case we will use Broderchain) to sample from Ising model (given the probability distribution). This problem with free boundary seems very difficult and has remained open for a long time. Bhatnagar et al. in 2006 showed that we can sample from the model if we impose a boundary condition on the lattice.
The reason that I think this topic is interesting is that there are hopes that one can use the main idea to sample from other spin systems (with modifications).
*** No prior knowledge about Markov chain, Ising model, or statistical physics is needed at all. I will start “almost” from scratch. ***
___________________________________________________________________________________________________________
Lower bounds for testing graphical models (Antonio Blanca, Oct 8)
We study the identity testing problem in the context of spin systems (a.k.a. undirected graphical models), where it takes the following form:
given the parameter specification of the model M and a sampling oracle for the distribution μ of an unknown model M*, can we efficiently determine if the two models M and M* are the same?
We establish hardness results for two prototypical spin systems: the Ising model and proper colorings. For the ferromagnetic (attractive)
Ising model, Daskalakis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the
antiferromagnetic (repulsive) setting. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal
works on the hardness of approximate counting. Our results for proper colorings are based on the presumed hardness of #BIS, the problem of
(approximately) counting independent sets in bipartite graphs.
Based on joint work with Ivona Bezakova, Zongchen Chen, Daniel Stefankovic and Eric Vigoda
___________________________________________________________________________________________________________
A proof of Sensitivity Conjecture By Hao Huang (Jianqiang Li, Oct 15)
https://arxiv.org/pdf/1907.
/* No prior knowledge required */
___________________________________________________________________________________________________________
“Terrain guarding is NPhard” by James King and Erik Krohn (Ishan Behoora, Oct 22)
A set G of points on a 1.5dimensional terrain, also known as an xmonotone polygonal chain, is said to guard the terrain if every point on the terrain is seen y a point in G. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. Using a reduction from PLANAR 3SAT the authors prove that the decision version of this problem is NPhard.
The problem was widely believed to be hard however, while there had been many approximate solutions including a ptas thus showing the problem was not APXcomplete, the hardness of the problem remained open till the authors’ 2010 Soda paper which is the basis of this talk.
___________________________________________________________________________________________________________
Collaborative Learning: sample complexity and robustness (Mehrdad Mahdavi, Nov 5)
Abstract:
In many applications of machine learning, such as multitask learning and federated learning, multiple users with different distributions try to collaboratively learn a centralized or personalized model. In this talk we discuss generalization of Valiant’s PAC model to collaborative learning and provide tight bounds on the sample complexity. We also discuss scenarios where a subset of users are malicious and aim at misleading the learning process. The analysis is constructive and is based on online learning algorithms.
___________________________________________________________________________________________________________
Coded Computing (Viveck Cadambe, Nov 19)
Abstract:
There is a lot of recent interest in information and coding theory research in an emerging area dubbed “coded computing” that uses redundancy to mitigate stragglers and errors in distributed data processing. This talk will present some ideas and results in this area. We will look at the following specific problem. Given two matrices $A, B$, we consider the problem of computing the product $AB$ over $P$ processing nodes in a faulttolerant manner. We assume that the $i$th node, for $i = 1,2,\ldots,P$ receives $g_i(A)$, and $h_i(B),$ where $g_i, h_i$ are linear operators on the space of matrices, and the nodes compute the product of the matrices it receives, i.e., $g_i(A) h_i(B)$. The functions are designed so that the product $AB$ is recoverable from any $K$ of the $P$ nodes; for a given scheme, we refer to the smallest such $K$ as the recovery threshold of the scheme. We will survey results related to the minimum known recovery threshold under various restrictions/constraints on the functions $g_i, h_i$. We will describe several schemes via polynomial evaluation based encoding and polynomial interpolation based decoding. No knowledge of coding theory will be assumed.