More Like this

1. Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting

   Hemaspaandra, Lane A.; Juvekar, Mandar.; Nadjimzadah, Arian.; Phillips, Patrick (August 2022, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science)

   Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕P (and thus that FewP ⊆ ⊕P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappy”-ness) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES . 

   more » « less
2. Classification via Two-Way Comparisons

   https://doi.org/10.1145/3709361  

   Chrobak, Marek; Young, Neal_E (February 2025, ACM Transactions on Algorithms)

   Given a weighted, ordered query set\(Q\)and a partition of\(Q\)into classes, we study the problem of computing a minimum-cost decision tree that, given any query\(q\in Q\), uses equality tests and less-than tests to determine\(q\)'s class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify\(q\), not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes. 

   more » « less
3. Tiny Pointers

   https://doi.org/10.1145/3700594  

   Bender, Michael A; Conway, Alex; Farach-Colton, Martín; Kuszmaul, William; Tagliavini, Guido (October 2024, ACM Transactions on Algorithms)

   This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional\(\log n\)-bit pointers can be replaced with\(o(\log n)\)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor\(1-\delta\), then the optimal tiny-pointer size is\(\Theta(\log\log\log n+\log\delta^{-1})\)bits in the fixed-size case, and\(\Theta(\log\delta^{-1})\)expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that:A data structure storing\(n\)\(v\)-bit values for\(n\)keys with constant-factor time modifications/queries can be implemented to take space\(nv+O(n\log^{(r)}n)\)bits, for any constant\(r\gt0\), as long as the user stores a tiny pointer of expected size\(O(1)\)with each key—here,\(\log^{(r)}n\)is the\(r\)-th iterated logarithm.Any binary search tree can be made succinct, meaning that it achieves\((1+o(1))\)times the optimal space, with constant-factor time overhead, and can even be made to be within\(O(n)\)bits of optimal if we allow for\(O(\log^{*}n)\)-time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree.Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and\((1+o(1))\)-factor space overhead.Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of\(\log^{(r)}n+O(\log j)\)bits per\(j\)-bit value for an arbitrary constant\(r\gt0\)of our choice.Given an external-memory array\(A\)of size\((1+\varepsilon)n\)containing a dynamic set of up to\(n\)key-value pairs, it is possible to maintain an internal-memory stash of size\(O(n\log\varepsilon^{-1})\)bits so that the location of any key-value pair in\(A\)can be computed in constant time (and with no IOs). In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free. 

   more » « less
4. 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
5. Model theory and agnostic online learning via excellent sets

   https://doi.org/10.1090/tran/9235  

   Malliaris, M; Moran, S (November 2024, Transactions of the American Mathematical Society)

   We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\mathrm{ϵ<\#comment/>}$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi’s celebrated Regularity Lemma). We prove that $\mathrm{ϵ<\#comment/>}$-excellent sets exist for any $\mathrm{ϵ<\#comment/>}>\frac{1}{2}$in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\mathrm{ϵ<\#comment/>}>1/2^{2^k}$or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide. 

   more » « less