Adam L. Buchsbaum

Home

CV

Papers

Links to postscript are provided only where not precluded by copyright transfer agreements.

Journal publications

  1. Minimum Density RAID-6 Codes, with J. S. Plank and B. T. Vander Zanden, ACM Transactions on Storage, 6(4), 2011.
  2. Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems, with L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook, SIAM Journal on Computing, 38(4):1533-1573, 2008.
  3. New Results for Finding Common Neighborhoods in Massive Graphs in the Data Stream Model, With R. Giancarlo and B. Racz, Theoretical Computer Science, 407(1-3):302-309, 2008.
  4. Rectangular Layouts and Contact Graphs, with E. R. Gansner, C. M. Procopiuc, and S. Venkatasubramanian, ACM Transactions on Algorithms, 4(1), Article 8 (28 pp.), 2008.
  5. Biased Skip Lists, with A. Bagchi and M. T. Goodrich, Algorithmica special issue on invited papers from ISAAC'02, 42(1):31-48, 2005.
  6. Fast Prefix Matching of Bounded Strings, with G. S. Fowler, B. Krishnamurthy, K.-P. Vo, and J. Wang, ACM J. Experimental Algorithmics special issue on invited papers from ALENEX'03, 10, 2005.
  7. Three-Dimensional Layers of Maxima, with M. T. Goodrich, Algorithmica, 39(4):275-286, 2004.
  8. OPT versus LOAD in Dynamic Storage Allocation, with H. Karloff, C. Kenyon, N. Reingold, and M. Thorup, SIAM Journal of Computing, 33(3):632-646, 2004.
  9. Improving Table Compression with Combinatorial Optimization, with G. S. Fowler and R. Giancarlo, Journal of the ACM, 50(6):825-851, 2003.
  10. On Finding Common Neighborhoods in Massive Graphs, with R. Giancarlo and J. R. Westbrook, Theoretical Computer Science, 299(1-3), 2003.
  11. A Functional Approach to External Graph Algorithms, with J. Abello and J. R. Westbrook, Algorithmica, 32(3):437-58, 2002.
  12. Visualizing and Analyzing Software Infrastructures, with Y. Chen, H. Huang, E. Koutsofios, J. Mocenigo, A. Rogers, M. Jankowsky, and S. Mancoridis, IEEE Software, 18(5):62-70, 2001.
  13. An Approximate Determinization Algorithm for Weighted Finite-State Automata, with R. Giancarlo and J. R. Westbrook, Algorithmica, 30(4):503-26, 2001.
  14. On the Determinization of Weighted Finite Automata, with R. Giancarlo and J. R. Westbrook, SIAM Journal on Computing, 30(5):1502-31, 2000.
  15. A New, Simpler Linear-Time Dominators Algorithm, with H. Kaplan, A. Rogers, and J. R. Westbrook, ACM Transactions on Programming Languages and Systems, 20(6):1265-1296, 1998. Corrigendum, 27(3):383-7, 2005.
  16. Algorithmic Aspects in Speech Recognition: An Introduction, with R. Giancarlo, ACM Journal of Experimental Algorithmics, 2, 1997.
  17. Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues, with R. Sundar and R.E. Tarjan, SIAM J. Computing, 24(6):1190-1206, 1995.
  18. Lazy Structure Sharing for Query Optimization, with R. Sundar and R.E. Tarjan, Acta Informatica, 32:255-70, 1995.
  19. Confluently Persistent Deques via Data-Structural Bootstrapping, with R.E. Tarjan, Journal of Algorithms, 18:513-47, 1995.
  20. Monte Carlo and Markov Chain Techniques for Network Reliability and Sampling, with M. Mihail, Networks, 25(3):117-30, 1995.
  21. Determining Uni-Connectivity in Directed Graphs, with M.C. Carlisle, Information Processing Letters, 48(1):9-12, 1993.
  22. A Data Structure for Arc Insertion and Regular Path Finding, with P.C. Kanellakis and J.S. Vitter, Annals of Mathematics and Artificial Intelligence, 3(2-4):187-210, 1991.

Conference publications

  1. Directed Graphs and Rectangular Layouts, with E. R. Gansner and S. Venkatasubramanian, in Proc. Asia-Pacific Symposium on Visualisation (APVIS07), pp. 61-64, 2007.
  2. Restricted Strip Covering and the Sensor Cover Problem, with A. Efrat, S. Jain, S. Venkatasubramanian, and K. Yi, in Proc. 18th Symp. on Discrete Algorithms, pp. 1056-65, 2007.
  3. Small Parity-Check Erasure Codes---Exploration and Observations, with J. S. Plank, R. L. Collins, and M. G. Thomason, in Proc. 2005 IEEE Int'l. Conf. on Dependable Systems and Networks, 2005.
  4. OPT versus LOAD in Dynamic Storage Allocation, with H. Karloff, C. Kenyon, N. Reingold, and M. Thorup, in Proc. 35th ACM Symp. on Theory of Computing, pp. 556-64, 2003.
  5. Fast Prefix Matching of Bounded Strings, with G. S. Fowler, B. Krishnamurthy, K.-P. Vo, and J. Wang, in Proc. 5th Wks. on Algorithm Engineering and Experiments, pp. 128-39, SIAM, 2003.
  6. Biased Skip Lists, with A. Bagchi and M. T. Goodrich, in Proc. 13th Int'l. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, vol. 2518, pp. 1-13, Springer-Verlag, 2002.
  7. Three-Dimensional Layers of Maxima, with M. T. Goodrich, in Proc. 10th Euro. Symp. on Algorithms, Lecture Notes in Computer Science, vol. 2461, pp. 257-69, Springer-Verlag, 2002.
  8. Improving Table Compression with Combinatorial Optimization, with G. S. Fowler and R. Giancarlo, in Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, pp. 213-22, 2002.
  9. Range Searching Over Tree Cross Products, with M. T. Goodrich and J. R. Westbrook, in Proc. 8th Euro. Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1879, pp. 120-31, Springer-Verlag, 2000.
  10. Algorithmic Aspects of Speech Recognition: A Synopsis, with R. Giancarlo, in Proc. 11th Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 1848, pp. 27-32, Springer-Verlag, 2000.
  11. Maintaining Hierarchical Graph Views, with J. R. Westbrook, in Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, pp. 566-75, 2000.
  12. Engineering the Compression of Massive Tables: An Experimental Approach, with D. F. Caldwell, K. W. Church, G. S. Fowler, and S. Muthukrishnan, in Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, pp. 175-84, 2000.
  13. On External Memory Graph Traversal, with M. Goldwasser, S. Venkatasubramanian, and J. R. Westbrook, in Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, pp. 859-60, 2000.
  14. A Functional Approach to External Graph Algorithms, with J. Abello and J. R. Westbrook, in Proc. 6th Euro. Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1461, pp. 332-43, Springer-Verlag, 1998.
  15. On the Determinization of Weighted Finite Automata, with R. Giancarlo and J. R. Westbrook, in Proc. 25th Int'l. Coll. on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 1443, pp. 482-93, Springer-Verlag, 1998.
  16. Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators, with H. Kaplan, A. Rogers, and J. R. Westbrook, in Proc. 30th ACM Symp. on the Theory of Computing, pp. 279-88, 1998.
  17. Shrinking Language Models by Robust Approximation, with R. Giancarlo and J. R. Westbrook, in Proc. IEEE Int'l. Conf. on Acoustics, Speech, and Signal Processing (ICASSP-98), v. 2, pp. 685-8, Seattle, Washington, 1998.
  18. Methods for Optimal Text Selection, with J. P. H. van Santen, in Proc. 5th Euro. Conf. on Speech Communication and Technology (EUROSPEECH-97), v. 2, pp. 553-6, Rhodes, Greece, 1997.
  19. A Comparison of Head Transducers and Transfer for a Limited Domain Translation Application, with H. Alshawi and F. Xia, in Proc. 36th Ann. Mtg. of the Asso. for Computational Linguistics, Madrid, Spain, 1997.
  20. State-Transition Cost Functions and an Application to Language Translation, with H. Alshawi, in Proc. IEEE Int'l. Conf. on Acoustics, Speech, and Signal Processing (ICASSP-97), v. 1, pp. 103-6, Munich, Germany, 1997.
  21. Selecting Training Inputs via Greedy Rank Covering, with J. P. H. van Santen, in Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, pp. 288-95, 1996.
  22. Monte Carlo and Markov Chain Techniques for Network Reliability and Sampling, with M. Mihail, in Proc. DIMACS Workshop on Computational Support for Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 15:199-222, 1994.
  23. Confluently Persistent Deques via Data Structural Bootstrapping, with R.E. Tarjan, in Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 155-64, 1993.
  24. Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues, with R. Sundar and R.E. Tarjan, in Proc. 33rd IEEE Symp. on Foundations of Computer Science, pp. 40-9, 1992.
  25. A Data Structure for Arc Insertion and Regular Path Finding (Extended Abstract), with P.C. Kanellakis and J.S. Vitter, in Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pp. 22-31, 1990.

Technical reports

  1. Enterprise Navigator: A System for Visualizing and Analyzing Software Infrastructures, with Y. Chen, H. Huang, E. Koutsofios, J. Mocenigo, A. Rogers, M. Jankowsky, and S. Mancoridis, Tech. Report 99.16.1, AT&T Labs - Research, 1999.
  2. State-Transition Cost Functions and an Application to Language Translation, with H. Alshawi, Tech. Report 96.11.1, AT&T Labs - Research, 1996.
  3. Head Automata and Bilingual Tiling: Translation with Minimal Representations, with H. Alshawi, Tech. Report 96.10.1, AT&T Labs - Research, 1996.
  4. Software for Simulating and Analyzing Markov Chains, with M. Mihail, Tech. Report TM-ARH-020-376, Bellcore, 1991.

Ph.D. Thesis

Data-Structural Bootstrapping and Catenable Deques, Princeton University, June, 1993.
© Copyright 2008- Adam L. Buchsbaum.