Jason Gaitonde

I am a fifth-year PhD student in the Department of Computer Science at Cornell University, where I am very fortunate to be advised by Éva Tardos. Before that, I graduated from Yale University with degrees in Mathematics (B.S., with distinction) and Economics (B.A.).

I am broadly interested in theoretical computer science. In particular, my research to date focuses on theoretical problems at the intersection of algorithms, learning, game theory, networks, and randomness.

Preprints

Bounds on the Covariance Matrix of the Sherrington-Kirkpatrix Model, with Ahmed El Alaoui.
[Abstract] [PDF]
We consider the Sherrington-Kirkpatrick model with no external field and inverse temperature $\beta<1$ and prove that the expected operator norm of the covariance matrix of the Gibbs measure is bounded by a constant depending only on $\beta$. This answers an open question raised by Talagrand, who proved a bound of $C(\beta) (\log n)^8$. Our result follows by establishing an approximate formula for the covariance matrix which we obtain by differentiating the TAP equations and then optimally controlling the associated error terms. We complement this result by showing diverging lower bounds on the operator norm, both at the critical and low temperatures.

Conference Papers
Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence, with Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins.
To appear in Innovations in Theoretical Computer Science 2023 (ITCS 2023).
[Abstract]    [PDF]
We study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in the context of repeated auctions with budgets. Such algorithms are commonly used as bidding agents in Internet advertising platforms. We show that when agents simultaneously apply a natural form of gradient-based pacing, the liquid welfare obtained over the course of the learning dynamics is at least half the optimal expected liquid welfare obtainable by any allocation rule. Crucially, this result holds without requiring convergence of the dynamics, allowing us to circumvent known complexity-theoretic obstacles of finding equilibria. This result is also robust to the correlation structure between agent valuations and holds for any core auction, a broad class of auctions that includes first-price, second-price, and generalized second-price auctions. For individual guarantees, we further show such pacing algorithms enjoy dynamic regret bounds for individual value maximization, with respect to the sequence of budget-pacing bids, for any auction satisfying a monotone bang-for-buck property.

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets, with Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang.
International Conference on Randomization and Computation 2022 (RANDOM 2022).
[Abstract]    [PDF]
Fast mixing of random walks on hypergraphs (simplicial complexes) has recently led to myriad breakthroughs throughout theoretical computer science. Many important applications, however, (e.g.\ to LTCs, 2-2 games) rely on a more general class of underlying structures called \emph{posets}, and crucially take advantage of non-simplicial structure. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g.\ simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how \emph{regularity} controls the spectral decay and edge-expansion of corresponding random walks. We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit strong (even exponential) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly---a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on expanding posets in the $\ell_2$-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on $\ell_\infty$ rather than $\ell_2$-structure.

Fractional Pseudorandom Generators from Any Fourier Level, with Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty.
Computational Complexity Conference 2021 (CCC 2021).
[Abstract]    [PDF]
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [CHHL18, CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels [CHHL18], or has polynomial dependence on the error parameter in the seed length [CHLT19], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(\log n)$ levels is sufficient to recover the seed length in [CHHL], which requires bounds on the entire tail. We obtain our results by an alternate analysis of fractional PRGs using Taylor's theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHHLZ20], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for $\mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio08].

Virtues of Patience in Strategic Queuing Systems, with Éva Tardos.
The Twenty-Second ACM Conference on Economics and Computation (EC 21).
[Abstract]    [PDF]
We consider the problem of selfish agents in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies, resulting in a highly dependent random process. In classical work for learning in repeated games, the learners evaluate the outcome of their strategy in each step---in our context, this means that queues estimate their success probability at each server. Earlier work by the authors [in EC'20] shows that with no-regret learners the system needs twice the capacity as would be required in the coordinated setting to ensure queue lengths remain stable, despite the selfish behavior of the queues. In this paper, we demonstrate that this myopic way of evaluating outcomes is suboptimal: if more patient queues choose strategies that selfishly maximize their long-run success rate, stability can be ensured with just $\frac{e}{e-1}\approx 1.58$ times extra capacity, strictly better than what is possible assuming the no-regret property. As these systems induce highly dependent random processes, our analysis draws heavily on techniques from the theory of stochastic processes to establish various game-theoretic properties of these systems. Though these systems are random even under any fixed stationary policies by the queues, we show using careful probabilistic arguments that surprisingly, under such fixed policies, these systems have essentially deterministic and explicit asymptotic behavior. We show that the growth rate of a set can be written as the ratio of a submodular and modular function, and use the resulting explicit description to show that the subsets of queues with largest growth rate is closed under union and non-disjoint intersections, which we use in turn to prove the claimed sharp bicriteria result for the equilibria of the resulting system. Our equilibrium analysis relies on a novel deformation argument towards a more analyzable solution that is quite different from classical price of anarchy bounds. While the intermediate points in this deformation will not be Nash, the structure will ensure the relevant constraints and incentives similarly hold to establish monotonicity along this continuous path.

Polarization in Geometric Opinion Dynamics, with Jon Kleinberg and Éva Tardos.
The Twenty-Second ACM Conference on Economics and Computation (EC 21).
[Abstract]    [PDF]
In light of increasing recent attention to political polarization, understanding how polarization can arise poses an important theoretical question. While more classical models of opinion dynamics seem poorly equipped to study this phenomenon, a recent novel approach by Hᶏzla, Jin, Mossel, and Ramnarayan [HJMR20] proposes a simple geometric model of opinion evolution that provably exhibits strong polarization in specialized cases. Moreover, polarization arises quite organically in their model: in each time step, each agent updates opinions according to their correlation/response with an issue drawn at random. However, their techniques do not seem to extend beyond a set of special cases they identify, which benefit from fragile symmetry or contractiveness assumptions, leaving open how general this phenomenon really is. In this paper, we further the study of polarization in related geometric models. We show that the exact form of polarization in such models is quite nuanced: even when strong polarization does not hold, it is possible for weaker notions of polarization to nonetheless attain. We provide a concrete example where weak polarization holds, but strong polarization provably fails. However, we show that strong polarization provably holds in many variants of the HJMR model, which are also robust to a wider array of distributions of random issues---this suggests that the form of polarization introduced by HJMR is more universal than suggested by their special cases. We also show that the weaker notions connect more readily to the theory of Markov chains on general state spaces.
Stability and Learning in Strategic Queuing Systems, with Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract]    [PDF]    [EC Talk]
Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service. Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. We analyze this random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds.

Adversarial Perturbations of Opinion Dynamics in Networks, with Jon Kleinberg and Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract]    [PDF]    [EC Talk]
We study the connections between network structure, opinion dynamics, and an adversary's power to artificially induce disagreements. We approach these questions by extending models of opinion formation in the social sciences to represent scenarios, familiar from recent events, in which external actors seek to destabilize communities through sophisticated information warfare tactics via fake news and bots. In many instances, the intrinsic goals of these efforts are not necessarily to shift the overall sentiment of the network, but rather to induce discord. These perturbations diffuse via opinion dynamics on the underlying network, through mechanisms that have been analyzed and abstracted through work in computer science and the social sciences. We investigate the properties of such attacks, considering optimal strategies both for the adversary seeking to create disagreement and for the entities tasked with defending the network from attack. We show that for different formulations of these types of objectives, different regimes of the spectral structure of the network will limit the adversary's capacity to sow discord; this enables us to qualitatively describe which networks are most vulnerable against these perturbations. We then consider the algorithmic task of a network defender to mitigate these sorts of adversarial attacks by insulating nodes heterogeneously; we show that, by considering the geometry of this problem, this optimization task can be efficiently solved via convex programming. Finally, we generalize these results to allow for two network structures, where the opinion dynamics process and the measurement of disagreement become uncoupled, and determine how the adversary's power changes; for instance, this may arise when opinion dynamics are controlled an online community via social media, while disagreement is measured along "real-world" connections.