The Nautalis in Vedauwoo, Wyoming
Me, hanging around in Rocktown, GA

Clay Thomas

Hello! I'm a PhD student in the Computer Science Theory group at Princeton. I'm broadly interested in TCS, and recently I've been studying Algorithmic Game Theory. I completed my undergrad in Mathematics and Computer Science at Purdue University, where I was fortunate to be advised by Elena Grigorescu.

My other interests include rock climbing, gymnastics, and teaching.

Here's my CV

Publications

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.

Projects

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.

Small Projects

These are all smaller, simpler, code-based projects which I wrote independently. Some of them contain kernels of ideas which I would like to return to some day, so please contact me if these sound interesting and you would like to work on them!

Fair Read-Write Locks

March 2016. A kernel-level read-write lock implementation in the Xinu operating system, giving readers and writers access in exactly the order they request it.

This small project inspired a question I really want to come back to one day: Are all synchronization protocols implementable with common sets of synchronization primitives? For example, is it possible to implement fair read-write locks using only semaphores? No implementation I have seen is actually fair in the sense discussed above. See the repo for more information.

Free Decision Trees — Library and Blog Post

January 2016. A rudimentary library to train and apply decision trees represented in an elegant way. This project was inspired by the observation that the Haskell data type Free ((->) r) Bool could be used to represent decision trees. The result is a blog-post style explanation of the concept and implementation, which I think is a good way to understand free monads.

Other Things

Teaching

I enjoy lecturing and explaining foundational concepts. Furthermore, I like writing challenging and interesting practice questions for students (including thinking of exercises for myself!).

When I TAed for Purdue's "Foundations of computer science" course, I wrote some lecture notes for a few of my "practice, study, observation" sessions and I wrote review materials for the midterm and final. You can find those materials here.

Haskell

My manager at Facebook told me that there's an old saying among Haskellers: "The best way to learn monads is to write a monad tutorial, then throw it away" because nobody else will ever find it useful. Personally, I think monad tutorials are a myth. Writing a monad tutorial is like writing a "data structures" tutorial or a "programming patterns" tutorial: way too broad. Anyway, here's my monad tutorial.

I want make some simplified versions of Haskell libraries that are easier to understand so people can learn the concepts of the libraries. Here's the start of that project for the Lens library.

Rock Climbing

Before starting grad school, I took a gap semester to go on a cross-country rock climbing road trip. I made an infographic attempting to show my progress and some of the highs and lows.

Stuff from the distant past

Here's a hackathon project I worked on to help you meet your friends at different Purdue dining courts.

Here's a Purdue problem of the week from back in the day. Here is a partial graph of the function constructed, where I enumerated rationals in some simple order and plotted the value of the function there. Seems like the graph is dense in the plane, but I don't think I even knew what "dense" meant at the time.

Here's an image I made to explain how to derive an equation of the form z = f(x,y) for the graph of a Torus.

Here's a little writeup of a counting problem that I found tough and interesting at the time.

Here's a writeup I did when I took physics about the fact that objects always roll down slopes with less acceleration than if they were slipping down the slope without rolling. I also construct shapes with acceleration arbitrarily close to the "slipping acceleration".