Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
From MaRDI portal
Recommendations
Cites work
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A survey of lower bounds for satisfiability and related problems.
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Computational Complexity
- Concentration of Measure for the Analysis of Randomized Algorithms
- Determinism versus nondeterminism for linear time RAMs with memory restrictions
- Generalized String Matching
- scientific article; zbMATH DE number 5899238 (Why is no real title available?)
- Introduction to algorithms.
- Limits on alternation trading proofs for time-space lower bounds
- Linear Time Algorithms and NP-Complete Problems
- Lower bounds on the complexity of recognizing SAT by Turing machines
- Nonuniform ACC circuit lower bounds
- On Ajtai's lower bound technique for R-way branching programs and the Hamming distance problem
- Oracle branching programs and Logspace versus \(P^*\)
- Relativization of questions about log space computability
- The computational complexity of universal hashing
- Time-space lower bounds for satisfiability
- Time-space trade-off lower bounds for randomized computation of decision problems
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- Time-space tradeoffs for algebraic problems on general sequential machines
- Time-space tradeoffs for branching programs
- Time-space tradeoffs for counting NP solutions modulo integers
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
Cited in
(4)- scientific article; zbMATH DE number 5528957 (Why is no real title available?)
- Algebraic algorithms for variants of subset sum
- Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
- Time-space lower bounds for simulating proof systems with quantum and randomized verifiers
This page was built for publication: Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090435)
