More Like this

1. Insight into Voting Problem Complexity Using Randomized Classes

   https://doi.org/10.24963/ijcai.2022/42  

   Fitzsimmons, Zack ; Hemaspaandra, Edith ( July 2022 , International Joint Conference on Artificial Intelligence (IJCAI))

   The first step in classifying the complexity of an NP problem is typically showing the problem in P or NP-complete. This has been a successful first step for many problems, including voting problems. However, in this paper we show that this may not always be the best first step. We consider the problem of constructive control by replacing voters (CCRV) introduced by Loreggia et al. [2015, https://dl.acm.org/doi/10.5555/2772879.2773411] for the scoring rule First-Last, which is defined by (1, 0, ..., 0, -1). We show that this problem is equivalent to Exact Perfect Bipartite Matching, and so CCRV for First-Last can be determined in random polynomial time. So on the one hand, if CCRV for First-Last is NP-complete then RP = NP, which is extremely unlikely. On the other hand, showing that CCRV for First-Last is in P would also show that Exact Perfect Bipartite Matching is in P, which would solve a well-studied 40-year-old open problem.Considering RP as an option for classifying problems can also help classify problems that until now had escaped classification. For example, the sole open problem in the comprehensive table from Erdélyi et al. [2021, https://doi.org/10.1007/s10458-021-09523-9] is CCRV for 2-Approval. We show that this problem is in RP, and thus easy since it is widely assumed that P = RP.

    

   more » « less
2. Global Well-Posedness for $$H^{-1}(\mathbb {R})$$ Perturbations of KdV with Exotic Spatial Asymptotics

   https://doi.org/10.1007/s00220-022-04522-7  

   Laurens, Thierry ( November 2022 , Communications in Mathematical Physics)

   Given a suitable solutionV(t, x) to the Korteweg–de Vries equation on the real line, we prove global well-posedness for initial data$$u(0,x) \in V(0,x) + H^{-1}(\mathbb {R})$$$u(0,x)\in V(0,x)+H^{-1}\left(R\right)$. Our conditions onVdo include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$$V(0,x)\in H^5(R/Z)$satisfy our hypotheses. In particular, we can treat localized perturbations of the much-studied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.https://doi.org/10.1088/1361-6544/ac37f5) we show that smooth step-like initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4) where$$V\equiv 0$$$V\equiv 0$. In that setting, it is known that$$H^{-1}(\mathbb {R})$$$H^{-1}\left(R\right)$is sharp in the class of$$H^s(\mathbb {R})$$$H^s\left(R\right)$spaces.

    

   more » « less
3. Global Nonlinear Stability of Schwarzschild under polarized perturbations

   https://doi.org/10.2307/j.ctv15r57cw  

   Klainerman, S ; Szeftel, J ( October 2020 , Annals of mathematics studies)

   Chang, A ; Griffith, P ; Naor, A (Ed.)

   We prove the nonlinear stability of the Schwarzschild spacetime under axially symmetric polarized perturbations, i.e. solutions of the Einstein vacuum equations for asymptotically flat $1+3$ dimensional Lorentzian metrics which admit a hypersurface orthogonal spacelike Killing vectorfield with closed orbits. While building on the remarkable advances made in the last 15 years on establishing quantitative linear stability, the paper introduces a series of new ideas among which we emphasize the \textit{general covariant modulation} (GCM) procedure which allows us to construct, dynamically, the center of mass frame of the final state. The mass of the final state itself is tracked using the well known Hawking mass relative to a well adapted foliation itself connected to the center of mass frame. Our work here is the first to prove the nonlinear stability of Schwarzschild in a restricted class of nontrivial perturbations. To a large extent, the restriction to this class of perturbations is only needed to ensure that the final state of evolution is another Schwarzschild space. We are thus confident that our procedure may apply in a more general setting. 

   more » « less
4. Gravity from thermodynamics: Optimal transport and negative effective dimensions

   https://doi.org/10.21468/SciPostPhys.15.2.039  

   De Luca, Giuseppe Bruno ; De Ponti, Nicolò ; Mondino, Andrea ; Tomasiello, Alessandro ( January 2023 , SciPost Physics)

   We prove an equivalence between the classical equations of motion governing vacuum gravity compactifications (and more general warped-product spacetimes) and a concavity property of entropy under time evolution. This is obtained by linking the theory of optimal transport to the Raychaudhuri equation in the internal space, where the warp factor introduces effective notions of curvature and (negative) internal dimension. When the Reduced Energy Condition is satisfied, concavity can be characterized in terms of the cosmological constant\Lambda$\Lambda$; as a consequence, the masses of the spin-two Kaluza-Klein fields obey bounds in terms of\Lambda$\Lambda$alone. We show that some Cheeger bounds on the KK spectrum hold even without assuming synthetic Ricci lower bounds, in the large class of infinitesimally Hilbertian metric measure spaces, which includes D-brane and O-plane singularities. As an application, we show how some approximate string theory solutions in the literature achieve scale separation, and we construct a new explicit parametrically scale-separated AdS solution of M-theory supported by Casimir energy.

    

   more » « less
5. The Nonlinear Schrödinger Equation for Orthonormal Functions II: Application to Lieb–Thirring Inequalities

   https://doi.org/10.1007/s00220-021-04039-5  

   Frank, Rupert L. ; Gontier, David ; Lewin, Mathieu ( May 2021 , Communications in Mathematical Physics)

   In this paper we disprove part of a conjecture of Lieb and Thirring concerning the best constant in their eponymous inequality. We prove that the best Lieb–Thirring constant when the eigenvalues of a Schrödinger operator$$-\Delta +V(x)$$$-\Delta +V\left(x\right)$are raised to the power$$\kappa $$$\kappa$is never given by the one-bound state case when$$\kappa >\max (0,2-d/2)$$$\kappa >max(0,2-d/2)$in space dimension$$d\ge 1$$$d\ge 1$. When in addition$$\kappa \ge 1$$$\kappa \ge 1$we prove that this best constant is never attained for a potential having finitely many eigenvalues. The method to obtain the first result is to carefully compute the exponentially small interaction between two Gagliardo–Nirenberg optimisers placed far away. For the second result, we study the dual version of the Lieb–Thirring inequality, in the same spirit as in Part I of this work Gontier et al. (The nonlinear Schrödinger equation for orthonormal functions I. Existence of ground states. Arch. Rat. Mech. Anal, 2021.https://doi.org/10.1007/s00205-021-01634-7). In a different but related direction, we also show that the cubic nonlinear Schrödinger equation admits no orthonormal ground state in 1D, for more than one function.

    

   more » « less