| 2011 | WADS | On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations. | Michael L. Fredman |
| 2003 | STACS | Adaptive Sorting and the Information Theoretic Lower Bound. | Amr Elmasry, Michael L. Fredman |
| 1998 | STOC | Information Theoretic Implications for Pairing Heaps. | Michael L. Fredman |
| 1993 | FOCS | Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums | Haripriyan Hampapuram, Michael L. Fredman |
| 1993 | ICALP | Products of Finite State Machines with Full Coverage. | David M. Cohen, Michael L. Fredman |
| 1993 | SODA | Data Structures for Traveling Salesmen. | Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer |
| 1990 | FOCS | Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths | Michael L. Fredman, Dan E. Willard |
| 1990 | STOC | BLASTING through the Information Theoretic Barrier with FUSION TREES | Michael L. Fredman, Dan E. Willard |
| 1989 | STOC | The Cell Probe Complexity of Dynamic Data Structures | Michael L. Fredman, Michael E. Saks |
| 1988 | FOCS | Three Stacks | Michael L. Fredman, Deborah L. Goldsmith |
| 1984 | FOCS | Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms | Michael L. Fredman, Robert Endre Tarjan |
| 1983 | FOCS | Hash Functions for Priority Queues | Mikls Ajtai, Michael L. Fredman, Jnos Komls |
| 1982 | FOCS | Storing a Sparse Table with O(1) Worst Case Access Time | Michael L. Fredman, Jnos Komls, Endre Szemerdi |
| 1980 | FOCS | The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries | Michael L. Fredman |
| 1979 | STOC | A Near Optimal Data Structure for a Type of Range Query Problem | Michael L. Fredman |
| 1975 | FOCS | On the Decision Tree Complexity of the Shortest Path Problems | Michael L. Fredman |
| 1975 | STOC | Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees | Michael L. Fredman |