Two-player games on finite graphs are the central algorithmic model of the reactive synthesis problem: av{automatically} constructing a controller that enforces a given temporal specification against every behavior of its environment. av{A faithful game model is, however, delicate: an overly powerful environment makes winning impossible, an overly weak one yields controllers that fail in practice.} \emph{Fairness assumptions} address this modeling challenge by concisely capturing realistic constraints on the environment, such as ``a request enabled infinitely often is granted infinitely often.'' The most general such notion, \emph{strong fairness}, is encoded by a Streett winning condition and makes game solving intractable. This thesis studies a structurally restricted, yet practically expressive subclass: \emph{strong transition fairness}, which attaches fairness to designated \emph{fair edges} of the game graph. Recent work has shown that for ùù-regular winning conditions such as B\"uchi, Rabin, and parity, strong transition fairness comes essentially \emph{for free}: fair games can be solved with the same algorithmic effort as their non-fair counterparts. This thesis investigates how far fairness stays free, and what its boundaries are. We start by saving a foundational result: the published equivalence between fairness and randomness turns out to rest on a false clause; we refute that clause and prove the surviving equivalence for all Muller objectives. The phenomenon extends further. Fairness may constrain both players at once, as environment assumption and system obligation: we introduce the first framework for such \emph{doubly-fair} games, give a determined semantics \dfsc{for all ùù -regular objectives} and\dfsc{, for parity,} a polynomial reduction to standard parity games. Beyond ùù-regular objectives, fair mean-payoff and energy games stay in the pseudo-polynomial regime, though one variant is, surprisingly, not determined; throughout, we settle the strategy complexity of both players. "Fairness for free'' ends twice. It ends at the arena. A complete classification of \emph{viability games} over valence systems, of independent interest, shows that fairness strictly shrinks what stays decidable: a game solvable in exponential time without fairness becomes undecidable with it. And it ends at the format. Fairness attached to a \emph{group} of edges makes game solving NP-hard already for reachability, and tractability is not preserved under products. We show that fairness is "for free'' not only on paper but also in practice: symbolic fixpoints, Zielonka's recursion, and progress measures all carry over to their fair counterparts with negligible overhead. The fair Zielonka solver matches its classical counterpart in experiments; the new progress measures drive the first incremental, data-driven synthesis framework for unknown stochastic systems, with speedups approaching two orders of magnitude.

Critical autonomous systems, such as robots operating amongst humans or a rover navigating on a remote planet, must continuously react to environments they do not control while provably satisfying their specifications. Designing a correct controller for such machines manually is impossible as a human cannot foresee every environmental possibility. Reactive synthesis provides an alternative approach of automatically building correct-by-construction controllers from formal specifications. Although this is a well-studied field, it almost entirely focuses on finding a single controller that satisfies the specification. The real world, however, is transient, and a single controller is rarely sufficient in practical applications. When an action proposed by the controller becomes unavailable (e.g., due to a component failure), the system immediately stalls, forcing an expensive re-synthesis.

This thesis addresses this problem by introducing a concise data-structure, called the strategy template, which represents infinitely many controllers. Strategy templates localize a given specification by local guidelines for a controller to choose the next action. In the first part of the thesis, we define the notion of strategy templates for major classes of specifications and models of interaction of the system and the environment. We then provide algorithms for computing the templates, and prove soundness (i.e., a controller following the template satisfies the specification) and completeness (i.e., if there is a controller that satisfies the specification, we compute a strategy template). We show that the strategy templates enable us to compose various specification online, and make controllers more robust to changes in the environment at runtime. In the second part, we utilize the resulting permissiveness (i.e., capturing infinitely many controllers) of the templates to shield learned policies which usually lack formal guarantees of correctness. The templates allow us to monitor and nudge the policies to ensure that they satisfy liveness (i.e., some progress is made), which until now had eluded the shielding literature. Furthermore, we implement all the algorithms proposed and show that they outperform the state-of-the-art in terms of composibility, robustness and scalability.

Block-based visual programming initiatives such as Hour of Code by code.org and Intro to Programming with Karel by CodeHS.com, have transformed introductory computer science education by making programming more accessible to K-8 learners. Despite their accessibility, students often struggle with multi-step reasoning and conceptual abstraction when solving open-ended tasks. Quizzes (such as fill-in-the-gap exercises, and multiple-choice conceptual questions based on code debugging and task design) offer interactive practice and targeted feedback that can promote active learning and scaffold novice programmers. However, manually designing such quizzes is time-consuming and difficult to scale. This thesis tackles these challenges by developing automated synthesis techniques for programming tasks and quizzes, and evaluates their pedagogical utility.

The first part of the thesis introduces algorithmic methods for synthesizing programming tasks and quizzes in block-based environments. Specifically, we develop methods for the following : (i) synthesizing conceptually similar and yet visually dissimilar write-code tasks; and (ii) synthesizing adaptive multiple-choice programming quizzes that address student-specific misconceptions; Each method leverages symbolic execution, sketch-based code mutation, and search-guided generation to ensure pedagogical utility, relevance, and technical correctness. Empirical evaluations conducted through controlled user studies demonstrate the efficacy of these approaches, showing that they not only support novice learners effectively but also outperform existing methods, including next-step code edit based feedback methods.

The second part of the thesis empirically evaluates the pedagogical utility of programming quizzes in these environments via user studies and classroom deployments with K-8 learners. Specifically, we examine: (i) the design, validation, and classification of quiz types using cognitive frameworks such as Bloom's Revised Taxonomy; (ii) the impact of embedding quizzes within programming curricula on post-learning outcomes; and (iii) the effectiveness of quiz-based feedback scaffolds with different quiz-types. Our findings show that quizzes designed using metacognitive strategies and adapted to learners’ attempts significantly enhance engagement and task performance. Moreover, we observe that richer and more diverse quiz types—when integrated into the curriculum—lead to improved post-learning outcomes, while simpler, less cognitively demanding quizzes may hinder post-learning performance.

Overall, this thesis contributes novel synthesis methods for programming quizzes and empirical evidence of their effectiveness in elementary-level programming education. These findings provide a foundation for scalable and adaptive support in elementary computing curricula.

A mix network (mixnet) is a routing network that conceals communication patterns by shuffling, or mixing, the routes of concurrently transmitted messages, thereby providing anonymity for senders, receivers, and sender-receiver pairs. Notable examples of deployed mixnets are Tor and Nym. Given the potential use of mixnets in high-stakes applications, such as protecting whistleblowers, it is essential to establish formal guarantees of sender anonymity, even against powerful adversaries that have a full view of the network and are capable of compromising subsets of mix servers. However, existing analyses of mixnets anonymity typically rely on additional mechanisms, such as noise or chaff messages, or are based on empirical metrics such as entropy, which cannot provide strong guarantees in the presence of adversaries with auxiliary information. My thesis consists of two complementary parts: (1) a first part on parallel mixnets, in which mix nodes operate in loosely synchronized rounds, and (2) a second part on continuous-time mixnets, in which mix nodes operate independently and forward messages after user-specified random delays. First, I present a new analysis of horizontally scalable parallel mixnets, showing that they can achieve strong indistinguishability guarantees for messages without requiring additional noise messages or extensive cryptographic techniques. Second, I develop a theoretical framework for continuous-time mixing by identifying two interacting stochastic processes that govern mixnets' operation: a local shuffling process at each mix node, driven by message delays and their sampling, and a global shuffling process that determines how messages (or batches) propagate between mixing layers. Building on this perspective, I derive a new tractable analytical model that captures mixing at both the local (per-node) and global (system-wide) levels. Finally, I use this model to establish provable anonymity guarantees for asynchronous mixnets.

AI-driven systems increasingly shape consequential decisions in domains such as lending, university admissions, and content moderation. Yet making these systems trustworthy in practice requires more than principled algorithms: it requires methods that scale, account for bias throughout the decision-making process, and can be evaluated against deployed real-world systems. This thesis addresses these challenges through three lines of work: scalable causal algorithmic recourse, fairness across the decision-making pipeline, and content policy enforcement on digital platforms.

First, it introduces CARMA, a neural-network-based approach that amortizes causal recourse generation, producing near-real-time recommendations while preserving causal validity and effort optimality. Second, it addresses fairness across the decision-making pipeline by developing a causal framework for measuring and mitigating bias in post-selection treatment decisions, alongside an online learning framework, FairAll, that learns fair and temporally consistent selection policies without sacrificing utility. Third, it studies instruction-driven moderation with foundation models and introduces ModerationBench, a benchmark of multimodal, in-the-wild social media content grounded in Bluesky’s deployed moderation guidelines.

Together, these contributions push Responsible AI beyond idealized settings and toward practical deployment. They provide scalable mechanisms for recourse, broader tools for fairness across the full decision-making pipeline, and grounded methods for evaluating adaptable content-safety enforcement in real-world digital platforms.

Multi-pushdown automata (MPDA) are a classic computational model that can be used to capture the behavior of multithreaded recursive programs. Here, each parallel thread is simply modeled by a single stack, and there is a fixed number of them. Due to the well known fact that most verification problems are undecidable for MPDA, even with just two stacks, the literature contains many different ways to restrict the runs of this model, in such a manner as to recover decidability. A popular restriction of this kind is known as bounded context-switching: For a fixed bound k, every parallel thread (or stack) may only be interrupted by another thread up to k times.

We consider an extended setting, where the number of parallel threads is not fixed, and more of them can be spawned dynamically during execution. This gives rise to the model of dynamic networks of concurrent pushdown systems (DCPS), which we still restrict with bounded context-switching. In this setting, we consider various verification questions, that have been asked for similar models in the past. These include state reachability, non-termination (with and without assumptions on fairness), and boundedness of the thread buffer. Moreover we consider the novel verification problem of Dyck inclusion: Given a model with action sequences over some alphabet of bracket pairs, are all its executions well-bracketed? Our results close a preexisting complexity gap for state reachability, and settle the complexity of several other verification problems, where in many cases even decidability was unknown before

Software is what turns quantum hardware into technology everyone can use. In this talk we focus on the quantum communication networks, with the first metropolitan scale quantum networks being built and the technologies to connect them over long distances advancing. We begin with the first operating system for quantum networks (QNodeOS), allowing applications to be programmed and executed on arbitrary quantum processors connected to a quantum network. Demonstrated on two different types of quantum hardware, QNodeOS now provides a framework for experimenting with software systems for quantum networks. We then turn to a specific kind of quantum network application, in which entanglement is harnessed for coordination between distant parties. We explore this through a recent example in radio spectrum allocation, opening the door to a new domain of quantum network applications.

Put yourself in the shoes of an algorithm designer working on some computational problem. You have found an algorithm running in time O(n^2), say, but after months of effort no faster algorithm is in sight. Perhaps your algorithm is already optimal – but how could you show this? This is the central challenge of fine-grained complexity theory. In the spirit of classical NP-hardness, this theory starts from the assumption that certain canonical problems are hard, and then uses so-called fine-grained reductions to show that many other problems are conditionally hard as well.

In this talk, I will first describe the basic concepts of fine-grained complexity along with some illustrative examples, before turning to more recent developments, including some of my own work. I will discuss some questions that resisted the basic theory for a long time, and how progress on them has required a more sophisticated method – the celebrated structure-versus-randomness paradigm.

Generative AI holds great promise in enhancing programming education by automatically generating personalized feedback for students. However, ensuring that this feedback is both technically accurate and pedagogically effective remains a critical challenge before these systems can be safely deployed in real-world classrooms. This thesis investigates the end-to-end integration of generative AI in programming education, divided into two main parts.

The first part focuses on the optimization of AI-generated feedback quality. We introduce novel techniques that not only enhance the generated feedback but also perform automatic validation of the feedback before returning it. Specifically, to improve feedback quality, our techniques contextualize the prompt with similar examples from the database and uses symbolic information of failing test cases and fixes. Next, to validate the quality of AI-generated feedback, they leverage another AI agent as simulated students in a run-time validation mechanism. These techniques achieve high-precision, human tutor-style feedback.

The second part transitions to the deployment of the feedback systems in real-world classroom settings, focusing on student-instructor-AI interaction. Specifically, to ensure feedback meets both expert educators' and students' quality standards, we investigate the discrepancies between expert-created rubrics and student perceptions of hint helpfulness. To understand how to position AI-generated hints with traditional pedagogical practices, we examine the interplay between AI-generated hints and student reflection. To address the problem of students being over-reliant on AI support, we base our design on metacognitive theory to introduce different hint types with quotas to require students' critical engagement during interaction with the system. Finally, to ensure students receive relevant support in difficult cases when AI is insufficient, we propose a hybrid instructor-in-the-loop escalation mechanism, allowing instructors to efficiently involve and support students when most needed.

Ultimately, this thesis provides a foundational framework for deploying LLMs that balance automated efficiency with established pedagogical standards and human oversight.

Floating-point numbers often represent real numbers in computer systems. They are applicable in many domains, including embedded systems, machine learning, and scientific computing. Despite their widespread use, they pose some difficulties. Floating-point numbers and operations typically suffer from roundoff errors, making computations over floating-points inaccurate with respect to a real-valued specification. Moreover, the IEEE 754 floating-point standard, a fundamental element in formalizing floating-point arithmetic for today’s computers, presents additional challenges due to special values and resulting unintuitive behaviors. This thesis has three main contributions that address existing gaps in automated reasoning about floating-point arithmetic, making it easier for developers and researchers to understand, verify, and trust the floating-point computations in their programs. First, we introduce the first floating-point support in a deductive verifier for the Java programming language. Our support in the KeY verifier automatically handles floating-point arithmetic and transcendental functions. We achieve this with a combination of delegation to external SMT solvers on one hand, and rule-based reasoning within KeY on the other, exploiting the complementary strengths of both approaches. As a result, this approach can prove functional floating-point properties for realistic programs. Second, inspired by KeY’s treatment of method calls and the need for a scalable roundoff error analysis, we present the first modular optimization-based roundoff error analysis for non-recursive procedural floating-point programs. Our key idea is to achieve modularity while maintaining reasonable accuracy by automatically computing procedure summaries that are a function of the input parameters. Technically, we extend an existing optimization-based roundoff error analysis and show how to effectively use first-order Taylor approximations to compute precise procedure summaries, and how to integrate those to obtain end-to-end roundoff error bounds. Third, our experience using SMT solvers to discharge KeY’s floating-point verification conditions revealed unexpected performance behavior, motivating a systematic study of floating-point reasoning in SMT solvers. We propose a metamorphic testing approach that uses semantics-preserving rewrite rules, focusing on floating-point special values, to uncover unexpected performance behavior in SMT solvers’ handling of floating-point formulas, such as an increase in solving time when the SMT queries are simplified. Using real-world test inputs, our approach can identify such performance bugs for every SMT solver tested.

The synthesis of logical controllers that guarantee desired specifications is a central problem in the design of cyber-physical systems (CPS). In practice, such guarantees rely on assumptions about how the controller interacts with its environment. These assumptions restrict environment behavior to make synthesis feasible, but in existing approaches they are often overly restrictive, leading to conservative designs and limiting the range of behaviors that systems can safely accommodate.

This thesis rethinks the role of assumptions in logical controller synthesis by emphasizing their \emph{permissiveness}---the ability to capture a wide range of admissible environment behaviors. We study permissive assumptions in two key settings: (a) interactions among multiple discrete components in distributed systems, and (b) interactions between high-level logical controllers and low-level physical dynamics in hybrid systems. In both settings, we develop theoretical and algorithmic foundations for computing and exploiting permissive assumptions to enable new design paradigms for logical controller synthesis.

For distributed systems, we define permissiveness as capturing all cooperative behaviors of other components that enable a controller to satisfy its specification. We present an algorithm for computing such assumptions in monolithic systems and extend it to distributed systems via a negotiation-based framework that iteratively constructs permissive assume-guarantee contracts for each component. These contracts enable decentralized synthesis and are applied to human-robot interaction, allowing robots to cooperate with humans whenever possible and request cooperation only when necessary.

For hybrid systems, we utilize permissive assumptions on the plant model---the abstract representation of physical dynamics---to address three key challenges. To enable seamless adaptation of controllers to changing logical contexts, i.e., changes in high-level goals or tasks, we introduce a novel synthesis framework that utilizes \emph{persistent live groups}, a class of assumptions capturing liveness properties of continuous dynamics. To improve scalability to large or uncertain plant models, we develop \emph{universal controllers} where decisions are conditioned on branching-time assumptions called \emph{prophecies}, which are learned from representative models and efficiently verified at runtime on unseen plant models. Finally, to enhance robustness under uncertainty or partial violations of assumptions on the plant model, we introduce a robust semantics for branching-time temporal logics, enabling formal reasoning about controller behavior under such violations.

Overall, this work enables correctness-by-construction synthesis while avoiding unnecessary conservatism, resulting in CPS that are more robust, scalable, and responsive.

Computers have become ubiquitous in everyday life and so have bugs in programs running on those computers. Research in the field of programming languages and verification has produced countless ways to attack the problem of software defects. This thesis concerns itself with two established techniques being applied to an unconventional setting.

Firstly, in the category of extending the applicability of program verification to more realistic settings, we demonstrate how to verify high-performance algorithms and data structures making use of highly efficient memory access patterns that are not automatically synchronized with main memory or other processors’ caches. Hardware and programming languages that expose these weakly or un-synchronized memory accesses are said to have weak memory models. The lack of synchronization in weak memory models goes directly against the assumption of sequential consistency which still sits at the heart of most verification works. Concretely, we show how to perform verification in weak memory models using an existing program logic framework, Iris, that was traditionally limited to sequential consistency. In building on Iris, we inherit its mechanized proof of soundness of the core logic as well as the ability to perform mechanized program verification.

Secondly, we propose to bring the benefits of dependent types to the process of writing and automating proofs in the Rocq proof assistant. This aims to adress the limitations of Rocq's oldest — and, for a long time, only — tactic language: Ltac. Ltac's pitfalls are numerous and it is arguably unable to fulfill the requirements of large verification projects. Our contribution is a new tactic language called Mtac2. Mtac2 is based on Mtac, a principled metaprogramming language for Rocq offering strongly typed primitives based on Rocq’s own dependent type system. Mtac’s primitives could already be used to implement some tactics but it lacks the ability to directly interact with Rocq’s proof state and to perform backwards reasoning on it. Mtac2 extends Mtac with support for backwards reasoning and keeps in line with Mtac’s tradition of strong types by introducing the concept of typed tactics. Typed tactics statically track the expected type of the current goal(s) and can rule out entire classes of mistakes that often plague Ltac tactics.

The modern datacentres that power the cloud use virtualised infrastructures to improve efficiency through sharing, but I/O datapaths resist consolidation and remain a source of inefficiency. In response, shared network datapaths have emerged as an approach to reduce overheads and improve utilisation of communication heavy applications by multiplexing resources and better absorbing bursts. The problem is that sharing leads to contention in multiplexed cores and causes performance interference between tenants. Furthermore, shared datapaths are rigid and tenants depend on network protocols implemented by the operators, foregoing opportunities for running specialised protocols due to the safety and performance interference risks from untrusted tenant code. For my dissertation, I propose a time protection mechanism that uses time based accounting and enforcement to prevent performance interference and guarantee tail latency isolation at microsecond scale. I also propose a programmable datapath substrate that exposes a programming interface that safely enables tenants to upload custom network protocols to a shared datapath, so they can specialise protocols to applications. Finally, these mechanisms are combined in a shared network stack that integrates with the virtualised infrastructure of modern datacentres and provides microsecond scale latencies.