Search

The paper proposes to decode Reed-Muller (RM) codes by projecting onto only a few subspaces such that the number of projections is significantly reduced. It reveals that the probability that error pairs are canceled simultaneously in two different projections is determined by their intersection size. Then, correlation coefficient which indicates the intersection size of two subspaces in a collection is introduced for collecting subspaces. Simulation results show that our proposed approach with a small number of projections onto collected subspaces performs close to the original approach.

We present parameterized streaming algorithms for the graph matching problem in both the dynamic and the insert-only models. For the dynamic streaming model, we present a one-pass algorithm that, with high probability, computes a maximum-weight $k$-matching of a weighted graph in $\tilde{O}(Wk^2)$ space and that has $\tilde{O}(1)$ update time, where $W$ is the number of distinct edge weights and the notation $\tilde{O}()$ hides a poly-logarithmic factor in the input size. For the insert-only streaming model, we present a one-pass algorithm that runs in $O(k^2)$ space and has $O(1)$ update time, and that, with high probability, computes a maximum-weight $k$-matching of a weighted graph. The space complexity and the update-time complexity achieved by our algorithms for unweighted $k$-matching in the dynamic model and for weighted $k$-matching in the insert-only model are optimal. A notable contribution of this paper is that the presented algorithms {\it do not} rely on the apriori knowledge/promise that the cardinality of \emph{every} maximum-weight matching of the input graph is upper bounded by the parameter $k$. This promise has been a critical condition in previous works, and lifting it required the development of new tools and techniques.

We study fundamental point-line covering problems in computational geometry, in which the input is a set $S$ of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least $\lambda$ points from $S$, for a given integer parameter $\lambda \geq 2$; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which -- the latter -- asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of $k$ lines that cover the points of $S$, for a given parameter $k \in \mathbb{N}$. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.'s algorithm [Computational Geometry 1996], for a wide range of the parameter $\lambda$. We derive lower-bound results showing that, for $\lambda =\Omega(\sqrt{n \log n})$, the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model. For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.

We study the evolution of a qubit evolving according to the Schr\"odinger equation with a Hamiltonian containing noise terms, modeled by random diagonal and off-diagonal matrix elements. We show that the noise-averaged qubit density matrix converges to a final state, in the limit of large times $t.$ The convergence speed is polynomial in $1/t$, with a power depending on the regularity of the noise probability density and its low frequency behaviour. We evaluate the final state explicitly. We show that in the regimes of weak and strong off-diagonal noise, the process implements the dephasing channel in the energy- (localized) and the delocalized basis, respectively.

Detection of Barrett's esophagus (BE) at points of care outside the endoscopy suite may improve screening access and reduce esophageal adenocarcinoma mortality. Tethered capsule optical coherence tomography (OCT) can volumetrically image esophageal mucosa and detect BE in unsedated patients. We investigated ultrahigh-speed tethered capsule, swept-source OCT (SS-OCT) in unsedated patients, improved device design, developed procedural techniques, measured how capsule contact and longitudinal pullback non-uniformity affect coverage, and assessed patient toleration. OCT was performed in 16 patients prior to endoscopic surveillance/treatment. Unsedated patients swallowed the capsule with small sips of water and the esophagus imaged by retracting the tether. Ultrahigh-speed SS-OCT at 1,000,000 A-scans/second imaged ~40cm$^2$ esophageal areas in 10 seconds with 30um transverse and 8um axial resolution. Nine patients had non-dysplastic BE, 3 had ablative treatment-naive neoplasia, and 4 had prior ablation for history of dysplasia. The capsule procedure was well tolerated. Ultrahigh-speed SS-OCT enabled the generation of cross-sectional and sub-surface en face images. BE could be rapidly identified in cross-sectional and en face images, while assessment of the gastro-esophageal junction (GEJ) required subsurface en face views. Capsule esophageal contact was worse in long-segment BE and sliding hiatal hernia, and longitudinal image coverage was worse in short-segment BE. OCT candidate features of dysplasia are reported. Ultrahigh-speed tethered capsule SS-OCT enabled en face and cross-sectional imaging of mucosal features over wide areas. Device and procedure optimization led to improved imaging performance. Areas of BE could be readily identified, but limited capsule contact and longitudinal image coverage can yield sampling errors.

We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).

With the development of blockchain, the huge history data limits the scalability of the blockchain. This paper proposes to downsample these data to reduce the storage overhead of nodes. These nodes keep good independency, if downsampling follows the entropy of blockchain. Moreover, it demonstrates that the entire blockchain history can be efficiently recovered through the cooperative decoding of a group of nodes like fountain codes, if reserved data over these nodes obey the soliton distribution. However, these data on nodes are uncoded (transparent). Thus, the proposed algorithm not only keeps decentralization and security, but also has good scalability in independency and recovery., Comment: 8pages, 6 figures