More Like this

1. An algorithm and computation to verify Legendre’s conjecture up to $$7\cdot 10^{13}$$

   https://doi.org/10.1007/s40993-024-00589-4  

   Sorenson, Jonathan; Webster, Jonathan (March 2025, Research in Number Theory)

   Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integern, there exists a prime between$$n^2$$ $n^2$and$$(n+1)^2$$ ${(n+1)}^2$. Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between$$n^2$$ $n^2$and$$n(n+1)$$ $n(n+1)$and also between$$n(n+1)$$ $n(n+1)$and$$(n+1)^2$$ ${(n+1)}^2$. Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all$$n\le N$$ $n\le N$in time$$O( N \log N \log \log N)$$ $O(NlogNloglogN)$and space$$N^{O(1/\log \log N)}$$ $N^{O(1/loglogN)}$. We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous$$N = 2\cdot 10^{9}$$ $N=2·{10}^9$up to$$N = 7.05\cdot 10^{13} > 2^{46}$$ $N=7.05·{10}^{13}>2^{46}$, so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors. 

   more » « less
2. Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

   https://doi.org/10.1007/s00453-023-01102-6  

   Akmal, Shyan; Chen, Lijie; Jin, Ce; Raj, Malvika; Williams, Ryan (February 2023, Algorithmica)

   Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$ $\tilde{O}\left(n\right)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time).Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$ $\tilde{O}\left(n^{\lceil k/2\rceil }\right)$(where$$k\ge 3$$ $k\ge 3$). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$ $\tilde{O}\left(m\right)$. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$ $\tilde{O}\left(n^2\right)$. Note this is optimal, as the matrix can have$$\Omega (n^2)$$ $\Omega \left(n^2\right)$nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$ $\tilde{O}\left(n^{2.94}\right)$nondeterministic time algorithm.Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$ $2^{n/2-n/O\left(k\right)}$. We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$ $2^{n/2}·\text{poly}\left(n\right)$-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$ $\#$SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$ $2^{n/2}/n^{\omega \left(1\right)}$time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$ $2^{4n/5}·\text{poly}\left(n\right)$. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$ $2^{2n/3}·\text{poly}\left(n\right)$time.Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$ $2^{n/3}·\text{poly}\left(n\right)$, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$ $2^{0.49991n}·\text{poly}\left(n\right)$time. 

   more » « less
3. A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices

   https://doi.org/10.1007/s00493-025-00187-7  

   Pettie, Seth; Tardos, Gábor (December 2025, Combinatorica)

   Abstract The theory of forbidden 0–1 matrices generalizes Turán-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parametertwin width. The foremost open problem in this area is to resolve thePach-Tardos conjecturefrom 2005, which states that if a forbidden pattern$$P\in \{0,1\}^{k\times l}$$ $P\in {\{0,1\}}^{k\times l}$isacyclic, meaning it is the bipartite incidence matrix of a forest, then$$\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)$$ $Ex(P,n)=O\left(n{log}^{C_P}n\right)$, where$$\operatorname {Ex}(P,n)$$ $Ex(P,n)$is the maximum number of 1s in aP-free$$n\times n$$ $n\times n$0–1 matrix and$$C_P$$ $C_P$is a constant depending only onP. This conjecture has been confirmed on many small patterns, specifically allPwith weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that$$\operatorname {Ex}(S_0,n),\operatorname {Ex}(S_1,n) \ge n2^{\Omega (\sqrt{\log n})}$$ $Ex(S_0,n),Ex(S_1,n)\ge n{2}^{\Omega \left(\sqrt{logn}\right)}$, where$$S_0,S_1$$ $S_0,S_1$are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class ofalternatingpatterns$$(P_t)$$ $\left(P_t\right)$, specifically that for every$$t\ge 2$$ $t\ge 2$,$$\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)$$ $Ex(P_t,n)=\Theta \left(n{(logn/loglogn)}^t\right)$. This is the first proof of an asymptotically sharp bound that is$$\omega (n\log n)$$ $\omega (nlogn)$. 

   more » « less
4. Curvature and sharp growth rates of log-quasimodes on compact manifolds

   https://doi.org/10.1007/s00222-025-01315-2  

   Huang, Xiaoqi; Sogge, Christopher D (March 2025, Inventiones mathematicae)

   Abstract We obtain new optimal estimates for the$$L^{2}(M)\to L^{q}(M)$$ $L^2\left(M\right)\to L^q\left(M\right)$,$$q\in (2,q_{c}]$$ $q\in (2,q_c]$,$$q_{c}=2(n+1)/(n-1)$$ $q_c=2(n+1)/(n-1)$, operator norms of spectral projection operators associated with spectral windows$$[\lambda ,\lambda +\delta (\lambda )]$$ $[\lambda ,\lambda +\delta (\lambda \left)\right]$, with$$\delta (\lambda )=O((\log \lambda )^{-1})$$ $\delta \left(\lambda \right)=O\left({(log\lambda )}^{-1}\right)$on compact Riemannian manifolds$$(M,g)$$ $(M,g)$of dimension$$n\ge 2$$ $n\ge 2$all of whose sectional curvatures are nonpositive or negative. We show that these two different types of estimates are saturated on flat manifolds or manifolds all of whose sectional curvatures are negative. This allows us to classify compact space forms in terms of the size of$$L^{q}$$ $L^q$-norms of quasimodes for each Lebesgue exponent$$q\in (2,q_{c}]$$ $q\in (2,q_c]$, even though it is impossible to distinguish between ones of negative or zero curvature sectional curvature for any$$q>q_{c}$$ $q>q_c$. 

   more » « less
5. Online Paging with Heterogeneous Cache Slots

   https://doi.org/10.1007/s00453-024-01270-z  

   Chrobak, Marek; Haney, Samuel; Liaee, Mehraneh; Panigrahi, Debmalya; Rajaraman, Rajmohan; Sundaram, Ravi; Young, Neal_E (October 2024, Algorithmica)

   Abstract It is natural to generalize the online$$k$$ $k$-Server problem by allowing each request to specify not only a pointp, but also a subsetSof servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a pagep, but also a subsetSof cache slots, and is satisfied by having a copy ofpin some slot inS. We call this problemSlot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family$${\mathcal {S}}\subseteq 2^{[k]}$$ $S\subseteq 2^{\left[k\right]}$of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache sizekand family$${\mathcal {S}}$$ $S$:If all request sets are allowed ($${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ $S=2^{\left[k\right]}\backslash \left\{\varnothing \right\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ($${\mathcal {S}}=\{[k]\}$$ $S=\left\{\right[k\left]\right\}$).As a function of$$|{\mathcal {S}}|$$ $\left|S\right|$andk, the optimal deterministic ratio is polynomial: at most$$O(k^2|{\mathcal {S}}|)$$ $O\left(k^2\right|S\left|\right)$and at least$$\Omega (\sqrt{|{\mathcal {S}}|})$$ $\Omega \left(\sqrt{\left|S\right|}\right)$.For any laminar family$${\mathcal {S}}$$ $S$of heighth, the optimal ratios areO(hk) (deterministic) and$$O(h^2\log k)$$ $O(h^{2}logk)$(randomized).The special case of laminar$${\mathcal {S}}$$ $S$that we callAll-or-One Pagingextends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio forweightedAll-or-One Paging is$$\Theta (k)$$ $\Theta \left(k\right)$. Offline All-or-One Paging is$$\mathbb{N}\mathbb{P}$$ $NP$-hard.Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set$$P$$ $P$ofpages, and is satisfied by fetching any page from$$P$$ $P$into the cache. The optimal ratios for the latter problem (with laminar family of heighth) are at mosthk(deterministic) and$$hH_k$$ $h{H}_k$(randomized). 

   more » « less