On Ajtai's lower bound technique for R-way branching programs and the Hamming distance problem

DOI10.4086/CJTCS.2005.001MaRDI QIDQ3594440zbMATH OpenOpenAlexFDO

Authors Jakob Illeborg Pagter

Publication date 8 August 2007

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://cjtcs.cs.uchicago.edu/articles/2005/1/contents.html

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time-space tradeoffs for branching programs
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space trade-offs for branching programs
• Time-space tradeoffs for set operations
• Near-Optimal Time-Space Tradeoff for Element Distinctness

Cited in

(5)

• Time-space tradeoffs for branching programs
• The Mersenne Low Hamming Combination Search problem can be reduced to an ILP problem
• scientific article; zbMATH DE number 981682 (Why is no real title available?)
• Time-space trade-off lower bounds for randomized computation of decision problems
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

This page was built for publication: On Ajtai's lower bound technique for \(R\)-way branching programs and the Hamming distance problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3594440)