Quantitative Analysis of Complex Systems: From Program Termination to Blockchain Optimization

PhD Thesis Proposal Defence


Title: "Quantitative Analysis of Complex Systems: From Program Termination to 
Blockchain Optimization"

by

Mr. Sergei NOVOZHILOV


Abstract:

Modern computational systems have stepped beyond classical settings. They may 
exhibit stochastic behavior, operate in distributed environments whose 
participants are financially motivated toward certain outcomes, or be subject 
to non-standard resource constraints. Some systems do not perform computation 
themselves, yet pose challenging computational tasks in their analysis. 
Examples of such systems range from probabilistic programs and recursive 
programs modeled by recurrence systems, to blockchain protocols, dynamic 
graphs of exchange rates, and molecular graphs.

For such domains, computability and complexity theory often give negative or
incomplete answers, from undecidability to #P-hardness. Yet these worst-case
barriers do not explain when quantitative analysis is possible for structured
instances arising in practice.

In this thesis, we develop tailored analysis methods for several such
domains. The common strategy is to identify problem-specific structure, for
instance the regular structure of infinite-state Markov chains induced by
probabilistic counter programs, structural sparsity of molecular,
transaction-dependency, and decentralized-exchange routing graphs, and the
polynomial nature of recursive constraints. As a consequence, we obtain
tractability results, decision procedures, and techniques capable of scaling
to real-world instances.

We first develop methods for two central problems in program analysis:
automated resource analysis for recursive programs and termination analysis
for probabilistic counter programs. For recursive programs, we obtain a
semi-completeness result for synthesizing tight polynomial upper bounds on
their runtime. For almost-sure termination of probabilistic counter programs,
we prove a sharp boundary between one-dimensional and higher-dimensional
systems: the problem is decidable for the former class, while it remains
undecidable for the latter.

We next extend this structure-aware perspective to revenue optimization in
blockchain block construction through transaction selection and ordering.
Cardano's transaction-dependency constraints and Ethereum's order-dependent
execution costs lead to distinct optimization problems, which we solve using
tailored combinatorial and learning-based methods. In both cases, we obtain
algorithms that scale to real-world instances, with experimentally observed
annual revenue improvements of $0.4 million and $63 million, respectively,
based on retrospective experiments.

Structure-aware methods have become a key tool for addressing graph
optimization problems that are computationally intractable in general, but
become tractable in practice due to structural properties of real-world
instances. This phenomenon emerges across diverse domains, where we show that
both decentralized exchange graphs and molecular graphs exhibit low treewidth.
For molecular graphs, we exploit tree decomposition to design dynamic
programming algorithms that compute chemical descriptors over the entire
PubChem database within a few hours.

Overall, the thesis demonstrates a cross-domain phenomenon in which problems
that are intractable in the worst case exhibit structural properties not
captured by classical theory. Accounting for these properties leads to
algorithms that are both practically efficient and theoretically grounded,
highlighting the limitations of worst-case analysis as a sole predictor of
computational feasibility.


Date:                   Monday, 13 July 2026

Time:                   4:00pm - 6:00pm

Venue:                  Room 3494
                        Lift 25/26

Committee Members:      Dr. Dimitris Papadopoulos (Co-supervisor, HKUST)
                        Dr. Amir Goharshady (Co-supervisor, Oxford)
                        Dr. Lionel Parreaux (Chairperson)
                        Dr. Dan Xu