ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 15, 2025
We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fundamental results in the area all assume independent samples from the distrib ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Theory of Computing · June 10, 2024
We revisit the well-studied problem of efficiently learning the underlying structure and parameters of an Ising model from data. Current algorithmic approaches achieve essentially optimal sample complexity when samples are generated i.i.d. from the station ...
Full textCite
Journal ArticleElectronic Communications in Probability · January 1, 2024
We consider the Sherrington-Kirkpatrick model with no external field and inverse temperature β < 1 and prove that the expected operator norm of the covariance matrix of the Gibbs measure is bounded by a constant depending only on β. This answers an open qu ...
Full textCite
Journal ArticleJournal of the ACM · May 23, 2023
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 algorithmic game theory. Classical work on such bounds in repeated games makes the strong as ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics Lipics · September 1, 2022
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 s ...
Full textCite
ConferenceEC 2021 Proceedings of the 22nd ACM Conference on Economics and Computation · July 18, 2021
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 nov ...
Full textCite
ConferenceEC 2021 Proceedings of the 22nd ACM Conference on Economics and Computation · July 18, 2021
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 arriv ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics Lipics · July 1, 2021
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [4, 6] that exploit L1 Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bo ...
Full textCite
ConferenceEC 2020 Proceedings of the 21st ACM Conference on Economics and Computation · July 13, 2020
In this paper, 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 mathematical social sciences to ...
Full textCite
ConferenceEC 2020 Proceedings of the 21st ACM Conference on Economics and Computation · July 13, 2020
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 algorithmic game theory. In this paper, we study this phenomenon in the context of a game mo ...
Full textCite
