PhD Defense: Applications of Logic and Graph Theory in Computer Science
Shaopeng Zhu
Friday, April 7, 2023, 2:00-4:00 pm 
Abstract
We study the CSP of unary expansions of directed graphs. When we expand the simple structure (Z,succ) with one unary predicate U , its CSP (Constraint Satisfaction Problem) may vary in complexity. We find some sufficient conditions for its tractability, prove bounds on its complexity, and then generalize our results to more complicated structures. We also give a Karp-equivalent characterization of CSP(Z, succ, U )’s.
Next, fixing α ∈ (0, 1], we generalized the axiomatizations in [1] to the class of hereditarily linearly sparse Kn-free graphs, and made efforts towards connecting this with almost sure theories of Shelah-Spencer graphs, a type of random graphs, which may be of interest in theory of computer science.
Then we study the constraint satisfaction problems of selected infinite relational structures. For α ∈ (0, 5/6], K_α := the class of hereditarily α-sparse graphs, M_α := the generic structure of K_α; K_{α,Kn−free}, M_{α,Kn−free}:= the Kn-free subclass and its generic structure respectively, we prove multiple structural properties of graphs presenting the Hrushovski-Fraïssé class K_{α,TF}, strongly indicating that this class should have a finite homomorphic presentation when α is close to 5/6 from below, which would imply NP-Completeness. More general results are explored along. We also study the complexity-theoretic implications of our findings on a relevant decision problem, namely the constraint satisfaction problem of the corresponding generic structure.
Next, fixing α ∈ (0, 1], we generalized the axiomatizations in [1] to the class of hereditarily linearly sparse Kn-free graphs, and made efforts towards connecting this with almost sure theories of Shelah-Spencer graphs, a type of random graphs, which may be of interest in theory of computer science.
Then we study the constraint satisfaction problems of selected infinite relational structures. For α ∈ (0, 5/6], K_α := the class of hereditarily α-sparse graphs, M_α := the generic structure of K_α; K_{α,Kn−free}, M_{α,Kn−free}:= the Kn-free subclass and its generic structure respectively, we prove multiple structural properties of graphs presenting the Hrushovski-Fraïssé class K_{α,TF}, strongly indicating that this class should have a finite homomorphic presentation when α is close to 5/6 from below, which would imply NP-Completeness. More general results are explored along. We also study the complexity-theoretic implications of our findings on a relevant decision problem, namely the constraint satisfaction problem of the corresponding generic structure.
Examining Committee
Bio
Shaopeng Zhu is a PhD student in Computer Science at the University of Maryland. He got his Bachelor's degree at Peking University and a Masters Degree from UC Davis.
This talk is organized by Tom Hurst