MIT Open Access Articles: Recent submissions

Now showing items 4-6 of 55067

    • Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin 

      Chen, Lijie; Li, Jiatu; Liang, Jingxun (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice (AMEXP/2nε) requires circuit complexity at least 2n/n. Previously, the best known such near-maximum lower bounds were for ...

    • List-Decoding Capacity Implies Capacity on the 𝑞-ary Symmetric Channel 

      Pernice, Francisco; Sprumont, Oscar; Wootters, Mary (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      It is known that the Shannon capacity of the q-ary symmetric channel (qSC) is the same as the list-decoding capacity of an adversarial channel, raising the question of whether there is a formal (and black-box) connection ...

    • A molecularly impermeable polymer from two-dimensional polyaramids 

      Ritt, Cody L; Quien, Michelle; Wei, Zitang; Gress, Hagen; Dronadula, Mohan T; e.a. (Springer Science and Business Media LLC, 2025-11-12)
      All polymers exhibit gas permeability through the free volume of entangled polymer chains1, 2–3. By contrast, two-dimensional (2D) materials including graphene stack densely and can exhibit molecular impermeability4, 5–6. ...