More Like this

1. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
2. A case study of SMEFT $$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ effects in diboson processes: pp → W±(ℓ±ν)γ

   https://doi.org/10.1007/JHEP05(2024)223  

   Martin, Adam (May 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> In this paper we explorepp→W^±(ℓ^±ν)γto$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$in the SMEFT expansion. Calculations to this order are necessary to properly capture SMEFT contributions that grow with energy, as the interference between energy-enhanced SMEFT effects at$$ \mathcal{O}\left(1/{\Lambda}^2\right) $$ $O\left(1/{\Lambda }^2\right)$and the Standard Model is suppressed. We find that there are several dimension eight operators that interfere with the Standard Model and lead to the same energy growth, ~$$ \mathcal{O}\left({E}^4/{\Lambda}^4\right) $$ $O\left(E^4/{\Lambda }^4\right)$, as dimension six squared. While energy-enhanced SMEFT contributions are a main focus, our calculation includes the complete set of$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$SMEFT effects consistent with U(3)⁵flavor symmetry. Additionally, we include the decay of theW^±→ ℓ^±ν, making the calculation actually$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$. As such, we are able to study the impact of non-resonant SMEFT operators, such as$$ \left({L}^{\dagger }{\overline{\sigma}}^{\mu }{\tau}^IL\right)\left({Q}^{\dagger }{\overline{\sigma}}^{\nu }{\tau}^IQ\right) $$ $\left(L^{†}{\overline{\sigma }}^{\mu }{\tau }^{I}L\right)\left(Q^{†}{\overline{\sigma }}^{\nu }{\tau }^{I}Q\right)$B_μν, which contribute to$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$directly and not to$$ \overline{q}{q}^{\prime}\to {W}^{\pm}\gamma $$ $\overline{q}{q}^{\prime }\to W^{\pm }\gamma$. We show several distributions to illustrate the shape differences of the different contributions. 

   more » « less
3. 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)

   Abstract 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
4. Construction of a Dirichlet form on Metric Measure Spaces of Controlled Geometry

   https://doi.org/10.1007/s11118-024-10144-6  

   Butaev, Almaz; Luo, Liangbing; Shanmugalingam, Nageswari (June 2024, Potential Analysis)

   Abstract Given a compact doubling metric measure spaceXthat supports a 2-Poincaré inequality, we construct a Dirichlet form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$that is comparable to the upper gradient energy form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$. Our approach is based on the approximation ofXby a family of graphs that is doubling and supports a 2-Poincaré inequality (see [20]). We construct a bilinear form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$using the Dirichlet form on the graph. We show that the$$\Gamma $$ $\Gamma$-limit$$\mathcal {E}$$ $E$of this family of bilinear forms (by taking a subsequence) exists and that$$\mathcal {E}$$ $E$is a Dirichlet form onX. Properties of$$\mathcal {E}$$ $E$are established. Moreover, we prove that$$\mathcal {E}$$ $E$has the property of matching boundary values on a domain$$\Omega \subseteq X$$ $\Omega \subseteq X$. This construction makes it possible to approximate harmonic functions (with respect to the Dirichlet form$$\mathcal {E}$$ $E$) on a domain inXwith a prescribed Lipschitz boundary data via a numerical scheme dictated by the approximating Dirichlet forms, which are discrete objects. 

   more » « less
5. On the Moduli of Lipschitz Homology Classes

   https://doi.org/10.1007/s12220-025-01916-6  

   Kangasniemi, Ilmari; Prywes, Eden (February 2025, The Journal of Geometric Analysis)

   Abstract We define a type of modulus$$\operatorname {dMod}_p$$ ${dMod}_p$for Lipschitz surfaces based on$$L^p$$ $L^p$-integrable measurable differential forms, generalizing the vector modulus of Aikawa and Ohtsuka. We show that this modulus satisfies a homological duality theorem, where for Hölder conjugate exponents$$p, q \in (1, \infty )$$ $p,q\in (1,\infty )$, every relative Lipschitzk-homology classchas a unique dual Lipschitz$$(n-k)$$ $(n-k)$-homology class$$c'$$ $c^{\prime }$such that$$\operatorname {dMod}_p^{1/p}(c) \operatorname {dMod}_q^{1/q}(c') = 1$$ ${dMod}_p^{1/p}\left(c\right){dMod}_q^{1/q}\left(c^{\prime }\right)=1$and the Poincaré dual ofcmaps$$c'$$ $c^{\prime }$to 1. As$$\operatorname {dMod}_p$$ ${dMod}_p$is larger than the classical surface modulus$$\operatorname {Mod}_p$$ ${Mod}_p$, we immediately recover a more general version of the estimate$$\operatorname {Mod}_p^{1/p}(c) \operatorname {Mod}_q^{1/q}(c') \le 1$$ ${Mod}_p^{1/p}\left(c\right){Mod}_q^{1/q}\left(c^{\prime }\right)\le 1$, which appears in works by Freedman and He and by Lohvansuu. Our theory is formulated in the general setting of Lipschitz Riemannian manifolds, though our results appear new in the smooth setting as well. We also provide a characterization of closed and exact Sobolev forms on Lipschitz manifolds based on integration over Lipschitzk-chains. 

   more » « less