Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Random Variables01:09

Random Variables

13.4K
A random variable is a single numerical value that indicates the outcome of a procedure. The concept of random variables is fundamental to the probability theory and was introduced by a Russian mathematician, Pafnuty Chebyshev, in the mid-nineteenth century.
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
13.4K
Wald-Wolfowitz Runs Test I01:17

Wald-Wolfowitz Runs Test I

744
The Wald-Wolfowitz test, also known as the runs test, is a nonparametric statistical test used to assess the randomness of a sequence of two different types of elements (e.g., positive/negative values, successes/failures). It examines whether the order of the elements in a sequence is random or if there is a pattern or trend present. This nonparametric test applies to any ordered data despite the population and sample data distribution, even if a higher sample size is available.
The test works...
744
Propagation of Uncertainty from Random Error00:59

Propagation of Uncertainty from Random Error

1.1K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.1K
Wald-Wolfowitz Runs Test II01:17

Wald-Wolfowitz Runs Test II

318
The Wald-Wolfowitz runs test, commonly referred to as the runs test, is a nonparametric test used to assess the randomness of ordered data. The test evaluates the number of runs, which are consecutive sequences of similar elements within the data. If the number of runs is significantly higher or lower than expected, the data is considered non-random, indicating a detectable pattern or structure.
For binary data, runs are identified using symbols such as + and −, or equivalently, 1s and...
318
Stream Function01:20

Stream Function

1.6K
In two-dimensional incompressible fluid flow, the continuity equation is essential for ensuring mass conservation, meaning that any change in fluid entering or exiting a region is balanced by a corresponding change elsewhere. For incompressible flow, where density remains constant, this requirement simplifies to the condition that the divergence of the velocity field must be zero. Mathematically, this is expressed as,
1.6K
Poisson Probability Distribution01:09

Poisson Probability Distribution

8.5K
A Poisson probability distribution is a discrete probability distribution. It gives the probability of a number of events occurring in a fixed interval of time or space if these events happen at a known average rate and independently of the time since the last event. For example, a book editor might be interested in the number of words spelled incorrectly in a particular book. It might be that, on average, there are five words spelled incorrectly in 100 pages. The interval is 100 pages.
The...
8.5K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms.

... International Conference on Learning Representations·2026
Same author

Safe to Speak, Teach, and Research? Experiences of Reprisals in Danish Academia.

The British journal of sociology·2026
Same author

Learning-augmented sketching offers improved performance for privacy preserving and secure GWAS.

iScience·2025
Same author

<math> </math> -Regression in the Arbitrary Partition Model of Communication.

Proceedings of machine learning research·2024
Same author

Improved Algorithms for White-Box Adversarial Streams.

Proceedings of machine learning research·2024
Same author

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut.

Proceedings of the ACM on management of data·2024

Related Experiment Video

Updated: Sep 13, 2025

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

661

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming.

Praneeth Kacham1, Rasmus Pagh2, Mikkel Thorup2

  • 1CMU.

Proceedings ... Annual Symposium on Foundations of Computer Science. Symposium on Foundations of Computer Science
|July 31, 2025
PubMed
Summary

This study introduces HashPRG, a new pseudorandom generator that improves space-bounded computation and streaming algorithms. HashPRG enables significant reductions in update time for data stream algorithms without increasing space complexity.

More Related Videos

Quasi-light Storage for Optical Data Packets
07:45

Quasi-light Storage for Optical Data Packets

Published on: February 6, 2014

11.0K
A Protocol for Real-time 3D Single Particle Tracking
10:16

A Protocol for Real-time 3D Single Particle Tracking

Published on: January 3, 2018

15.0K

Related Experiment Videos

Last Updated: Sep 13, 2025

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

661
Quasi-light Storage for Optical Data Packets
07:45

Quasi-light Storage for Optical Data Packets

Published on: February 6, 2014

11.0K
A Protocol for Real-time 3D Single Particle Tracking
10:16

A Protocol for Real-time 3D Single Particle Tracking

Published on: January 3, 2018

15.0K

Area of Science:

  • Theoretical Computer Science
  • Algorithms and Data Structures
  • Computational Complexity

Background:

  • Nisan's pseudorandom generator (PRG) is a foundational tool for space-bounded computation and streaming algorithms.
  • Existing derandomization techniques often involve trade-offs between space, time, and reliance on random oracles.
  • Optimizing update times in data stream algorithms while maintaining space efficiency is a key challenge.

Purpose of the Study:

  • To introduce HashPRG, a novel symmetric pseudorandom generator offering a time-space trade-off.
  • To apply HashPRG for derandomizing space-bounded streaming algorithms, improving update times without sacrificing space.
  • To enhance the efficiency of algorithms for F_p estimation, l_p sampling, and CountSketch in data streams.

Main Methods:

  • Development of HashPRG, a symmetric pseudorandom generator with adjustable seed length and computation time.
  • Application of HashPRG to derandomize Andoni's F_p estimation algorithm, removing the random oracle assumption.
  • Utilizing HashPRG's time-space trade-off for improved F_p estimation (0 < p < 2) and entropy estimation algorithms.
  • Derandomization of a private version of CountSketch and algorithms for estimating the L_infinity norm of vectors in turnstile streams.

Main Results:

  • HashPRG enables derandomizations with significantly better update times and no increase in space complexity for various streaming algorithms.
  • Achieved constant update time for F_p estimation (p > 2) without random oracles, preserving optimal space.
  • For 0 < p < 2, achieved a quadratic improvement in update time (O(log d)) for F_p estimation using optimal space.
  • Provided the first derandomization of a private CountSketch and efficient algorithms for L_infinity norm estimation with optimal space and improved update times.

Conclusions:

  • HashPRG is a powerful tool for improving the efficiency of space-bounded streaming algorithms.
  • The new generator facilitates time-optimal derandomizations, breaking previous limitations and enhancing practical applicability.
  • This work offers significant advancements in the theoretical and practical aspects of data stream processing and analysis.