Lower Bounds and Algorithms in the Linear Decision Tree Model

Build

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

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.
Fredman, M. L. (1976). How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355–361.
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.
Linial, N. (1984). The information-theoretic bound is good for merging. SIAM Journal on Computing, 13(4):795–801.
Meiser, S. (1993). Point location in arrangements of hyperplanes. Information and Computation, 106(2):286–303.