Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

DOI10.4230/LIPICS.ITCS.2019.56MaRDI QIDQ5090435zbMATH OpenOpenAlexFDO

Authors Dylan M. McKay, Ryan Williams

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.ITCS.2019.56

zbMATH Keywords

lower boundsSATcounting complexityrandom oraclesbranching programstime-space tradeoffs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Time-space trade-off lower bounds for randomized computation of decision problems
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Time-space tradeoffs for branching programs
• Time-space lower bounds for satisfiability
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A survey of lower bounds for satisfiability and related problems.
• Computational Complexity
• Concentration of Measure for the Analysis of Randomized Algorithms
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Generalized String Matching
• 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

(2)

• scientific article; zbMATH DE number 5528957 (Why is no real title available?)
• Algebraic algorithms for variants of subset sum

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)