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. The weight hierarchy of decreasing norm-trace codes

   https://doi.org/10.1007/s10623-025-01619-7  

   Camps-Moreno, Eduardo; López, Hiram H; Matthews, Gretchen L; San-José, Rodrigo (April 2025, Designs, Codes and Cryptography)

   Abstract The Generalized Hamming weights and their relative version, which generalize the minimum distance of a linear code, are relevant to numerous applications, including coding on the wire-tap channel of type II,t-resilient functions, bounding the cardinality of the output in list decoding algorithms, ramp secret sharing schemes, and quantum error correction. The generalized Hamming weights have been determined for some families of codes, including Cartesian codes and Hermitian one-point codes. In this paper, we determine the generalized Hamming weights of decreasing norm-trace codes, which are linear codes defined by evaluating sets of monomials that are closed under divisibility on the rational points of the extended norm-trace curve given by$$x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y$$ $x^u=y^{q^{s-1}}+y^{q^{s-2}}+\cdots +y$over the finite field of cardinality$$q^s$$ $q^s$, whereuis a positive divisor of$$\frac{q^s - 1}{q - 1}$$ $\frac{q^s-1}{q-1}$. As a particular case, we obtain the weight hierarchy of one-point norm-trace codes and recover the result of Barbero and Munuera (2001) giving the weight hierarchy of one-point Hermitian codes. We also study the relative generalized Hamming weights for these codes and use them to construct impure quantum codes with excellent parameters. 

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