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