Back to search

Georgia Institute of Technology

Witness Functions in Program Analysis and Complexity Theory

Abstract

dc:description.abstract

Proving impossibility results is one of the main themes of program analysis theory and computability/complexity theory. For example, we can prove a program analysis problem is undecidable, meaning that there does not exist an algorithm to precisely solve the problem. As another example, we can prove a problem does not belong to a complexity class, meaning that every correct algorithm for the problem must exceed the given resource restriction. In general, given a class C of computational problems and a specific computational problem P not in C, a witness function maps every candidate Q in C to an input on which P and Q are different. We investigate the computational properties of such witness functions and discuss their implications. In program analysis theory, we prove that a large class of undecidable program analysis problems have computable witness functions, including every semantic property described in Rice's theorem. This implies the existence of computable functions mapping every program analyzer to a more precise program analyzer. Through two real program analysis tasks (1) CFL-reachability based program analysis for Java and LLVM-IR and (2) template constraint analysis for C++, we demonstrate that computable witness functions provide guarantees on the progress of developing more and more precise program analysis techniques. In complexity theory, we prove that witness functions for major complexity classes are closely related to reductions, and discuss the implications in complexity class separation proofs.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ding, Shuo
Advisor dc:contributor.advisor
  • Zhang, Qirun
Committee members dc:contributor.committeemember
  • Bansal, Suguman
  • Ganesh, Vijay
  • Palsberg, Jens
  • Sarkar, Vivek

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/76979

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ding, Shuo. Witness Functions in Program Analysis and Complexity Theory. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/76979