Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
From MaRDI portal
Cites work
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Element distinctness, frequency moments, and sliding windows
- Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
- scientific article; zbMATH DE number 1033441 (Why is no real title available?)
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Nonadaptive quantum query complexity
- Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum time-space tradeoff for finding multiple collision pairs
- Quantum time-space tradeoffs for sorting
- Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
- Tight time-space lower bounds for finding multiple collision pairs and their applications
- Time-space tradeoffs for algebraic problems on general sequential machines
- Time-space tradeoffs for element distinctness and set intersection via pseudorandomness
- Truly low-space element distinctness and subset sum via pseudorandom hash functions
- Typically-correct derandomization for small time and space
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
This page was built for publication: Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906327)
