Fast Arrays support initialization of the entire array in just constant time, in addition to supporting constant-time reading and writing of individual elements. Jayanti and Shun introduced concurrent fast arrays, including a generalized fast array which supports constant-time read-modify-write (RMW) operations in addition to reads and writes. Their generalized algorithm, however, assumes mixed-size atomicity—i.e., that 128-bit compare-and-swap and 64-bit read-modify-write operations can be performed concurrently on the same location—which is not available in most programming languages (e.g., C++ and Rust) and not guaranteed on most architectures (e.g., x86 and ARM), as opposed to fixed-size atomicity.

Modern servers are equipped with many tiers of random access memory (RAM), where faster tiers offer greater speed of memory accesses while slower tiers offer greater capacity. In this paper, we model such tiered memory systems and ask the fundamental question of how to simultaneously exploit the computation speed of the fast tiers and the capacity of the slow tiers.

LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving ε-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality d, that is, when d < (1/ε)^0.999. Our main result is an O(ds) pass algorithm with O(s(√d/ε)^{3d/s}) ⋅ poly(d, log (1/ε)) space complexity in words, for any parameter s ∈ [1, d log (1/ε)], to solve ε-approximate LP-type problems of O(d) combinatorial and VC dimension. Notably, by taking s = d log (1/ε), we achieve space complexity polynomial in d and polylogarithmic in 1/ε, presenting exponential improvements in 1/ε over current algorithms. We complement our results by showing lower bounds of (1/ε)^Ω(d) for any 1-pass algorithm solving the (1 + ε)-approximation MEB and linear SVM problems, further motivating our multi-pass approach.