Headshot

Clayton Thomas

Hello! I am a postdoctoral researcher at Microsoft Research New England (EconCs group). I try to understand and design algorithms in the presence of strategic behavior. (In academic jargon, I study mechanism and market design, from both an economic theory and a computer science theory perspective.) Lately, I've been most excited by questions of how these algorithms should be explained to real people—see our paper for the first instalment in this line of work. Other topics I've worked on include stable matchings, obviously strategyproof mechanisms, communication complexity, and combinatorial auctions.

I completed my PhD in the computer science theory group at Princeton, where I was very fortunate to be advised by Matt Weinberg. I completed my undergrad in mathematics and computer science at Purdue University, where Elena Grigorescu got me started on my journey to become a theorist. My other interests include functional programming, teaching, rock climbing, and slacklining.

Email: clathomas (attempted spam prevention) (at) (attempted spam prevention) microsoft.com

Publications and Preprints

[GT]
Yannai A. Gonczarowski and Clayton Thomas. Structural Complexities of Matching Mechanisms. STOC 2024. [arXiv]
[GHT]
Yannai A. Gonczarowski, Ori Heffetz, and Clayton Thomas. Strategyproofness-Exposing Mechanism Descriptions. EC 2023. [arXiv] [online experimental materials] [35min talk] [annotated abstract poster]
[CT]
Linda Cai and Clayton Thomas. The Short-Side Advantage in Random Matching Markets. SOSA 22. [arXiv] [2022 Slides] [2019 Poster]

A recent breakthrough of Ashlagi, Kanoria, and Leshno [AKL17] found that imbalance in the number of agents on either side of a random matching market has a profound effect on the expected characteristics of the market. Specifically, across all stable matchings, the “long side” (i.e. the side with a greater number of agents) receives significantly worse matches in expectation than the short side. If matchings are found via the classic one-side proposing deferred acceptance algorithm, this indicates that the difference between the proposing and the receiving side is essentially unimportant compared to the difference between the long and the short side.

We provide new intuition and a new proof for preliminary results in the direction of [AKL17], namely calculating the expected rank that an agent on the long side has for their optimal stable match.

[RSTWZ]
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Mathew Weinberg, and Junyao Zhao. Exponential Communication Separations between Notions of Selfishness. STOC 2021. [arXiv] [20min talk] [poster]
[T]
Clayton Thomas. Classification of Priorities Such That Deferred Acceptance is Obviously Strategyproof. EC 2021. [arXiv] [1min talk] [20min talk]
[ABSTZ]
Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao. Tiered Random Matching Markets: Rank is Proportional to Popularity. ITCS 2021. [arXiv]
[CTW]
Linda Cai, Clayton Thomas, and S. Matthew Weinberg. Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard. ITCS 2020. [arXiv]

State-of-the-art posted-price mechanisms for submodular bidders with m items achieve approximation guarantees of \( O((\log\log m)^3) \) [Assadi and Singla, 2019]. Their truthfulness, however, requires bidders to compute an NP-hard demand-query. Some computational complexity of this form is unavoidable, as it is NP-hard for truthful mechanisms to guarantee even an \( m^{1/2−\epsilon} \)-approximation for any \( \epsilon>0 \) [Dobzinski and Vondrák, 2016]. Together, these establish a stark distinction between computationally-efficient and communication-efficient truthful mechanisms.

We show that this distinction disappears with a mild relaxation of truthfulness, which we term implementation in advised strategies. Specifically, advice maps a tentative strategy either to that same strategy itself, or one that dominates it. We say that a player follows advice as long as they never play actions which are dominated by advice. A poly-time mechanism guarantees an \(\alpha\)-approximation in implementation in advised strategies if there exists poly-time advice for each player such that an \(\alpha\)-approximation is achieved whenever all players follow advice. Using an appropriate bicriterion notion of approximate demand queries (which can be computed in poly-time), we establish that (a slight modification of) the [Assadi and Singla, 2019] mechanism achieves the same \(O((\log\log m)^3)\) approximation in implementation in advised strategies.

[CT]
Linda Cai and Clayton Thomas. Representing All Stable Matchings by Walking a Maximal Chain. Mimeo. [arXiv]

The seminal book of Gusfield and Irving [GI89] provides a compact and algorithmically useful way to represent the collection of stable matches corresponding to a given set of preferences. In this paper, we reinterpret the main results of [GI89], giving a new proof of the characterization which is able to bypass a lot of the “theory building” of the original works. We also provide a streamlined and efficient way to compute this representation. Our proofs and algorithms emphasize the connection to well-known properties of the deferred acceptance algorithm.

[GGTZ]
V. Gandikota, E. Grigorescu, C. Thomas, and M. Zhu. Maximally recoverable codes: The bounded case. In Allerton Conference on Communication, Control, and Computing, 2017. [paper] [slides]

Modern distributed storage systems employ Maximally Recoverable codes that aim to balance failure recovery capabilities with encoding/decoding efficiency tradeoffs. Recent works of Gopalan et al (SODA 2017) and Kane et al (FOCS 2017) show that the alphabet size of grid-like topologies of practical interest must be large, a feature that hampers decoding efficiency.

To bypass such shortcomings, in this work we initiate the study of a weaker version of recoverability, where instead of being able to correct all correctable erasure patterns (as is the case for maximal recoverability), we only require to correct all erasure patterns of bounded size. The study of this notion reduces to a variant of a combinatorial problem studied in the literature, which is interesting in its own right.

We study the alphabet size of codes withstanding all erasure patterns of small (constant) size. We believe the questions we propose are relevant to both real storage systems and combinatorial analysis, and merit further study.

Old Stuff

Course Projects

Paper Survey: Expansion in the Johnson Graph With Uma Girish. [report]

The (generalized) Johnson graph is given by slices of the hypercube, and is important for under-standing probabilistically checkable proof systems and hardness of approximation. Characterizing the expansion of the Johnson Graph recently served as an important conceptual stepping stone to proving the 2-to-1 games conjecture. Here, we summarize the proof technique used, with a focus on simplicity and clarity of presentation.

Paper Survey: New Lower Bound Techniques for the Query Complexity of Truthful Mechanisms. With Uma Girish. For Matt Weinberg's "Open Problems in AGT" course. [report]

A survey of "Computational Efficiency Requires Simple Taxation" by Shahar Dobzinski.

You Can't Handle the Lie: Next-Hop Verification in BGP. With Gavriel Hirsch. For Jennifer Rexford's "Advanced Networking" course. [report]

BGP, the control-plane interdomain routing protocol used in today's internet, is notoriously difficult to secure and verify. This paper presents a new protocol called Next-Hop Verification, which reduces the set of contexts in which autonomous systems are incentivized to lie while participating in BGP. The protocol works by sharing information about BGP path announcements between different ASs, using the existing structure of the network, and checking those path announcements against the true flow of traffic in the data plane. We discuss the advantages and disadvantages of this new approach, and compare its effectiveness to that of previously considered verification techniques, focusing on cases where next-hop verification provably eliminates the incentives to lie in BGP. While our protocol is likely not practical, we believe it makes progress towards a more secure version of BGP in which ASs are able to "check each other" to enforce honesty.

Verifying Structural Invariants of Programs. With Jacob Bond. For Roopsha Samanta's "Reasoning about Programs" course at Purdue. [report] [slides]

A core problem in program verification is checking the invariance of programs under certain transformations. For example, a maximum function should be invariant under the order of a list, and a find function on binary search trees should return the same result for equivalent trees (i.e. those which represent the same ordered list). For both of these data types, we've found simple operations that "generate" all equivalent data types, in the sense that applying those permutations in some order to any data structure can result in all structures equivalent to the input. Thus, checking the invariance of programs for these data types can be reduced to checking their invariance under the more simple "generating" operations. This idea could potentially be useful for reasoning about algebraic data types with a notion of equivalence.

We have a more general, sound procedure that can verify the invariance of an arbitrary data type under some underlying representation (for example, a function on binary search trees should be invariant under the function "list" that returns the ordered list corresponding to the tree). However, our procedure includes an inductive synthesizer and an equivalence-of-programs verifier in its inner loop, so it is not likely to be practical.

Teaching

My teaching philosophy is best summed up by the following quote, from the first edition preface to Spivak's Calculus (some adjustments are my own).

Precision and rigor are neither deterrents to intuition, nor the ends in themselves, but the natural medium in which to formulate and think about mathematical computer science questions.

I am particularly interested in writing problem sets that both test and instruct students, and in crafting course policies and material which is simultaneously accessible to all motivated learners and challenging for those looking for a deeper understanding of the material.

Teaching experience: