We present simple constructions of good approxi-mate locally decodable codes (ALDCs) in the presence of a$\delta{-}$fraction of errors for$\delta < 1/2$. In a standard locally decodable code$C:\Sigma_{1}^{k}\rightarrow\Sigma_{2}^{n}$, there is a decoder$M$that on input$i\in[k]$correctly outputs the i-th symbol of a message$x$(with high probability) using only$q$queries to a given string$w$that is$\Delta$-close to$C(x)$. In an ALDC, the decoder$M$only needs to be correct on a 1$-\varepsilon$fraction of$i\in[k]$for$\varepsilon$much smaller than$\delta$. We present a construction of explicit ALDCs for all constants 1/2$> \delta > \varepsilon$with a constant number of queries$q$and with constant, near-optimal rate. Standard LDCs with constant number of queries and any constant rate are known to be impossible. We additionally explore what is the lowest error probability$\varepsilon$one can achieve for fixed$\delta$and$q$. We show that for any ALDC,$\in=\Omega(\delta \mathrm{r}q/2\rceil)$. We then show that there exist explicit constant rate ALDCs for any constant$q$that achieve$\varepsilon=O(\delta^{\lceil q/2\rceil})$. In particular, for$q=3$, we have a constant rate ALDC with error probability$\varepsilon=O(\delta^{2})$. A full version of this paper is available at https://eccc.weizmann.ac.il/report/2023/056/.

We construct the first asymptotically good relaxed locally correctable codes with polylogarithmic query complexity, bringing the upper bound polynomially close to the lower bound of Gur and Lachish (SICOMP 2021). Our result follows from showing that a high-rate locally testable code can boost the block length of a smaller relaxed locally correctable code, while preserving the correcting radius and incurring only a modest additive cost in rate and query complexity. We use the locally testable code's tester to check if the amount of corruption in the input is low; if so, we can “zoom-in” to a suitable substring of the input and recurse on the smaller code’s local corrector. Hence, iterating this operation with a suitable family of locally testable codes due to Dinur, Evra, Livne, Lubotzky, and Mozes (STOC 2022) yields asymptotically good codes with relaxed local correctability, arbitrarily large block length, and polylogarithmic query complexity.

Large-scale genome rearrangements occur frequently in species evolution and cancer evolution. While the computation of evolutionary distances is tractable for balanced rearrangements, such as inversions and translocations, computing distances involving duplications and deletions is much more difficult. In the recently proposed Copy Number Distance (CND) model, a genome is represented as a Copy Number Profile (CNP), a sequence of integers, and the CND between two CNPs is the length of a shortest sequence of deletions and amplifications of contiguous segments that transforms one CNP into the other. In addition to these segmental events, genomes also undergo global events such as Whole Genome Duplication (WGD) or polyploidization that multiply the entire genome content. These global events are common and important in both species and cancer evolution. In this paper, we formulate the genome halving problem of finding a closest preduplication CNP that has undergone a WGD and evolved into a given CNP under the CND model. We also formulate the analogous genome aliquoting problem of finding the closest prepolyploidzation CNP under the CND distance. We give a linear time algorithm for the halving distance and a quadratic time dynamic programming algorithm for the aliquoting distance. We implement these algorithms and show that they produce reasonable solutions on simulated CNPs.

Since the BRAIN Initiative and Human Brain Project began, a few efforts have been made to address the computational challenges of neuroscience Big Data. The promises of these two projects were to model the complex interaction of brain and behavior and to understand and diagnose brain diseases by collecting and analyzing large quanitites of data. Archiving, analyzing, and sharing the growing neuroimaging datasets posed major challenges. New computational methods and technologies have emerged in the domain of Big Data but have not been fully adapted for use in neuroimaging. In this work, we introduce the current challenges of neuroimaging in a big data context. We review our efforts toward creating a data management system to organize the large-scale fMRI datasets, and present our novel algorithms/methods for the distributed fMRI data processing that employs Hadoop and Spark. Finally, we demonstrate the significant performance gains of our algorithms/methods to perform distributed dictionary learning.

The authors evaluate the use of Apache Flink, a novel data analysis framework offering optimizations over competitors such as Apache Spark, in order to use a rank-1 dictionary learning (r1DL) algorithm to decompose fMRI data. We first expand the functionality of the Flink Python API in order to accommodate the implementation of rank-1 dictionary learning, a model for decomposing a large matrix. Iterative algorithms, aggregators, and other features are added to the incomplete Python API, and the experiences and lessons learned are described. Using these features, we port an existing implementation of r1DL from using the Python API of Apache Spark to using the Python API of Apache Flink. In preliminary testing, this implementation suggests performance boosts over Spark for large input files, meriting further research. We conclude that Flink is likely a feasible tool for the application of dictionary learning to decompose fMRI data, and we continue to evaluate and apply it.