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) TBD
  • 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.