MIT Open Access Articles: Recent submissions

Now showing items 28-30 of 55096

    • All-Pairs Shortest Paths with Few Weights per Node 

      Abboud, Amir; Fischer, Nick; Jin, Ce; Williams, Virginia Vassilevska; Xi, Zoe (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most d distinct weights on the outgoing edges from every node. For d=n this is the classical (unrestricted) APSP problem ...

    • Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses 

      Huang, Brice; Mohanty, Sidhanth; Rajaraman, Amit; Wu, David X. (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      There has been a recent surge of powerful tools to show rapid mixing of Markov chains, via functional inequalities such as Poincaré inequalities. In many situations, Markov chains fail to mix rapidly from a worst-case ...

    • Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics 

      Gaitonde, Jason; Moitra, Ankur; Mossel, Elchanan (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      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 ...