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 (at) microsoft.com
Publications and Preprints

[GT]

Yannai A. Gonczarowski and Clayton Thomas.
[GHT]

Yannai A. Gonczarowski, Ori Heffetz, and Clayton Thomas.
annotated abstractposter]

[CT]

Linda Cai and Clayton Thomas.
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.
[T]

Clayton Thomas.
[ABSTZ]

Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao.
[CTW]

Linda Cai, Clayton Thomas, and S. Matthew Weinberg.
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.
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.
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

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.

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

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.

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 sciencequestions.

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:

- Sprint 2020: Preceptor for COS 445 (Economics and Computing) at Princeton.
- Fall 2019: Preceptor for COS 340 (Reasoning about Computation) at Princeton.
- Spring and Fall 2015: Recitation Teaching Assistant for CS 182 (Foundations of Computer Science) at Purdue. I kept a small homepage with supplemental exercises I wrote.