CS860 Advanced Topics in Theoretical Computer Science

Topic: Five Open Problems in Algorithm Design and Analysis

Instructor: Alex Lopez-Ortiz

The format of the course will be a series of introductory lectures on each of the topics by the instructor or the students, followed by working sessions on particular cases of the questions that could potentially be solved. There will be one lecture a week, 2 to 3 hours long with a short break in between. Students must attend all lectures, give a presentation, write a survey on a chosen problem and make partial progress towards the solution of one of the problems.

Prerequisites: A solid undergraduate knowledge of algorithm analysis and data structures is required. An "algorithms course" like CS 466/666 is a must.

Organization: The first two classes will be lectures given by the instructor. Later classes will be seminars presented by one or more members of the class. Credit for the course will be based on the two presentations, a survey and the course project. The project will involve reading several recent papers in a topic, presenting an overview of the paper(s) to class, making partial progress towards the solution of one of the problems, and reporting on this work both in class and in a written report. These projects may involve implementations or not, depending on the interests of the individual student(s).

References: There is no formal text, most of the material covered will come from the recent literature in the field of algorithms and data structures.

Class time: Organization meeting on Thursday, May 4, at 3:00pm in DC3313. The schedule is Thursdays from 3:00 to 6:00 in DC3313.

Splay Trees and the Dynamic Optimality Conjecture

Intro to Splay Trees reference::
Michael T. Goodrich and Roberto Tamassia, Algorithm Design, Wiley, pages 185-194.

Availability:
On reserve in the library.

Competitive Analysis of Splay Trees:
D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, Volume 32, Issue 3 (July 1985), pp: 652-686.

Availability:
Free access from within campus using URL above.

Reference:
Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu, Dynamic Optimality--Almost, SIAM Journal on Computing, to appear. Special issue of selected papers from the 45th Annual IEEE Symposium on Foundations of Computer Science.

Abstract:
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan's dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.

Brendan Lucier's project on Splay Trees:
Brendal Lucier, Applying the Interleave Bound to Splay Trees Project report, CS840, University of Waterloo, 2005.

Static unknown frequency.
D. Sleator and M. Talapur, Optimal Binary Trees in on-line algorithms. Technical Report CMU-CS-02-148, School of Computer Science, Carnegie Mellon University, September 2002.

Intro to Splay Trees reference::
Michael T. Goodrich and Roberto Tamassia, Algorithm Design, Wiley, pages 185-194.

Availability:
On reserve in the library.

3SUM

n^2 hardness

Anka Gajentaan, and Mark H. Overmars. On a class of O(n^2) problems in computational geometry. Computational Geometry: Theory and Applications, Volume 5, Issue 3 (October 1995), pp:165-185.

Availability:
Free access from within campus using URL above.

Subquadratic algorithms

Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic Algorithms for 3SUM. In proceedings of Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005. Eds. F. Dehne, A. López-Ortiz, J-R. Sack.

Abstract:
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of O(n2 / max {w/lg2 w, lg2 n / (lg lg n)2}). In the circuit RAM with one nonstandard AC0 operation, we obtain O(n2 (lg2 w) / w2). In external memory, we achieve O(n2 / (M B)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of O(n2 (lg2 M) / (M B)). In all cases, our speedup is almost quadratic in the parallelism the model can afford, which may be the best possible. Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability.

3SUM perhaps not that hard

Stephen A. Bloch, Jonathan F. Buss, and Judy Goldsmith. How hard are n^2-hard problems? ACM SIGACT News, Volume 25, Issue 2 (June 1994).

Availability:
Free access from within campus using URL above.

A related problem that turned out not to be n^2

Jeff Erickson, True complexity of min-plus convolution?. Timothy Chan, On the Complexity of min-plus convolution.

Problem posed and solved on a blog!

Matching

Sub-n^2.5 matching

H. Alt, N. Blum, K. Mehlhorn, and M. Paul. Computing a maximum cardinality matching in a bipartite graph in time O(n^1.5 m/log n) Information Processing Letters. Volume 37, Issue 4 (February 1991).

Availability:
Free access from within campus using URL above.

Matching 1
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn Popular matchings Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005.

Availability:
Free access from within campus using URL above.

Matching 2
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch Rank-maximal matchings Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004.

Availability:
Free access from within campus using URL above.

Matching 3
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem Proceedings of 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS, 2004. Eds. V. Diekert, M. Habib

Availability:
Free access from within campus using URL above.

Matching 4
Holger Bast, Kurt Mehlhorn, Guido Schdfer, Hisao Tamaki. Matching Algorithms Are Fast in Sparse Random Graphs. Proceedings of 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS, 2004. Eds. V. Diekert, M. Habib

Availability:
Free access from within campus using URL above.

Matching 5
Holger Bast, Kurt Mehlhorn, Guido Schdfer. A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms. Algorithmica 36(1): 75-88 (2003)

Availability:
Free access from within campus using URL above.

Breaking the 1.5 barrier using randomized algorithms
Marcin Mucha, Piotr Sankowski, Maximum Matchings via Gaussian Elimination. Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.

Availability:
Free access from within campus using URL above.

Simpler version of Mucha and Sankowski
Nick Harvey, Algebraic Structures and Algorithms for Matching and Matroid Problems. Arxiv report cs.DS/0601026, January 2006.

Suffix trees and text indexing

Lower bound

Erik D. Demaine, Alejandro López-Ortiz. A linear lower bound on index size for text retrieval. J. Algorithms 48(1): 2-15 (2003)

Availability:
Free access from within campus using URL above.

Succinct representation of trees

J. Ian Munro, Venkatesh Raman. Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. Comput. 31(3): 762-776 (2001)

Availability:
Free access from within campus using URL above.

Succinct representation of suffix trees

J. Ian Munro, Venkatesh Raman, S. Srinivasa Rao. Space Efficient Suffix Trees J. Algorithms 39(2): 205-222 (2001)

Availability:
Free access from within campus using URL above.

Dynamic Space Efficient Trees

J. Ian Munro, Venkatesh Raman, Adam J. Storm. Representing dynamic binary trees succinctly SODA 2001: 529-536

Availability:
Free access from within campus using URL above.

Dynamic Space Efficient Trees

Meng He, J. Ian Munro, S. Srinivasa Rao. A categorization theorem on suffix arrays with applications to space efficient text indexes SODA 2005: 23-32

Availability:
Free access from within campus using URL above.