Lower Bounds and Algorithms in the Linear Decision Tree Model

Build

• Print cover
• Main file
• Presentation slides

Keywords

Problems in the Linear Decision Tree Model

• Sorting, Merging
• Sorting under Partial Information, Merging under Partial Information
• Sorting X + Y
• 3SUM, k-SUM, k-LDT, subset sum
• Point Location in an Arrangement of Hyperplanes

Lower bounds

• Information-theoretic lower bound
• Lower bounds for linear satisfiability problems (Erickson)
• Lower bounds for linear degeneracy testing (Ailon, Chazelle)

Algorithms and upper bounds

• Quicksort
• Mergesort
• Heapsort
• Ford-Johnson algorithm
• Tape merge
• Hwang-Lin algorithm
• Linial's algorithm
• Fredman's algorithm
• Buck's theorem
• Meiser's algorithm

Contents

• Sorting, Merging and Sorting under Partial Information (Cardinal et al. [1])
• Linial's algorithm (Linial [4] + efficient implementation)
• Sorting X+Y (naive approach + Fredman [2])
• 3SUM, k-SUM, k-LDT (Grønlund and Pettie [3])
• Application of Meiser's Algorithm (Meiser [5])
• Solve k-SUM using only o(n)-linear queries

Main References

1. Cardinal, J., Fiorini, S., Joret, G., Jungers, R. M., and Munro, J. I. (2013). Sorting under partial information (without the ellipsoid algorithm). Combinatorica, 33(6):655–697.
2. Fredman, M. L. (1976). How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355–361.
3. Grønlund, A. and Pettie, S. (2014). Threesomes, degenerates, and love triangles. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 621–630. IEEE.
4. Linial, N. (1984). The information-theoretic bound is good for merging. SIAM Journal on Computing, 13(4):795–801.
5. Meiser, S. (1993). Point location in arrangements of hyperplanes. Information and Computation, 106(2):286–303.