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

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

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)

• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Time-space trade-off lower bounds for randomized computation of decision problems
• 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 tradeoffs for branching programs

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)