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

Designing algorithms for various combinatorial optimization problems and machine learning problems abstracted from computational biology

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

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

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 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 Spring 2017

 

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
January 20 Martin Furer (PSU) Multi-Clique-Width, a Powerful New Width Parameter
January 27 No seminar
February 3 No seminar
February 10 Jalaj Upadhyay (PSU) Fast and Space-Optimal Differentially-Private Low-Rank Factorization in the General Turnstile Update Model
February 17 Eunou Lee (PSU) Quantum Lovasz Local Lemma
February 24 Ramesh Krishnan (PSU) Parameterized Property Testing of Functions
March 3 Roksana Baleshzar (PSU) Optimal Unateness Testers
March 10 Spring break, no seminar
March 17, 10-11 a.m. in 223B IST Jiayu Zhang (PSU) CSS codes for quantum error correction
March 24 Nithin Varma (PSU) A polylogarithmic space deterministic streaming algorithm for estimating the distance to sortedness
March 31 Meiram Murzabulatov (PSU) An Improved Distributed Algorithm for the Maximal Independent Set Problem
April 6, 10-11:30 a.m. in 222 IST Tim Roughgarden (Stanford) How Computer Science Informs Modern Auction Design
April 7 Mahdi Belbasi (PSU) Saving Space by Algebraization
April 14 Om Thakkar (PSU) A brief introduction to Concentrated Differential Privacy
April 21 No seminar
April 21 Ishan Behoora (PSU) Near straight line trajectories
  • Talks will generally be held on Fridays from 12:10-1:10 p.m. in 118 Earth and Eng Sciences Building (unless they are part of the departmental colloquium, in which case they will be held from 2-3 p.m. in 113 IST Building (Cybertorium)). 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