More Like this

1. Deformation of d = 4, $$ \mathcal{N} $$ ≥ 5 supergravities breaks nonlinear local supersymmetry

   https://doi.org/10.1007/JHEP06(2023)156  

   Kallosh, Renata ; Yamada, Yusuke ( June 2023 , Journal of High Energy Physics)

   We studyd= 4,$$ \mathcal{N} $$$N$≥ 5 supergravities and their deformation via candidate counterterms, with the purpose to absorb UV divergences. We generalize the earlier studies of deformation and twisted self-duality constraint to the case with unbroken local$$ \mathcal{H} $$$H$-symmetry in presence of fermions. We find that the deformed action breaks nonlinear local supersymmetry. We show that all known cases of enhanced UV divergence cancellations are explained by nonlinear local supersymmetry.

   This result implies, in particular, that if$$ \mathcal{N} $$$N$= 5 supergravity at five loop will turn out to be UV divergent, the deformed theory will be BRST inconsistent. If it will be finite, it will be a consequence of nonlinear local supersymmetry and E7-type duality.

    

   more » « less
2. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil ; Williams, R. Ryan ( November 2022 , Theory of Computing Systems)

   We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

   #SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   #SAT algorithms for$2^{n^{{\varepsilon }}}$$2^{n^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$$2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    

   more » « less
3. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra ; Inamdar, Tanmay ; Quanrud, Kent ; Varadarajan, Kasturi ; Zhang, Zhao ( June 2022 , Journal of Combinatorial Optimization)

   We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$$f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$$k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$$f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$$f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

    

   more » « less
4. Savior curvatons and large non-Gaussianity

   https://doi.org/10.1007/JHEP11(2023)218  

   Lodman, Jackie ; Lu, Qianshu ; Randall, Lisa ( November 2023 , Journal of High Energy Physics)

   Curvatons are light (compared to the Hubble scale during inflation) spectator fields during inflation that potentially contribute to adiabatic curvature perturbations post-inflation. They can alter CMB observables such as the spectral indexn_s, the tensor-to-scalar ratior, and the local non-Gaussianity$$ {f}_{\textrm{NL}}^{\left(\textrm{loc}\right)} $$$f_{\mathrm{NL}}^{\left(\mathrm{loc}\right)}$. We systematically explore the observable space of a curvaton with a quadratic potential. We find that when the underlying inflation model does not satisfy then_sandrobservational constraints but can be made viable with a significant contribution from what we call a savior curvaton, a large$$ \left|{f}_{\textrm{NL}}^{\left(\textrm{loc}\right)}\right| $$$\left(f_{\mathrm{NL}}^{\left(\mathrm{loc}\right)}\right)$>0.05, such that the model is distinguishable from single-field inflation, is inevitable. On the other hand, when the underlying inflation model already satisfies then_sandrobservational constraints, so significant curvaton contribution is forbidden, a large$$ \left|{f}_{\textrm{NL}}^{\left(\textrm{loc}\right)}\right| $$$\left(f_{\mathrm{NL}}^{\left(\mathrm{loc}\right)}\right)$>0.05 is possible in the exceptional case when the isocurvature fluctuation in the curvaton fluid is much greater than the global curvature fluctuation.

    

   more » « less
5. Boundedness of Complements for Log Calabi–Yau Threefolds

   https://doi.org/10.1007/s42543-022-00057-x  

   Chen, Guodu ; Han, Jingjun ; Xue, Qingyuan ( February 2023 , Peking Mathematical Journal)

   In this paper, we study the theory of complements, introduced by Shokurov, for Calabi–Yau type varieties with the coefficient set [0, 1]. We show that there exists a finite set of positive integers$$\mathcal {N}$$$N$, such that if a threefold pair$$(X/Z\ni z,B)$$$(X/Z\ni z,B)$has an$$\mathbb {R}$$$R$-complement which is klt over a neighborhood ofz, then it has ann-complement for some$$n\in \mathcal {N}$$$n\in N$. We also show the boundedness of complements for$$\mathbb {R}$$$R$-complementary surface pairs.

    

   more » « less