Stefan Schneider

Department of Computer Science and Engineering
University of California, San Diego
Office: EBU3b 4242
stschnei [at] cs [dot] ucsd [dot] edu

About Me

I was a PhD student advised by Ramamohan Paturi. My research focus is on fine-grained complexity and exact (exponential-time) algorithms for satisfiability problems, but I am also interested in related questions such as circuit lower bounds, exact algorithms for other NP-complete problems and complexity theory in general.

Before attending UCSD I got my Bachelor and Master from ETH Zürich. My advisor for my Master Thesis was Emo Welzl


  • On the Fine-grained Complexity of One-Dimensional Dynamic Programming
    Marvin Künnemann, Ramamohan Paturi and Stefan Schneider Preprint (2017)
  • Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
    Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider and Mingzhou Song Preprint (2017)
  • Subquadratic Algorithms for Succinct Stable Matching
    Marvin Künnemann, Daniel Moeller, Ramamohan Paturi and Stefan Schneider Computer Science Russia (2016)
    Dan's Talk
    Note: The CSR version did not include Marvin as a co-author. The arxiv version is the current version with all results.
  • Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
    Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi and Stefan Schneider ITCS (2016)
  • 0-1 Integer Linear Programming with a Linear Number of Constraints
    Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi and Stefan Schneider Preprint (2014)
  • A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
    Russell Impagliazzo, Ramamohan Paturi and Stefan Schneider FOCS (2013)
  • Other

  • Random Walk Algorithms for SAT and Constraint Satisfaction Problems Stefan Schneider Master Thesis (2010)
  • Satisfiability Algorithms for Restricted Circuit Classes Stefan Schneider Research Exam (2013)
  • Fine-Grained Connections Between Exponential and Polynomial Time Stefan Schneider PhD Dissertation (2017)