Skip to main content
Open Access Publications from the University of California


UCLA Electronic Theses and Dissertations bannerUCLA

Descriptive Aspects of Locally Ckecable LAbelling and Constraint Satisfaction Problems

  • Author(s): Thornton, Riley
  • Advisor(s): Marks, Andrew S.
  • et al.

We explore the descriptive set theory of problems originating in theoretical computer science. We investigate a few special cases of locally checkable labelling problems using a variety of Borel and measurable techniques. Our result clarifies a small part of the connection between descriptive set theory and distributed computing. And, we adapt tools from the algebraic approach to constraint satisfaction problems to the Borel setting. In particular we draw a direct connection between NP-completeness and $\mathbf{\Sigma}^1_2$-completeness.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View