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

DOI10.4086/CJTCS.2005.001zbMATH Open1119.68085OpenAlexW4246677237MaRDI QIDQ3594440FDOQ3594440

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

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

Mathematics Subject Classification ID

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

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