Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
From MaRDI portal
Publication:5090435
DOI10.4230/LIPIcs.ITCS.2019.56OpenAlexW2912512664MaRDI QIDQ5090435
Dylan M. McKay, R. Ryan Williams
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.56
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limits on alternation trading proofs for time-space lower bounds
- 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 for algebraic problems on general sequential machines
- Oracle branching programs and Logspace versus \(P^*\)
- The computational complexity of universal hashing
- Lower bounds on the complexity of recognizing SAT by Turing machines
- Time-space tradeoffs for branching programs
- Determinism versus nondeterminism for linear time RAMs with memory restrictions
- Nonuniform ACC Circuit Lower Bounds
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Time-space lower bounds for satisfiability
- Time-space trade-off lower bounds for randomized computation of decision problems
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- A Survey of Lower Bounds for Satisfiability and Related Problems
- Generalized String Matching
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Relativization of questions about log space computability
- Linear Time Algorithms and NP-Complete Problems
- Computational Complexity
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
