Select Page

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!

Faculty positions: Our group will be hiring in the 2018-2019 academic cycle. Apply here!

 

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, 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.

 

Paul Medvedev


Computational Biology, Graph Theory.

 

 Mingfu Shao

Computational Biology, Machine Learning,  Combinatorial Optimization.

 Mehrdad Mahdavi

Large-scale Machine Learning, Statistical Learning Theory, Adversarial Learning Theory, Convex and non-convex Optimization, Computational Learning Theory, Distributed Optimization, Applications of Machine Learning

  • 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:

  • Nai-Hui 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:

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:

  • 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.
Archives

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014     Spring 2015     Fall 2015     Spring 2016     Fall 2016    Fall 2017

 

 

 ___________________________________________________________________________________________________________

Quantum Discrete Optimization and Approximation Algorithms (Ojas Parekh, Sep 10)

In this talk I will motivate quantum approaches to discrete optimization by highlighting fundamental connections between quantum physics and discrete optimization.  I will explain popular quantum discrete optimization techniques such as the Quantum Adiabatic Algorithm and the Quantum Approximate Optimization Algorithm (QAOA).  I will present recent results on quantum approximation algorithms, demonstrating rigorous bounds on the performance of QAOA for an NP-hard special case of the Maximum Cut problem (Max-Cut).  Finally, I will describe an almost optimal classical approximation algorithm for a physically motivated quantum generalization of Max-Cut and discuss future prospects for quantum approximation algorithms.
This talk is aimed at a general CS audience and assumes no familiarity with quantum computing.

 ___________________________________________________________________________________________________________

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(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)

In this talk, I will talk about a proof of sensitivity conjecture by Hao Huang (07/2019). 

https://arxiv.org/pdf/1907.00847.pdf 

/* 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.