8 papers
Bounds on the covariance matrix of the Sherrington-Kirkpatrick model
Ahmed El Alaoui, Jason Gaitonde
We consider the Sherrington-Kirkpatrick model with no external field and inverse temperature and prove that the expected operator norm of the covariance matrix of the Gibbs m…
Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
Jason Gaitonde, Yingkai Li, Bar Light +2
We study the aggregate welfare and individual regret guarantees of dynamic \emph{pacing algorithms} in the context of repeated auctions with budgets. Such algorithms are commonly u…
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Jason Gaitonde, Max Hopkins, Tali Kaufman +2
We study the relationship between the underlying structure of posets and the spectral and combinatorial properties of their higher-order random walks. While fast mixing of random w…
Polarization in Geometric Opinion Dynamics
Jason Gaitonde, Jon Kleinberg, Éva Tardos
In light of increasing recent attention to political polarization, understanding how polarization can arise poses an important theoretical question. While more classical models of…
Virtues of Patience in Strategic Queuing Systems
Jason Gaitonde, Eva Tardos
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 e…
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee +2
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit Fourier tail bounds for classes…
Stability and Learning in Strategic Queuing Systems
Jason Gaitonde, Eva Tardos
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…
Adversarial Perturbations of Opinion Dynamics in Networks
Jason Gaitonde, Jon Kleinberg, Eva Tardos
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…