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.

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.

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.

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.

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.