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/EECS-How-to-apply-CSE.aspx
Antonio Blanca
Randomized algorithms, markov chain Monte Carlo, learning, and statistical physics.
Debarati Das
Theoretical computer science, with a special focus on data structures, fine grained complexity and approximation algorithms, string algorithms, graph algorithms, lower bounds, and clustering algorithms.
Martin Fürer
Graph algorithms, approximation algorithms, computational molecular biology, computational complexity, and Graph isomorphism problem.
Sean Hallgren
Quantum computing and computational complexity.
Young Kun Ko
Applications of information theoretic techniques in complexity theory and data structure lower bounds using techniques from communication complexity
Chunhao Wang
Quantum algorithms related to simulating physical systems as well as their implications to classical algorithms
Proof systems, communication complexity, Boolean function analysis.
Associated faculty (in alphabetical order):
Algorithmic game theory, mechanism design, and computational social choice
Developing mathematically sound approaches to the analysis of high-throughput DNA sequencing data
Large-scale machine learning, statistical learning theory, adversarial learning theory, convex and non-convex optimization, computational learning theory, distributed optimization, and applications of machine learning
Computational biology and graph theory.
Computational biology, machine learning, and combinatorial optimization.
- 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
Postdocs:
-
Amir Carmel (advisor: Debarati Das)
Current Ph.D. Students (in alphabetical order):
-
Ishan Behoora (Ph.D., advisor: Piotr Berman)
-
Jeremy Ahrens Huang (Ph.D., advisor: Chunhao Wang)
-
Akshit Katiyar (Ph.D advisor: Sean Hallgren)
-
Medha Kumar (Ph.D., advisor: Martin Fürer)
-
Danrong Li (Ph.D advisor: Young Kun Ko)
-
Haowei Li (Ph.D advisor: Young Kun Ko)
-
Jianqiang Li (Ph.D., advisor: Sean Hallgren)
-
Zecheng Li (Ph.D., advisor: Chunhao Wang)
-
Michael Meehan (Ph.D., advisor: Sean Hallgren)
-
Tien Long Nguyen (Ph.D advisor: Debarati Das)
-
Heehyun Park (Ph.D., advisor: Antonio Blanca)
-
Md Tahmidur Rafid (Ph.D., advisor: Antonio Blanca)
-
Christopher Ye (Ph.D advisor: Chunhao Wang)
Recent Ph.D. Graduates:
-
Xusheng Zhang (Ph.D 2024 [advisor: Antonio Blanca])
-
Mahdi Belbasi (Ph.D. 2022 [advisor: Martin Fürer], current position: Software Engineer at gopuff)
-
Eunou Lee (Ph.D. 2020 [advisor: Sean Hallgren])
-
Nai-Hui Chia (Ph.D. 2018 [advisor: Sean Hallgren], current position: Postdoc at Texas at Austin)
-
Meiram Murzabulatov (Ph.D. 2017 [advisors: Sofya Raskhodnikova and Piotr Berman], current position: Assistant Professor at Nazarbayev University)
-
Audra McMillan (Visiting Student in Summer 2015, current position: Research Scientist at Apple)
-
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, current 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: Research Scientist at Apple)
-
Raef Bassily (current position: Assistant Professor at Ohio State University)
-
Chaowen Guan (current position: Assistant Professor at University of Cincinnati)
Theory Courses at Penn State
Spring 2022:
Fall 2021:
- Introduction to the Theory of Computation (Young Kun Ko)
- Quantum Computation (Chunhao Wang)
- Data Structures and Algorithms (Antonio Blanca — David Koslicki)
- Parameterized Complexity and Width Parameters (Martin Fürer)
- Algorithm Design and Analysis (Mingfu Shao)
- Large-Scale Machine Learning (Mehrdad Mahdavi)
- Writing in Computer Science (Paul Medvedev)
Spring 2021:
- Introduction to the Theory of Computation (Martin Fürer)
- Data Structures and Algorithms (Chunhao Wang)
- Probabilistic Algorithms (Antonio Blanca)
- Algorithms and Data Structures in Bioinformatics (Paul Medvedev)
- Quantum Computation (Sean Hallgren)
Fall 2020:
- Algorithm Design and Analysis (Antonio Blanca)
- Introduction to the Theory of Computation (Sean Hallgren)
- Parameterized Algorithms and Complexity (Martin Fürer)
- Introduction to Cryptography (Mohammad Hajiabadi)
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:
- Post-Quantum 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 Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization |
| September 24 | Eunou Lee (PSU) | A Classical Approximation Algorithm for A Quantum Generalization of MAX-2CSP |
| 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 NP-hard” 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:35-11: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 Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization (Martin Fürer, Sep 17)
An NP-hard 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 space-efficient 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 MAX-2CSP (Eunou Lee, Sep 24)
We present a classical approximation algorithm for the MAX-2-Local Hamiltonian Problem. This problem generalizes MAX-2-CSPs, so is NP-hard. It is an optimization version of the QMA-complete Local Hamiltonian problem in quantum computing, with the additional assumption that the local terms are complex positive semi-definite. We work in the product state space, and extend Goemans and Williamson’s framework for approximating MAX-2-CSPs. 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 MAX-2-Local 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 Broder-chain) 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 NP-hard” by James King and Erik Krohn (Ishan Behoora, Oct 22)
A set G of points on a 1.5-dimensional terrain, also known as an x-monotone 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 3-SAT the authors prove that the decision version of this problem is NP-hard.
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 APX-complete, 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 multi-task 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 fault-tolerant 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.