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 am a fifth year PhD student advised by Ramamohan Paturi. My research focus is on exact (exponential-time) algorithms for satisfiability problems and conditional lower bounds, 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


  • Subquadratic Algorithms for Succinct Stable Matching
    Daniel Moeller, Ramamohan Paturi and Stefan Schneider CSR (2016)
    Dan's Talk
  • 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)