Skip to main content
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [inherently-sequential]

Inherently sequential is In opposition to embarrassingly parallel tasks, the execution of some tasks depends heavily on the results of others. In other words, those tasks are not independent, and thus, cannot be made parallel or concurrent. Furthermore, if we were to try to implement concurrency into those programs, it could cost us more execution time to produce the same results.

Filter by
Sorted by
Tagged with
1 vote
1 answer

A doubt on Proofs-of-Sequential-Work protocols

Proofs-of-Sequential-Work ($\mathsf{PoSW}$) are cryptographic protocols that engage two parties, a prover with $\mathtt{poly}(N)$-parallel processors and a deterministic verifier such that the ...
Somudro Gupto's user avatar
1 vote
0 answers

How quickly can we compute SHA256?

Disclaimer. I have asked a similar question on Electronics StackExchange: they advised me to try here. The question I am in the process of developing a simple protocol whose security relies on the ...
Matteo Monti's user avatar
  • 1,407
6 votes
1 answer

Is XOR-and-SUM inherently sequential?

I have been thinking recently about inherently sequential functions. In trying to wrap my head around them, I tried to come to the simplest possible function that looks inherently sequential to me. ...
Matteo Monti's user avatar
  • 1,407
20 votes
2 answers

Can Grover's algorithm be parallelized?

Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$ on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit ...
CodesInChaos's user avatar
  • 24.9k
7 votes
1 answer

Are there secure stream ciphers that cannot be parallelized?

Are there any stream ciphers (or a deterministic random number generators, that should work as well I guess?) that cannot be parallelized? For example, if I seed it with a specific value, and then &...
Cray's user avatar
  • 173