Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “Randomized algorithm”

Successive randomized compression: A randomized algorithm for the compressed MPO-MPS product

Chris Camaño, Ethan N. Epperly, Joel A. Tropp · Quantum · 2026

Tensor networks like matrix product states (MPSs) and matrix product operators (MPOs) are powerful tools for representing exponentially large states and operators, with applications in quantum many-body physics, machine learning, numerical analysis, and other areas. In these applications, computing a compressed representation of the MPO-MPS product is a fundamental computational primitive. For this operation, this paper introduces a new single-pass, randomized algorithm, called successive randomized compression (SRC), that improves on existing approaches in speed or in accuracy. The performance of the new algorithm is evaluated on synthetic problems and unitary time evolution problems for quantum spin systems.

Cited by 0Open access

On the randomized Euler algorithm under inexact information

Marcin Baranek, Andrzej Kałuża, Paweł Morkisz et al. · arXiv (Cornell University) · 2023

This paper focuses on analyzing the error of the randomized Euler algorithm when only noisy information about the coefficients of the underlying stochastic differential equation (SDE) and the driving Wiener process is available. Two classes of disturbed Wiener process are considered, and the dependence of the algorithm's error on the regularity of the disturbing functions is investigated. The paper also presents results from numerical experiments to support the theoretical findings.

Cited by 0Open access

A randomized quantum algorithm for statistical phase estimation

Wan, Kianna, Berta, Mario, Campbell, Earl T. · arXiv (Cornell University) · 2021

Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all sources of error in our algorithm can be suppressed by collecting more data samples, without increasing the circuit depth.

Cited by 1Open access

A Randomized Concurrent Algorithm for Disjoint Set Union

Siddhartha Jayanti, Robert E. Tarjan · 2016

Disjoint set union is a basic problem in data structures with a wide variety of applications. We extend a known efficient sequential algorithm for this problem to obtain a simple and efficient concurrent wait-free algorithm running on an asynchronous parallel random access machine (APRAM). Crucial to our result is the use of randomization. Under a certain independence assumption, for a problem instance in which there are n elements, m operations, and l processes, our algorithm does θ(m (α{n, m/nl) + log (nl/m + 1 ))) expected work, where the expectation is over the random choices made by the algorithm and α is a functional inverse of Ackermann's function. In addition, each operation takes O(log n) steps with high probability.

Cited by 18

A randomized algorithm for gossiping in radio networks

Marek Chrobák, Leszek Gąsieniec, Wojciech Rytter · Networks · 2004

Abstract We present an O ( n log 4 n )‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O ( n 3/2 log 2 n ). © 2004 Wiley Periodicals, Inc.

Cited by 23

A Time-Optimal Randomized Parallel Algorithm for MIS

Mohsen Ghaffari, Bernhard Haeupler · Society for Industrial and Applied Mathematics eBooks · 2021

We present a randomized parallel algorithm, in the Exclusive-Read Exclusive-Write (EREW) PRAM model, that computes a Maximal Independent Set (MIS) in O(log n) time and using O(m log2 n) work, with high probability. Thus, MIS ∊ RNC1. This time complexity is optimal and it improves on the celebrated O(log2 n) time algorithms of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86], which had remained the state of the art for the past 35 years.

Cited by 4Open access

Randomized Average Kaczmarz Algorithm for Tensor Linear Systems

Wendi Bao, Feiyu Zhang, Weiguo Li et al. · Mathematics · 2022

For solving tensor linear systems under the tensor–tensor t-product, we propose the randomized average Kaczmarz (TRAK) algorithm, the randomized average Kaczmarz algorithm with random sampling (TRAKS), and their Fourier version, which can be effectively implemented in a distributed environment. We analyzed the relationships (of the updated formulas) between the original algorithms and their Fourier versions in detail and prove that these new algorithms can converge to the unique least F-norm solution of the consistent tensor linear systems. Extensive numerical experiments show that they significantly outperform the tensor-randomized Kaczmarz (TRK) algorithm in terms of both iteration counts and computing times and have potential in real-world data, such as video data, CT data, etc.

Cited by 11Open access

An Intelligent Question Paper Generator using Randomized Algorithm

Parth Shah, Uzair Faquih, Rutuja Dhanaji Devkar et al. · Zenodo (CERN European Organization for Nuclear Research) · 2022

This is a problematic era because of the boom in the subject of advanced technology and the demand we are dealing with nowadays. Therefore, examinations рlаy а сruсiаl rоle in сheсking оut аn individual's performance, аnd рreраrаtiоn оf exаm questiоn рарers hаs соnsistently been а mаtter оf interest. And this is why it's far critical to have an intelligent system for the growth of students in addition to checking their learning skills, thereby retaining a check on student performance. Faculties generate various question papers in keeping with the university's assessment requirements. It's very challenging for the teachers to make question papers with multiple questions that meet the course's learning targets. We have рrороsed аn аutоmаted рrосess оf question рарer generation thаt is fast, streamlined, randomized, and secure. Every action executed task by the system is automated, so that storage space, bias, and security are not a challenge anymore. It automatically creates a variety of sets of questions now and then without worrying about replication and duplication from the initial exam at the same time as the question bank keeps growing.

Cited by 0Open access

Randomized tree construction algorithm to explore energy landscapes

Léonard Jaillet, Francesc J. Corcho, Juan J. Pérez et al. · Journal of Computational Chemistry · 2011

In this work, a new method for exploring conformational energy landscapes is described. The method, called transition-rapidly exploring random tree (T-RRT), combines ideas from statistical physics and robot path planning algorithms. A search tree is constructed on the conformational space starting from a given state. The tree expansion is driven by a double strategy: on the one hand, it is naturally biased toward yet unexplored regions of the space; on the other, a Monte Carlo-like transition test guides the expansion toward energetically favorable regions. The balance between these two strategies is automatically achieved due to a self-tuning mechanism. The method is able to efficiently find both energy minima and transition paths between them. As a proof of concept, the method is applied to two academic benchmarks and the alanine dipeptide.

Cited by 54Open access

Randomized shellsort: A simple data-oblivious sorting algorithm

Michael T. Goodrich · 2016

In this paper, we describe a randomized Shellsort algorithm. This algorithm is a simple, random-ized, data-oblivious version of the Shellsort algorithm that always runs in O(n logn) time and succeeds in sorting any given input permutation with very high probability. Taken together, these properties imply applications in the design of new efficient privacy-preserving computations based on the secure multi-party computation (SMC) paradigm. In addition, by a trivial conversion of this Monte Carlo algorithm to its Las Vegas equivalent, one gets the first version of Shellsort with a running time that is provably O(n logn) with very high probability. 1

Cited by 0

Massive Text Normalization via an Efficient Randomized Algorithm

Nan Jiang, Luo Chen, Vihan Lakshman et al. · Proceedings of the ACM Web Conference 2022 · 2022

Current popular machine learning techniques in natural language processing and data mining rely heavily on high-quality text sources. Nevertheless, real-world text datasets contain a significant amount of spelling errors and improperly punctuated variants where the performance of these models would quickly deteriorate. Moreover, existing text normalization methods are prohibitively expensive to execute over web-scale datasets, can hardly process noisy texts from social networks, or require annotations to learn the corrections in a supervised manner. In this paper, we present Flan (Fast LSH Algorithm for Text Normalization), a scalable randomized algorithm to clean and canonicalize massive text data. Our approach suggests corrections based on the morphology of the words, where lexically similar words are considered the same with high probability. We efficiently handle the pairwise word-to-word comparisons via locality sensitive hashing (LSH). We also propose a novel stabilization process to address the issue of hash collisions between dissimilar words, which is a consequence of the randomized nature of LSH and is exacerbated by the massive scale of real-world datasets. Compared with existing approaches, our method is more efficient, both asymptotically and in empirical evaluations, does not rely on feature engineering, and does not require any annotation. Our experimental results on real-world datasets demonstrate the efficiency and efficacy of Flan. Based on recent advances in densified Minhash, our approach requires much less computational time compared to baseline text normalization techniques on large-scale Twitter and Reddit datasets. In a human evaluation of the quality of the normalization, Flan achieves 5% and 14% improvement against the baselines over the Reddit and Twitter datasets, respectively. Our method also improves performance on Twitter sentiment classification applications and the perturbed GLUE benchmark datasets, where we introduce random errors into the text.

Cited by 5

An Optimal Randomized Algorithm for Finding the Saddlepoint

Justin Dallant, Frederik Haagensen, Riko Jacob et al. · arXiv (Cornell University) · 2024

A \emph{saddlepoint} of an $n \times n$ matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task. For finding a \emph{strict saddlepoint} (an entry that is the strict maximum of its row and the strict minimum of its column) we recently gave an $O({n\log^*{n}})$-time algorithm, improving the $O({n\log{n}})$ bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein. In this paper we present an optimal $O({n})$-time algorithm for finding a strict saddlepoint based on random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to randomized algorithms, showing that the trivial $O(n^2)$ runtime cannot be improved even with the use of randomness.

Cited by 1Open access

RMBC: Randomized mesh blockchain using DBFT consensus algorithm

Sol Jeon, Inshil Doh, Kijoon Chae · 2018

The blockchain is decentralized network system that verifies the validity of the transaction through the consensus of the verifiers without trusted third parties. This mechanism ensures transaction integrity disclosing transaction information transparently. Therefore, it is emerging as the core technology of the 4th industrial revolution by improving reliability and efficiency with features of decentralization, ensuring the integrity, and economic cost reduction. However, there are some problems with the growth of the blockchain. The popularly used PoW (Proof of Work) consensus algorithm applied to the public blockchain requires the price to be compensated in order to agree on the validity of the transaction. This has the disadvantage that the system doesn't operate without compensation. Also, the BFT (Byzantine Fault Tolerance) Algorithm using private blockchain has a limited number of acceptable malicious users. In this case, if the users collude with malicious and exceed the limited number, the transaction is rejected. In this paper, we propose a Smart Manager System and RMBC-DBFT (Randomized Mesh Blockchain Diversity of opinion BFT) enables the safe transaction to the problems above.

Cited by 19