More Like this

1. On the Optimal Time/Space Tradeoff for Hash Tables

   Bender, Michael ; Farach-Colton, Martin ; Kuszmaul, John ; Kuszmaul, William ; Liu, Mingmou ( January 2022 , STOC)

   For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the information-theoretic optimum. Even prior to this bound being achieved, the target of O(log log n) wasted bits per key was known to be a natural end goal, and was proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters). This paper shows that O(log log n) wasted bits per key is not the end of the line for hashing. In fact, for any k ∈ [log∗ n], it is possible to achieve O(k)-time insertions/deletions, O(1)-time queries, and O(log(k) n) = Ologlog···logn 􏰟 􏰞􏰝 􏰠 k wasted bits per key (all with high probability in n). This means that, each time we increase inser- tion/deletion time by an additive constant, we reduce the wasted bits per key exponentially. We further show that this tradeoff curve is the best achievable by any of a large class of hash tables, including any hash table designed using the current framework for making constant-time hash tables succinct. Our results hold not just for fixed-capacity hash tables, but also for hash tables that are dynamically resized (this is a fundamental departure from what is possible for filters); and for hash tables that store very large keys/values, each of which can be up to no(1) bits (this breaks with the conventional wisdom that larger keys/values should lead to more wasted bits per key). For very small keys/values, we are able to tighten our bounds to o(1) wasted bits per key, even when k = O(1). Building on this, we obtain a constant-time dynamic filter that uses n􏰕logε−1􏰖+nloge+o(n) bits of space for a wide choice of 

   more » « less
2. Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

   https://doi.org/10.1007/s00220-021-04093-z  

   Blanca, Antonio ; Gheissari, Reza ( April 2021 , Communications in Mathematical Physics)

   We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs for all$$q\ge 1$$$q\ge 1$and$$p$p<p_u(q,\Delta )$, where the threshold$$p_u(q,\varDelta )$$$p_u(q,\Delta )$corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$$\Delta$-regular tree. It is expected that this threshold is sharp, and for$$q>2$$$q>2$the Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$$p_u(q,\Delta )$. More precisely, we show that for every$$q\ge 1$$$q\ge 1$,$$\varDelta \ge 3$$$\Delta \ge 3$, and$$p$p<p_u(q,\Delta )$, with probability$$1-o(1)$$$1-o\left(1\right)$over the choice of a random$$\varDelta $$$\Delta$-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$$\Theta (nlogn)$mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$$\Delta$-regular graphs for every$$q\ge 2$$$q\ge 2$, in the tree uniqueness region. Our proof relies on a sharp bound on the “shattering time”, i.e., the number of steps required to break up any configuration into$$O(\log n)$$$O(logn)$sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

    

   more » « less
3. Average-case analysis of the Gaussian elimination with partial pivoting

   https://doi.org/10.1007/s00440-024-01276-2  

   Huang, Han ; Tikhomirov, Konstantin ( April 2024 , Probability Theory and Related Fields)

   The Gaussian elimination with partial pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Although in specific cases the loss of precision in GEPP due to roundoff errors can be very significant, empirical evidence strongly suggests that for atypicalsquare coefficient matrix, GEPP is numerically stable. We obtain a (partial) theoretical justification of this phenomenon by showing that, given the random$$n\times n$$$n\times n$standard Gaussian coefficient matrixA, thegrowth factorof the Gaussian elimination with partial pivoting is at most polynomially large innwith probability close to one. This implies that with probability close to one the number of bits of precision sufficient to solve$$Ax = b$$$Ax=b$tombits of accuracy using GEPP is$$m+O(\log n)$$$m+O(logn)$, which improves an earlier estimate$$m+O(\log ^2 n)$$$m+O\left({log}^{2}n\right)$of Sankar, and which we conjecture to be optimal by the order of magnitude. We further provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than the Gaussian Elimination with no pivoting.

    

   more » « less
4. Efficient Computation of Sequence Mappability

   https://doi.org/10.1007/s00453-022-00934-y  

   Charalampopoulos, Panagiotis ; Iliopoulos, Costas S. ; Kociumaka, Tomasz ; Pissis, Solon P. ; Radoszewski, Jakub ; Straszyński, Juliusz ( February 2022 , Algorithmica)

   Sequence mappability is an important task in genome resequencing. In the (k, m)-mappability problem, for a given sequenceTof lengthn, the goal is to compute a table whoseith entry is the number of indices$$j \ne i$$$j\ne i$such that the length-msubstrings ofTstarting at positionsiandjhave at mostkmismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of$$k=1$$$k=1$. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=O(1)$$$k=O\left(1\right)$, works in$$O(n)$$$O\left(n\right)$space and, with high probability, in$$O(n \cdot \min \{m^k,\log ^k n\})$$$O(n·min\{m^k,{log}^{k}n\})$time. Our algorithm requires a careful adaptation of thek-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop$$O(n^2)$$$O\left(n^2\right)$-time algorithms to computeall(k, m)-mappability tables for a fixedmand all$$k\in \{0,\ldots ,m\}$$$k\in \{0,\dots ,m\}$or a fixedkand all$$m\in \{k,\ldots ,n\}$$$m\in \{k,\dots ,n\}$. Finally, we show that, for$$k,m = \Theta (\log n)$$$k,m=\Theta (logn)$, the (k, m)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018.

    

   more » « less
5. Identification of all-against-all protein–protein interactions based on deep hash learning

   https://doi.org/10.1186/s12859-022-04811-x  

   Jiang, Yue ; Wang, Yuxuan ; Shen, Lin ; Adjeroh, Donald A. ; Liu, Zhidong ; Lin, Jie ( July 2022 , BMC Bioinformatics)

   Protein–protein interaction (PPI) is vital for life processes, disease treatment, and drug discovery. The computational prediction of PPI is relatively inexpensive and efficient when compared to traditional wet-lab experiments. Given a new protein, one may wish to find whether the protein has any PPI relationship with other existing proteins. Current computational PPI prediction methods usually compare the new protein to existing proteins one by one in a pairwise manner. This is time consuming.

   In this work, we propose a more efficient model, called deep hash learning protein-and-protein interaction (DHL-PPI), to predict all-against-all PPI relationships in a database of proteins. First, DHL-PPI encodes a protein sequence into a binary hash code based on deep features extracted from the protein sequences using deep learning techniques. This encoding scheme enables us to turn the PPI discrimination problem into a much simpler searching problem. The binary hash code for a protein sequence can be regarded as a number. Thus, in the pre-screening stage of DHL-PPI, the string matching problem of comparing a protein sequence against a database withMproteins can be transformed into a much more simpler problem: to find a number inside a sorted array of lengthM. This pre-screening process narrows down the search to a much smaller set of candidate proteins for further confirmation. As a final step, DHL-PPI uses the Hamming distance to verify the final PPI relationship.

   The experimental results confirmed that DHL-PPI is feasible and effective. Using a dataset with strictly negative PPI examples of four species, DHL-PPI is shown to be superior or competitive when compared to the other state-of-the-art methods in terms of precision, recall or F1 score. Furthermore, in the prediction stage, the proposed DHL-PPI reduced the time complexity from$$O(M^2)$$$O\left(M^2\right)$to$$O(M\log M)$$$O(MlogM)$for performing an all-against-all PPI prediction for a database withMproteins. With the proposed approach, a protein database can be preprocessed and stored for later search using the proposed encoding scheme. This can provide a more efficient way to cope with the rapidly increasing volume of protein datasets.

    

   more » « less