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
Publications
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)
Talk
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)