log in  |  register  |  feedback?  |  help  |  web accessibility
PhD Proposal: Constraint SAT problems for Infinite Structures
Shaopeng Zhu
1131 Mathematics Building (MTH)
Wednesday, March 30, 2022, 2:00-4:00 pm
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract
We study the constraint satisfaction problems of selected infinite relational structures. In particular, we consider different classes of hereditarily linearly sparse graphs and their generic structures, and prove that in nice cases, the constraint satisfaction problems of the generic structures have simple finite characterizations and are therefore NP-complete. We also 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. Concurrently, we give a Karp-equivalent characterization of CSP(Z,succ, U)’s.

Examining Committee:
Chair:
Co-Chair:
Department Representative:
Dr. William Gasarch    
Dr. Chris Laskowski
Dr. Rob Patro    
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