Fine-Grained Connections between Exponential and Polynomial Time

Jun 19, 2017
Ph.D. candidate Stefan Schneider tackles exponential vs. polynomial time in dissertation.

CSE Ph.D. candidate Stefan Schneider is preparing for his upcoming Final Defense of his dissertation on "Fine-Grained Connections between Exponential and Polynomial Time."  On July 3, Schneider will face a committee chaired by his advisor Mohan Paturi, other CSE professors Sanjoy Dasgupta, Russell Impagliazzo and Shachar Lovett, and ECE professor Massimo Franceschetti. In May offered a preview of his dissertation in a presentation to the CSE Theory Seminar Series

Stefan Schneider

Date: Monday, July 3, 2017
Time: 3:00pm
Location: Room 4217, CSE Building

Fine-grained complexity aims at extending traditional complexity theory by making more precise and fine-grained statements on the complexity of problems in various resources, including time and space. In doing so, fine-grained complexity distinguishes between false equivalences, such as the equivalence of all NP-complete problems, while also exploring the connections between traditionally separate realms, such as polynomial and exponential time.

In his dissertation, Schneider takes a fine-grained view on computational problems from a range of fields, including geometry, biology, computational complexity, economics and graph theory. He studies the relationship between the satisfiability problem on threshold circuits and a geometric problem, giving the first non-trivial algorithms for both. From economics, the thesis explores the stable matching problem, giving both upper and lower bounds on the problem. "We also take a fine-grained view on the power of dynamic programming, again proving both upper and lower bounds, as well as relating dynamic programming to other algorithmic paradigms in a fine-grained manner," noted Schneider in his abstract. "Finally, we study the relationship between several problems central to the field of fine-grained complexity, including satisfiability, 3-sum and the all-pairs shortest path problem, giving the first fine-grained non-reducibility results."

Stefan Schneider is a sixth-year Ph.D. student in Computer Science who does research on fine-grained complexiy and exact (exponential-time) algorithms for satisfiability problems. He is also interested in related questions such as circuit lower bounds, exact algorithms for other NP-complete problems, and complexity theory in general. Prior to UC San Diego, Schneider earned his Bachelor's and Master's degrees from ETH Zurich (Switzerland).