PUBLICATIONS

Articles in Refereed Journals

  1. "A Note on the Application of Graph Theory to Digital Computer Programming," Information and Control, pp. 179-190 (1960).

  2. "Minimum-Redundancy Coding for the Discrete Noiseless Channel," IRE Transactions on Information Theory, Vol. IT-7, pp. 27-38 (1961).

  3. "A Dynamic Programming Approach to Sequencing Problems," (with M. Held), SIAM Journal, Vol. 10, pp. 196-210 (1962).

  4. "Minimization Over Boolean Graphs," (with J. P. Roth), IBM Journal, Vol. 6, pp. 227-238 (1962).

  5. "Assembly-Line Balancing--Dynamic Programming with Precedence Constraints," (with M. Held and R. Shareshian), Journal of Operations Research, pp. 442-459 (1963).

  6. "Functional Decomposition and Switching Circuit Design," SIAM Journal, pp. 291-335 (1963).

  7. "Some Techniques of State Assignment for Synchronous Sequential Machines," IEEE Transactions on Electronic Computers, Vol. EC-13, No. 5, pp. 507-518 (1964).

  8. "The Construction of Discrete Dynamic Programming Algorithms," (with M. Held), IBM Systems Journal, Vol. 4, No. 2, pp. 136-147 (1965).

  9. "Index Register Allocation," (with L. P. Horwitz, R. E. Miller and S. Winograd), Journal of ACM, Vol. 13, pp. 43-61 (1966).

  10. "On Non-terminating Stochastic Games," (with A. J. Hoffman), Management Science, Vol. 12, pp. 359-370 (1966).

  11. "Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing," (with R. E. Miller), SIAM Journal, Vol. 14, pp. 359-370 (1966).

  12. "Finite-State Processes and Dynamic Programming," (with M. Held), SIAM Journal, Vol. 15, pp. 693-718 (1967).

  13. "A Criterion for Planarity of the Square of a Graph," (with F. Harary and W. T. Tutte), Journal of Combinatorial Theory, Vol. 3 (1967).

  14. "The Organization of Computations for Uniform Recurrence Equations," (with R. E. Miller and S. Winograd), J. of ACM, Vol. 14, pp. 563-590 (1967).

  15. "Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines," J. of ACM, Vol. 14, pp. 478-489 (1967).

  16. "Parallel Program Schemata," (with R. E. Miller), J. Comput. System Sci., Vol. 3, pp. 147-195 (1969). Also, Proc. of 8th Annual Symp. on Foundations of Computer Science, pp. 55-61 (1967).

  17. "Parallel Minimax Search for a Maximum," (with W. L. Miranker), Journal of Combinatorial Theory, Vol. 4, pp. 19-34 (1968).

  18. "The Traveling-Salesman Problem and Minimum Spanning Trees," (with M. Held), Operations Research (1970).

  19. "The Traveling-Salesman Problem and Minimum Spanning Trees: Part II," (with M. Held), Mathematical Programming, Vol. 1, pp. 6-25 (1971).

  20. "A Phenomenon in the Theory of Sorting," (with D. Gale), Journal of Computer and System Sciences, Vol. 6, pp. 103-115 (1972). Also, Proc. of 11th Annual Symp. on Foundations of Computer Science, pp. 51-59 (1970).

  21. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," (with J. Edmonds), J. of ACM, Vol. 18, pp. 248-264 (1972).

  22. "A Simple Derivation of Edmonds' Algorithm for Optimum Branchings," Networks, Vol. 1, pp. 265-272 (1972).

  23. "A Algorithm for Maximum Matchings in Bipartite Graphs," (with J. Hopcroft), SIAM J. Computing, Vol. 2, No. 4, pp. 225-231 (1973).Also, Proc. of 12th Annual Symp. on Foundations of Computer Science, pp. 122-125 (1971).

  24. "Near-Optimal Solution to a 2-Dimensional Placement Problem," (with A. C. McKellar and C. Wong), SIAM J. Computing, Vol. 4., No. 3, pp. 271-286 (1975).

  25. "On the Computational Complexity of Combinatorial Problems," Networks, Vol. 5, pp. 45-68 (1975).

  26. "Two Special Cases of the Assignment Problem," (with S-Y R. Li), Discrete Mathematics, Vol. 13, pp. 129-142 (1975).

  27. "Optimality of Huffman Trees," (with C. R. Glassey), SIAM Journal of Applied Mathematics, Vol. 31, No. 2, pp. 368-378 (1976).

  28. "Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane," Mathematics of Operations Research, Vol. 2, No. 3, pp. 209-224 (1977). Reprinted in MC Tract 99, Interfaces Between Computer Science and Operations Research, Mathematische Centrum, Amsterdam, pp. 141-231 (1978).

  29. "A Characterization of the Minimum Cycle Mean in a Digraph," Discrete Math., Vol. 23, pp. 309-311 (1978).

  30. "A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem," SIAM J. Computing, Vol. 8, No. 4, pp. 561-573 (1979).

  31. "An Algorithm to Solve the m x n Assignment Problem in Expected Time 0( mn log n)," Networks, Vol. 10, No. 2 (1980).

  32. "Linear Expected-Time Algorithms for Connectivity Problems," (with R. E. Tarjan), Journal of Algorithms, Vol. 1, pp. 374-393 (1980). Also, 12th Symp. on Theory of Computing, pp. 368-377 (1980).

  33. "Parametric Shortest Path Algorithms with an Application to Cyclic Staffing," (with J. B. Orlin), Discrete Applied Mathematics 3, pp. 37-45 (1981).

  34. "The Complexity of Testing Whether a Graph is a Superconcentrator," (with M. Blum, C. Papadimitriou, O. Vornberger and M. Yannakakis), Information Processing Letters, Vol. 13, pp. 164-167 (1981).

  35. "On Linear Characterizations of Combinatorial Optimization Problems," (with C. Papadimitriou), SIAM J. Computing, Vol. 11, No. 4, pp. 620-632 (1982). Also, Proc. of 21st Annual Symp. on Foundations of Computer Science, pp. 1-9 (1980).

  36. "Dynamic Programming Meets the Principle of Inclusion and Exclusion," Operations Research Letters, Vol. 1, pp. 49-51 (1982).

  37. "Turing Machines that Take Advice," (with R. Lipton), L'Enseignement Mathematique, Vol. 28, pp. 191-209 (1982). Also, "Some Connections Between Nonuniform and Uniform Complexity Classes," 12th Symp. on Theory of Computing, pp. 302-309 (1980).

  38. "Searching for an Optimal Path in a Tree with Random Costs," (with J. Pearl), Artificial Intelligence, Vol. 21, pp. 99-116 (1983).

  39. "On the Security of Ping-Pong Protocols," (with D. Dolev and S. Even), Information and Control Vol. 55, pp. 57-68 (1982).

  40. "Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem," (with M. Luby), Journal of Complexity, Vol. 1, pp. 45-64 (1985).

  41. "A Fast Parallel Algorithm for the Maximal Independent Set Problem," (with A. Wigderson), JACM, Vol. 32, pp. 762-773 (1985). Also, 16th Symp. on Theory of Computing, pp. 266-272 (1984).

  42. "A Family of Simplex Variants Solving an Linear Program in Expected Number of Pivots Depending on Only," (with I. Adler and R. Shamir), Mathematics of Operations Research, Vol. 11, pp. 570-590 (1986).

  43. "Constructing a Perfect Matching in Random NC," (with E. Upfal and A. Wigderson), Combinatorica, Vol. 6, pp. 35-48 (1986). Also, 17th Symp. on Theory of Computing, pp. 22-32 (1985).

  44. "Probabilistic Analysis of Optimum Partitioning," (with N. Karmarkar, G. S. Lueker and A. M. Odlyzko), J. Applied Probability, Vol. 23, pp. 626-645 (1986).

  45. "Combinatorics, Complexity and Randomnes," (Turing Award Lecture), Communication ACM, Vol. 29, pp. 98-111 (1986).

  46. "Efficient Randomized Pattern-Matching Algorithms," (with M. Rabin), IBM Journal of Research and Development, (March 1987).

  47. "Global Wire Routing in 2-Dimensional Arrays," (with F. Leighton, R. Rivest, C. Thompson, U. Vazirani, V. Vazirani), Algorithmica, Vol. 2, pp. 113-129 (1987). Also, Proc. 24th Annual Symp. on Foundations of Computer Science, pp. 453-459 (1983).

  48. "A Simplex Variant Solving an m x d Linear Program in O(min (m2,d2)) Expected Number of Pivot Steps," (with I. Adler and R. Shamir), Journal of Complexity, Vol. 3, pp. 372-387 (1987).

  49. "The Complexity of Parallel Search," (with E. Upfal and A. Wigderson), J. Comp. Sys. Sci., Vol. 36, No. 2, pp. 225-253 (1988).

  50. "Deferred Data Structuring," (with R. Motwani and P. Raghavan), SIAM J. Comp., Vol. 17, No. 5 (October 1988).

  51. "Monte-Carlo Approximation Algorithms for Enumeration Problems," (with M. Luby and N. Madras), Journal of Algorithms, Vol. 10, No. 3 (September 1989).

  52. "The Transitive Closure of a Random Digraph," Random Structures and Algorithms, Vol. 1, No. 1 (1990).

  53. "FFD Bin Packing for Item Sizes with Distributions on [0, 1/2]," (with S. Floyd), Algorithmica, Vol. 6, pp. 222-240 (1991). Also, Proc. of 27th Annual Symp. on Foundations of Computer Science, pp. 322-330 (1986).

  54. "Subtree Isomorphism is in Random NC," (with P. B. Gibbons, G. L. Miller and D. Soroker), Discrete Applied Mathematics, Vol. 29, No. 1, pp. 35-62 (1990). Also, Proc. of Aegean Workshop on Computing (June 1988).

  55. "Transitive Compaction in Parallel via Branchings," (with P. Gibbons, V. Ramachandran, D. Soroker and R. Tarjan), Journal of Algorithms, Vol. 12, pp. 110-125 (1991).

  56. "Three-Stage Generalized Connectors," SIAM Journal on Discrete Mathematics Vol. 5, No. 2, pp. 259-272 (May 1992).

  57. "An Introduction to Randomized Algorithms," Discrete Applied Mathematics, Vol. 34, pp. 165-201 (1991).

  58. "Probabilistic Analysis of Network Flow Algorithms," (with R. Motwani and N. Nisan), Math. of Operations Research, (August 1992).

  59. "Competitive Paging Algorithms," (with A. Fiat, M. Luby, L. McGeoch, D. Sleator, N. Young), J. of Algorithms, Vol. 12, pp 685-699 (1991).

  60. "On the Power of Randomization in Online Algorithms," (with S. Ben-David, A. Borodin, G. Tardos, A. Wigderson), Algorithmica Vol. 11, Number 1 (1994).

  61. "A Monte-Carlo Algorithm for Estimating the Permanent," (with N. Karmarkar, R. Lipton, L. Lovász, M. Luby), SIAM Journal on Computing.

  62. "Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computations," (with Y. Zhang), JACM.

  63. "Coding Techniques for Handling Failures in Large Disk Arrays," (with G. Gibson, L. Hellerstein, R. M. Karp, R. H. Katz, D. A. Patterson), Algorithmica. Also, "Failure Correction Techniques for Large Disk Arrays," Proceedings of the Third Conference on Architectural Support for Programming Languages and Operating Systems (1988).

  64. "On Parallel Evaluation of Game Trees," (with Y. Zhang), JACM. Also, Proc. of ACM Symp. on Parallel Algorithms and Architectures, (July 1989).

  65. "Probabilistic Recurrence Relations," JACM, Vol. 41, No. 6, pp. 1136-1150 (1994). Also, Proc. 23rd Annual ACM Symp. on Theory of Computing, pp. 190-197 (1991).

  66. "A Method for Obtaining Randomized Algorithms with Small Tail Probabilities," (with H. Alt, L. Guibas, K. Mehlhorn and A. Wigderson), Algorithmica, Vol. 16, No. 4-5, Oct.-Nov. 1996, pp.543-547.

  67. "Average Case Analysis of a Heuristic for the Assignment Problem," (with A. Rinnooy Kan and R. Vohra), Math. of Operations Research, Vol. 19, No. 3, pp. 513-522 (1994).

  68. "Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology," (with Farid Alizadeh, Lee A. Newberg, and Deborah K. Weisser), Algorithmica (1995) 13:52-76. Also in Proc. ACM/SIAM Symp. on Discrete Algorithms (1993).

  69. "A Graph-Theoretic Game and its Application to the k-Server Problem," (with N. Alon, D. Peleg and D. West), SIAM J. Computing (1995) 24:78-100. Also in On-Line Algorithms, "DIMACS Series in Discrete Mathematics and Theoretical Computer Science," American Mathematical Society and Association for Computing Machinery, eds. L McGeogh and D. Sleator, Vol. 7, pp. 1-10 (1992).

  70. "An Algorithm for Analyzing Probed Partial Digest Experiments," (with L. Newberg), CABIOS (1995).

  71. "When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem," (with A. Frieze and B. Reed), SIAM J. Computing, Vol. 24, No. 3, 484-493 (1995).

  72. "Physical Mapping of Chromosomes Using Unique Probes," (with F. Alizadeh, D.K. Weisser, G. Zweig), Journal of Computational Biology, Vol. 2, No. 2, pp. 159-185 (1995).

  73. "Bounded Branching Process and AND/OR Tree Evaluation," (with Y. Zhang), Random Structures and Algorithms, Vol. 7, No. 2, pp. 97-116 (1995).

  74. "Efficient PRAM Simulation on a Distributed Memory Machine," (with M. Luby and F. Meyer auf der Heide), Algorithmica, Vol. 16, No. 4/5, Special Issue, pp. 517-542 (1996).

  75. "LogP: A practical Model of Parallel Computation," (with Culler D.E., Patterson, D., Sahay, A., Santos, E.E., Schauser, K.E., Subramonian R., Von-Eicken, T.,). Comm. of The ACM, Volume 39, No. 11 pp. 78-85 (1996).

  76. "The Rank of Sparse Random Matrices over Finite Fields," (with J. Bloemer and E. Welzl). Random Structures and Algorithms (1997).

  77. `Nearly Optimal Competitive Online Replacement Policies," (with R. El-Yaniv), Math. of Operations Research, Vol. 22, No. 3 (1997).

  78. "Mapping Clones with A Given Ordering or Interleaving," (with T. Jiang). Algorithmica, Vol. 21, No. 3, pp. 262-284 (1998). Preliminary version in Proceedings ACM/SIAM Symposium on Discrete Algorithms, Jan. 1997.

  79. "Graph Traversals, Genes and Matroids: An Efficient Case of the Traveling-Salesman Problem," (with D. Gusfield, L. Wang and P. Stelling). Discrete Applied Mathematics, Vol. 88, Nos. 1-3, (1998). Also in Combinatorial Pattern Matching (1996).

  80. "Error Checking and Graphical Representation of Multiple-Complete- Digest (MCD) Restriction-Fragment Maps," (with E. Thayer and M.Olson). Genome Research (1999).

  81. "Error-Resilient DNA Computation," (with Kenyon,C. and Waarts,O.), Random Structures and Algorithms 15(3-4): 450-466 (1999).

  82. "An Optimal Algorithm for Monte Carlo Estimation," (with P. Dagum, M. Luby and S. Ross), SIAM J. Computing 29(5): 1484-1496 (2000).

  83. "Parallel Sorting with Limited Bandwidth," (with M. Adler and J. Byers), SIAM Journal on Computing 29(6): 1997-2015 (2000).

  84. "An Algorithmic Approach to Multiple Complete Digest Mapping," (with Fasulo D., Jiang T., Settergren R. and Thayer, E.C.), Journal of Computational Biology (2000).

  85. "Algorithms for Optical Mapping," (with Shamir, R.), Journal of Computational Biology 7(1,2), (2000).

  86. "Universal DNA Tag Systems: A Combinatorial Design Scheme," (with Ben-Dor, A., Schwikowski, B. and Yakhini, Z., Journal of Computational Biology, (2000).

  87. "An Algorithm Combining Discrete and Continuous Methods for Optical Mapping," (with Pe'er, I. and Shamir, R.), Journal of Computational Biology, (2000).

  88. "Optimal Search and One-Way Trading Online Algorithms," (with El-Yaniv,R., Fiat, A. and Turpin, G.), Algorithmica 30(1) 101-138, (2001).

  89. "Algorithms for Graph Partitioning on the Planted Partition Model," (with Condon, A.), Random Structures and Algorithms (18) 116-140 (2001).

  90. "The Efficiency of Resolution and Davis-Putnam Procedures," (with Beame,P., Pitassi, T. and Saks, M.), SIAM Journal on Computing, (31)4 1048-1075 (2001).

  91. "Mathematical Challenges from Genomics and Molecular Biology," Notices of the AMS, 49(5) 544-553 (2002).

  92. "A Simple Algorithm for Finding Frequent Elements in Streams and Bags," (with Shenker, S. and Papadimitriou, C.), Transactions on Database Systems (2003).

  93. "Coalescing Times for IID Random Variables," (with Adler, I., Ahn, H.S. and Ross, S.M.), Random Structures and Algorithms (2003).

  94. "Efficient Reconstruction of Haplotype Structure Via Perfect Phylogeny," (with E. Eskin and E. Halperin), Journal of Bioinformatics and Computational Biology, 1(1) 1-20 (2003).

  95. "Conserved Pathways Within Bacteria and Yeast as Revealed by Global Protein Network Alignment," (with Kelley, B.P., Sharan, R., Sittler, E.T., Root, D.E., Stockwell, R. and Ideker, T.), PNAS, October, 2003.

  96. "Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem," (with A, Ben-Dor, B. Chor and Z. Yakhini) Journal of Computational Biology 10(3-4), 373-384 (2003).

  97. "The Restriction Scaffold Problem," (with A. Ben-Dor, B. Schwikowski and R. Shamir)," J. Comp. Bio 10(3-4), 385-398 (2003)

  98. "Towards Optimally Multiplexed Applications of Universal DNA Tag Systems," (with A. Ben-Dor, T. Hartman, B. Schwikowski, R. Sharan and Y. Yakhini), Journal of Computational Biology (submitted).

  99. "MotifPrototyper: A Bayesian Profile Model for Motif Families," (with E. Xing), PNAS (2004) (to appear).

Contributions to Books

  1. "Reducibility Among Combinatorial Problems," in Complexity of Computer Computations (Symposium Proceedings), Plenum Press (1972).

  2. "Two Combinatorial Problems Related to External Sorting," in Combinatorial Algorithms (Symposium Proceedings), Prentice-Hall (1972).

  3. "Computational Complexity of Combinatorial and Graph-Theoretic Problems," in Theoretical Computer Science, ed. by F. Preparata, Edizioni Cremonese, Roma, pp. 98-184 (1975).

  4. "The Probabilistic Analysis of Some Combinatorial Search Algorithms," in Algorithms and Complexity, J. Traub, ed., Academic Press (1976).

  5. "Probabilistic Analysis of a Canonical Numbering Algorithm for Graphs," Proc. AMS Symp. in Pure Mathematics, Vol. 34, pp. 365-378 (1979).

  6. "Theory of Computation," (with six co-authors), chapter in What Can Be Automated? (The COSERS Report), Massachusetts Institute of Technology Press (1980).

  7. "The Computational Complexity of Network Problems," Proc. AMS Symp. in Applied Mathematics, Vol. 26, pp. 45-62 (1982).

  8. "Probabilistic Analysis of Combinatorial Optimization Algorithms," Proc. of the International Congress of Mathematicians, Warsaw (1983).

  9. "Probabilistic Analysis of Heuristics," (with J. M. Steele), Chapter in The Traveling-Salesman Problem, (ed. A. Rinnooy Kan, E. L. Lawler, J. K. Lenstra, D. Shmoys), J. Wiley (1985).

  10. "Probabilistic Analysis of Combinatorial Algorithms: An Annotated Bibliography," (with J. K. Lenstra, C. McDiarmid and A. H. G. Rinnooy Kan), Chapter in Combinatorial Optimization: Annotated Bibliographies, (edited by M. O'Heigeartaigh, J. K. Lenstra and A. H. G. Rinnooy Kan), J. Wiley (1985).

  11. "An Upper Bound on the Expected Cost of an Optimal Assignment," in Discrete Algorithms and Complexity Theory, Academic Press (1987).

  12. "A Position Paper on Parallel Computation," in Opportunities and Constraints of Parallel Computing, (J. L. C Sanz, Editor), Springer-Verlag, pp. 73-75 (1989).

  13. "Parallel Algorithms for Shared-Memory Machines," (with V. Ramachandran), Handbook of Theoretical Computer Science, Algorithms and Complexity, ed. J. V. Leeuwen, North-Holland, Vol. A, pp. 871-941 (1990).

  14. "Parallel Combinatorial Computing," in Very Large Scale Computation in the Twenty-first Century, ed. Jill P. Mesirov, SIAM, Philadelphia, pp. 221-238 (1991). SIAM (1991).

  15. "On-line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future?," in Algorithms, Software, Architecture, Information Processing 92, ed. van Leeuwen, J., Vol. I, pp. 416-429, North-Holland (1992).

  16. "The Mysteries of Algorithms," chapter in People and Ideas in Theoretical Computer Science, ed. C. Calude, Springer Verlag (1998)

  17. "The Genomics Revolution and its Challenges for Algorithmic Research," in Current Trends in Theoretical Computer Science, ed. G. Paun, G. Rozenberg, A. Salomaa World Scientific (2001) pp. 631-642.

Books

  1. Complexity of Computation (ed. R. M. Karp), Proc. AMS-SIAM Symposia in Applied Mathematics, Vol. VII (1974).

Papers in Refereed Conference Proceedings

  1. "A Computer Program for the Synthesis of Combinational Switching Circuits," (with F. E. Mc Farlin, J. P. Roth and J. R. Wilts), Proc. of 2nd Annual Symp. on Foundations of Computer Science, pp. 182-194 (1961).

  2. "Rapid Identification of Repeated Patterns in Strings, Trees and Arrays," (with R. Miller and A. Rosenberg), Proc. of 4th Annual ACM Symp. on Theory of Computing, pp. 125-136 (1972).

  3. "Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems," (with R. Aleilunias, R. Lipton, L. Lovász, and C. Rackoff), 20th Annual Symp. on Foundations of Computer Science, pp. 218-223 (1979).

  4. "Maximum Matchings in Sparse Random Graphs," (with M. Sipser), Proc. 22nd Annual Symp. on Foundations of Computer Science, pp. 364-375 (1981).

  5. "An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem," (with N. Karmarkar), Proc. 23rd Annual Symp. on Foundations of Computer Science, 312-320 (1982).

  6. "Monte-Carlo Algorithms for Enumeration and Reliability Problems," (with M. Luby), Proc. 24th Annual Symp. on Foundations of Computer Science, pp. 56-84 (1983).

  7. "Probabilistic Analysis of Multidimensional Bin Packing Problems," (with M. Luby and A. Marchetti Spaccamela), Proc. of the 16th ACM Symp. on Theory of Computing, pp. 289-298 (1984).

  8. "The Complexity of Parallel Computation on Matroids," Proc. 26th Annual Symp. on Foundations of Computer Science, pp. 541-550 (1985).

  9. "Are Search and Decision Problems Computationally Equivalent?," (with E. Upfal and A.Wigderson), Proc. of 26th Annual Symp. on Foundations of Computer Science, pp. 464-475 (1985).

  10. "On a Search Problem Related to Branch-and-Bound Procedures," (with M. Saks and A. Wigderson), Proc. of the 27th Annual Symp. on Foundations of Computer Science, (1986).

  11. "A Randomized Parallel Branch-and-Bound Procedure," (with Y. Zhang), Proc. of the 20th ACM Symp. on Theory of Computing, pp. 290-300 (May 1988).

  12. "Failure Correction Techniques for Large Disk Arrays," (with G. Gibson, L. Hellerstein, R. H. Katz, D. A. Patterson), Proc. of the Third Conference on Architectural Support for Programming Languages and Operating Systems, (1988).

  13. "An Optimal Algorithm for On-line Bipartite Matching (Extended Abstract)," (with U. Vazirani and V. Vazirani), ACM Symp. on Theory of Computing, (1990).

  14. "When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?," (with A. Frieze and B. Reed), Proc. Symp. on Integer Programming and Combinatorial Optimization, (1992).

  15. "Competitive Analysis of Financial Games," (with R. El-Yaniv, A. Fiat, G. Turpin), IEEE Symp. on Foundations of Computer Science, (1992).

  16. "Mapping the Genome: Some Combinatorial Problems Arising in Molecular Biology," Proc. ACM Symposium on Theory of Computing, (1993).

  17. "Optimal Broadcast and Summation in the LogP Model," (with A. Sahay, E. Santos and K.E. Schauser), Proc. ACM Symp. on Parallel Algorithms and Architectures, (1993).

  18. "The Mortgage Problem," (with R. El-Yaniv), Proc. Second Israel Symp. on Theory of Computing and Systems, (1993).

  19. "A Generalization of Binary Search," Proc. Workshop on Algorithms and Data Structures, Springer-Verlag, (1993).

  20. "Selection in the Presence of Noise: the Design of Playoff Systems," (with M. Adler, P. Gemmell, M. Harchol and C. Kenyon), Proc. Fifth ACM/SIAM Symp. on Discrete Algorithms, (1994).

  21. "Scheduling Parallel Communication: the h-relation Problem," (with M. Adler, J.W. Byers), Proc. 20th Symp. on Mathematical Foundations of Computer Science, ed. J. Wiedermann and P. Hajek, pp. 1-20., Springer Verlag, (1995).

  22. "The Bit Vector Intersection Problem," (with O. Waarts and G. Zweig), Proc. 36th Annual Symposium on Foundations of Computer Science, pp. 621-630. IEEE Computer Society Press, (1995).

  23. "An Optimal Algorithm for Monte Carlo Estimation," (with P. Dagum, M. Luby and S. Ross), SIAM J. Computing 29(5):1484-1496 (2000). Also in Proc. 36th Annual Symp. on Foundations of Computer Science, pp. 142-149, 1995. IEEE Computer Science Press.

  24. "Parallel Sorting with Limited Bandwidth," (with M. Adler and J. Byers), SIAM Journal on Computing 29(6): 1997-2015 (2000). Also in Proc. 7th Annual Symposium on Parallel Algorithms and Architectures, pp. 129-136. ACM, (1995).

  25. "Error-Resilient DNA Computation," (with Kenyon,C. and Waarts,O.), Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms, (1996).

  26. "Efficient Information Gathering on the Internet," (with O. Etzioni, S. Hanks, T. Jiang, O. Madani and O. Waarts), pp. 234-243, Proceedings 37th Annual IEEE Symp. on Foundations of Computer Science, (1996).

  27. "An Algorithmic Approach to Multiple Complete Digest Mapping," (with Fasulo D., Jiang T., Settergren R. and Thayer, E.C.), Proceedings of RECOMB 97, pp. 118-127, (1997).

  28. "Constructing Maps Using the Span and Inclusion Relations," (with D. Fasulo, T. Jiang and N. Sharma), Proceedings of RECOMB, (1998).

  29. "On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas," (with P. Beame, M. Saks and T. Pitassi), STOC, 1998.

  30. "Algorithms for Graph Partitioning on the Planted Partition Model," (with Condon, A.), RANDOM-APPROX 1999: 221-232.

  31. "An Algorithm Combining Discrete and Continuous Methods for Optical Mapping," (with Pe'er, I. and Shamir, R.), ISMB, 159-68, (1999).

  32. "Algorithms for Choosing Differential Gene Expression Experiments," (with R. Stoughton and K. Yeung), Proceedings of RECOMB, 1999.

  33. "Universal DNA Tag Systems: A Combinatorial Design Scheme," (with Ben-Dor, A., Schwikowski, B. and Yakhini, Z., RECOMB, 2000.

  34. "Randomized Rumor Spreading," (with Schindelhauer, C., Shenker, S. and Voecking, B.), Proceedings 41st Annual IEEE Symp. on Foundations of Computer Science, (2000).

  35. "Optimization Problems in Congestion Control," (with Koutsoupias, E., Papadimitriou, C. and Shenker, S.), Proceedings 41st Annual IEEE Symp. on Foundations of Computer Science, (2000).

  36. "Discovery of Regulatory Interactions Through Perturbation: Inference and Experimental Design," (with Ideker, T.E. and Thorsson, V.), Pacific Symp. Biocomputing, (2000).

  37. "CLIFF: Clustering of High-Dimensional Microarray Data via Iterative Feature Filtering Using Normalized Cuts," (with Xing, E.P.), Intelligent Systems in Molecular Biology, (2001).

  38. "Feature Selection for High-Dimensional Genomic Microarray Data," (with Xing, E.P. and Jordan, M.I.), Machine Learning Symposium, (2001).

  39. "A Scalable Content-Addressable Network," (with Ratnasamy, S., Francis, P., Handley, M. and Shenker, S.), Proc. Sigcomm 2001, 161-172 (2001).

  40. "Application-level Multicast Using Content-Addressable Networks," (with Ratnasamy, S., Francis, P., Handley, M. and Shenker, S.), Infocom, (2001).

  41. "Discovering Local Structure in Gene Expression Data: The Order Preserving Submatrix Problem," (with Ben-Dor, A., Chor, B. and Yakhini, Z.), Proceedings of Recomb, 2002.

  42. "The Restriction Scaffold Problem," (with Ben-Dor, A., Chor, B., and Yakhini, Z.), Proceedings of RECOMB, 2002.

  43. "Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP," (with Akella, A., Seshan, S., Shenker, S. and Papadimitriou, C.), Proc. Sigcomm, (2002).

  44. "Topologically-Aware Overlay Construction and Server Selection," (with Ratnasamy, S., Handley, M. and Shenker, S.), Proceedings of Infocom, 2002.

  45. "A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Systems," (with E. Xing, M. Jordan and S. Russell, Neural Information Processing Systems, (2002).

  46. "A Stochastic Process on the Hypercube with Applications to Peer-to-peer Networks," (with Adler, M., Halperin, E. and Vazirani, V.), Proc. Thirty-fifth Annual ACM Symposium on Theory of Computing, (STOC2003).

  47. "Large-Scale Reconstruction of Haplotypes from Genotype Data," (with E. Eskin and E. Halperin), Proceedings of RECOMB, 2003.

  48. "Detecting Protein Sequence Conservation Via Metric Embeddings," (with J. Buhler, E. Halperin, R. Krauthgamer and B. Westover, Proc. Intelligent Systems in Molecular Biology, (2003).

  49. "A Gambling Game and Its Application to the Analysis of Adaptive Randomized Rounding," (with C. Kenyon), In Springer-Verlag Lecture Notes in Computer Science, Volume 2764/2003, ``Approximation, Randomization, and Combinatorial Optimization: Algorithms and techniques,'' pp. 329-340, (2003).

  50. "Load Balancing in Structured P2P Systems," (with A. Rao, K. Lakshminarayanan, S. Surana and I. Stoica), Proc. Second International Workshop on Peer-to-Peer Systems, (2003).

  51. "CREME: A Framework for Identifying Cis-regulatory Modules in Human-mouse Conserved Segments," (with R. Sharan, I. Ovcharenko and A. Ben-Hur), Proc. Intelligent Systems in Molecular Biology, (2003).

  52. "LOGOS: A Modular Bayesian Model for de novo Motif Detection," (with E. Xing, W. Wu and M. Jordan), Proc. IEEE Computer Society Bioinformatics Conference, (2003).

  53. "Reconstructing Chain Functions in Genetic Networks," (with I. Gat-Viks, R. Shamir and R. Sharan), Proc. Pacific Symposium on Biocomputing, (2003).

  54. "Load Balancing in Dynamic Structured P2P Systems," (with B. Godfrey, K. Lakshminarayanan, S. Surana and I. Stoica), Proc. INFOCOM, 2004.

  55. "Perfect Phylogeny and Haplotype Assignment," (with Eran Halperin), Proc. RECOMB, 2004.

  56. "Global Synchronization in Sensornets," (with J. Elson, C. Papadimitriou and S. Shenker) Proc. LATIN, 2004 (609-624).

  57. "Finite-Length Analysis of LT-Codes," (with M. Luby and A. Shokrollahi), submitted to International Symp. on Information Theory, (2004).

  58. "Search Strategies in Inter-Domain Traffic Engineering," (with K. Chandrayana, M. Roughan, Sen and Y. Zhang), submitted to SIGCOMM, 2004.

  59. "Achieving Fairness Through Selective Early Dropping," (with J. Scott), submitted to SIGCOMM, 2004.

  60. "The Minimum-Entropy Set Cover Problem," (with E. Halperin), ICALP, 2004, 733-744.

  61. "Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data," (with R. Sharan, T. Ideker, B. Kelley and R. Shamir), RECOMB, 2004, 282-289.
Selected Additional Publications
  1. "Selected Topics in Automata Theory," Report, Systems Engineering Laboratory, University of Michigan, Ann Arbor, prepared under Air Force Contract AF-30(602)-3546, (1966).

  2. "A Combined Ascent and Branch-and-Bound Algorithm for the Traveling- Salesman Problem," (with M. Held), 7th Mathematical Programming Symp., The Hague (1970).

  3. "Large-Scale Optimization and the Relaxation Method," (with M. Held and P. Wolfe), Proc. of 25th National ACM Meeting, (1972).

  4. "The Fast Approximate Solution of Hard Combinatorial Problems," Proc. of 6th Southeastern Conference on Combinatorics, Graph Theory and Computing, (1976).

  5. "Computers as Puzzle-Solvers - The Challenge of Efficient Search," Proc. of IRIA Tenth Anniversary Colloquium, (1978).

  6. "Combinatorial Search Problems: Is Exponential Growth Inevitable?," Forefront, (1977).

  7. "Roles of Industry and the University in Computer Research and Development," (with 11 coauthors), National Academy Press, (1982).

  8. "The Differencing Method of Set Partitioning," (with N. Karmarkar), Report No. UCB/CSD 82/113, Computer Science Division, University of California, Berkeley (December 1983).

  9. "A Time-Randomness Trade-Off," (with N. Pippenger and M. Sipser), abstract, AMS Conference on Probabilistic Computational Complexity, Durham, N.H. (1985)

  10. "Circuit Placement by Eigenvector Decomposition," (with J. Frankle), Proc. of ICCAD, (1986).

  11. "Forum on Military Funding of Mathematics," (with six co-authors) The Mathematical Intelligencer, Vol. 9, No. 11, pp. 52-62 (1987).

  12. "On the Cruelty of Really Teaching Computer Science," Response to Dijkstra's Article, COMM. ACM, Vol. 32, pp. 1410-1412 (December 1989).

  13. "Analysis of Algorithms," in Strategic Directions in Computing Research, ACM and The Computing Research Association, Section 3.2, pp. 23-26, October 11-13 (1989).

  14. "NP-Complete Problems," videotape, University Video Communications, (1993).

  15. "Modeling Parallel Comunication," (Abstract). Proceedings 9th International Parallel Processing Symp., IEEE Computer Society, (1995).

  16. "Nearly Optimal Competitive Online Replacement Policies," (with R. El-Yaniv,) Mathematics of Operations Research, Vol. 22, No. 3 (1997).

  17. "Theory of Computing: Goals and Directions," (with A.V. Aho, D.S. Johnson, S.R. Kosaraju, C.C. McGeoch, C.H. Papadimiriou, P. Pevzner), University of Washington Technical Report, CSE-96-03-03 (1996).

  18. "Fast and Intuitive Clustering of Web Documents," (with Zamir, O., Etzioni, O., Madani, O.), poster at KDD-97.

  19. "Report on the DNA/Biomolecular Computing Workshop," (with Delcher, A.L., Hood, L.), [Report to NSF], June 6-7, 1996.

  20. "Bridging the Gap: Connecting Theoretical Computer Science with the World of Applications," (with Aho, A., Johnson, D.S., Kosaraju, S.R., McGeoch, C.C., Papadimitriou, C.H., Pevzner, P.), UW/CSE Department Technical Report, 93-3.

  21. "An XOR-Based Erasure-Resilient Coding Scheme," (with Blomer, J, Kalfane, M., Karpinski, M., Luby, M. and Zuckerman, D.), ICSI Technical Report No. TR-95-048 (1995).

  22. "Emerging Opportunities for Theoretical Computer Science," (with A. Aho, D. Johnson, R. Kosaraju, C. McGeoch and C. Papadimitriou), SIGACT News, Vol. 28, No. 3, September, 1997.

  23. "Variations on the Theme of `Twenty Questions," IEEE Information Theory Newsletter, (2000).

  24. "Challenges for Theory of Computing," (with Condon.,A., Edelsbrunner, H. and others), SIGACT News 30(2), 62-76 (1999).

  25. "The Genomic Revolution and its Challenges for Algorithmic Research," EATCS Bulletin, (2000).
 

PATENTS

U.S. Patent No. 5,469,154, Multiconnection Switching Networks, Nov. 21, 1995.

November, 2003

Footnotes

... Proceedings
This list omits those conference papers prior to 1999 that later appeared as refereed journal articles.

Back to top

Last updated 07/29/05