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

DOI10.4230/LIPICS.ITCS.2019.56OpenAlexW2912512664MaRDI QIDQ5090435FDOQ5090435

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

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

zbMATH Keywords

lower boundsSATcounting complexityrandom oraclesbranching programstime-space tradeoffs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Introduction to algorithms.
• Computational Complexity
• Relativization of questions about log space computability
• Concentration of Measure for the Analysis of Randomized Algorithms
• The computational complexity of universal hashing
• Generalized String Matching
• Time-space tradeoffs for branching programs
• Time-space lower bounds for satisfiability
• A survey of lower bounds for satisfiability and related problems.
• Title not available (Why is that?)
• Limits on alternation trading proofs for time-space lower bounds
• Time-space tradeoffs for counting NP solutions modulo integers
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• 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
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Linear Time Algorithms and NP-Complete Problems
• Nonuniform ACC circuit lower bounds
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• Oracle branching programs and Logspace versus \(P^*\)
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Time-space tradeoffs for algebraic problems on general sequential machines
• Lower bounds on the complexity of recognizing SAT by Turing machines
• On Ajtai's lower bound technique for \(R\)-way branching programs and the Hamming distance problem

Cited In (2)

• Title not available (Why is that?)
• 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)