Baruch Schieber


Baruch Schieber



Baruch Schieber
Welcome to my home page. I work in the Mathematical Sciences Department as the manager of the Theory of Computation group. My main interests are algorithms, combinatorial optimization, routing and scheduling. Baruch Schieber
IBM T.J. Watson Research Center
P.O. Box 218
Yorktown Heights, NY 10598
TEL: (914) 945-1169
FAX: (914) 945-3434
sbar@watson.ibm.com


Education Projects Publications Conferences


EDUCATION


[1985-1987]

Ph.D. in Computer Science, Department of Computer Science, School of Mathematical Sciences, Tel-Aviv University, Tel Aviv, Israel.
Thesis: Design and analysis of some parallel algorithms.
Advisor: Prof. Uzi Vishkin.

[1983-1984]

M.Sc. in Computer Science, Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel.
Thesis: Parallel algorithms for finding maximum bipartite matchings and maximum flow in 0-1 networks.
Advisor: Prof. Shlomo Moran.

[1977-1980]

B.Sc. in Computer Science, Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel.


PROJECTS



PUBLICATIONS


Chapters in books Journal publications

Jump to Paper No. 1 11 21 31 41

  1. Y. Maon, B. Schieber and U. Vishkin, Parallel Ear Decomposition Search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47 (1986), pp. 277--298.
  2. A. Apostolico, C. Iliopoulos, G.M. Landau, B. Schieber and U. Vishkin, Parallel construction of a suffix tree with applications. Algorithmica, 3 (1988), pp. 347--365. pp. 314--325.
  3. Z. Galil and B. Schieber, On finding most uniform trees (a note). Discrete Applied Mathematics, 20 (1988), pp. 173--175.
  4. B. Schieber and U. Vishkin, On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing, 17 (1988), pp. 1253--1262.
  5. B. Schieber and S. Moran, Parallel algorithms for maximum bipartite matchings and maximum 0--1 flows. Journal of Parallel and Distributed Computing, 6 (1989), pp. 20--38.
  6. Y. Mansour and B. Schieber, Finding the edge connectivity of directed graphs. Journal of Algorithms, 10 (1989) pp. 76--85.
  7. Y. Afek, G.M. Landau, B. Schieber and M. Yung, The power of multimedia: combining point-to-point and multiaccess networks. Information and Computation, 84 (1990), pp. 97--118.
  8. B. Schieber and U. Vishkin, Finding all nearest neighbors for convex polygons in parallel: a new lower bound technique and a matching algorithm. Discrete Applied Mathematics, 29 (1990), pp. 97--111.
  9. Y. Mansour, B. Schieber and P. Tiwari, Lower bounds for computations with the floor operation. SIAM Journal on Computing, 20 (1991), pp. 315--327.
  10. S. Khuller and B. Schieber, Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs. SIAM Journal on Computing, 20 (1991), pp. 352--375.
Jump to Paper No. 1 11 21 31 41
  1. P.K. Agarwal, A. Aggarwal, B. Aronov, S.R. Kosaraju, B. Schieber and S. Suri, Computing external farthest neighbors for a simple polygon. Discrete Applied Mathematics, 31 (1991), pp. 97--111.
  2. Y. Mansour, B. Schieber and P. Tiwari, A lower bound for integer greatest common divisor computations. Journal of the ACM, 38 (1991), pp. 453--471.
  3. L.L. Larmore and B. Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure. Journal of Algorithms, 12 (1991), pp. 490--515.
  4. D. Gusfield, G.M. Landau and B. Schieber, An efficient algorithm for the all pairs Suffix-Prefix problem. Information Processing Letters, 41 (1992), pp. 181--185.
  5. S. Khuller and B. Schieber, On independent spanning trees. Information Processing Letters, 42 (1992), pp. 321--323.
  6. Y. Mansour and B. Schieber, The intractability of bounded protocols for non-FIFO channels. Journal of the ACM, 39 (1992), pp. 783--799.
  7. M.W. Bern, H.J. Karloff, P. Raghavan and B. Schieber, Fast approximation techniques and geometric embedding problems. Theoretical Computer Science, 106 (1992), pp. 265--281.
  8. N.H. Bshouty, Y. Mansour, B. Schieber and P. Tiwari, Fast exponentiation using the truncation operation. Computational Complexity, 2 (1992), pp. 244--255.
  9. O. Berkman, B. Schieber and U. Vishkin, Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms, 14 (1993), pp. 344--370.
  10. Y. Mansour, J.K. Park, B. Schieber and S. Sen, Improved selection in totally monotone arrays. International Journal of Computational Geometry and Applications, 3 (1993), pp. 115--132.
Jump to Paper No. 1 11 21 31 41
  1. A. Bar-Noy, S. Kipnis and B. Schieber, An optimal algorithm for computing census functions in message-passing systems. Parallel Processing Letters, 3 (1993), pp. 19--23.
  2. A. Fiat, Y. Rabani, Y. Ravid and B. Schieber, A deterministic O(k3)-competitive k-server algorithm for the circle. Algorithmica, 11 (1994), pp. 572--578.
  3. B. Schieber and M. Snir, Calling names on nameless networks. Information and Computation, 113 (1994), pp. 80--101.
  4. A. Aggarwal, B. Schieber and T. Tokuyama, Finding a minimum weight K-link path in graphs with Monge property and applications. Journal of Discrete and Computational Geometry, 12 (1994), pp. 263--280.
  5. A. Borodin, S. Irani, P. Raghavan and B. Schieber, Competitive paging with locality of reference. Journal of Computer and System Sciences, 50 (1995), pp. 244--258.
  6. A. Aggarwal, A. Bar-Noy, D. Kravets, S. Khuller and B. Schieber, Efficient minimum cost matching using the quadrangle inequality. Journal of Algorithms, 19 (1995), pp. 116--143.
  7. A. Bar-Noy, J. Bruck, C-T. Ho, S. Kipnis and B. Schieber, Computing global combine operations in the Multi-Port Postal Model. IEEE Trans. on Parallel and Distributed Systems, 6 (1995), pp. 896--900.
  8. A. Bar-Noy, S. Kipnis and B. Schieber, Optimal computation of census functions in the Postal Model. Discrete Applied Mathematics, 58 (1995), pp. 213--222.
  9. O. Berkman, B. Schieber and U. Vishkin, A fast parallel algorithm for finding the convex hull of a sorted point set. International Journal of Computational Geometry and Applications, 6 (1996), pp. 231--241.
  10. A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber and M. Sudan, Efficient routing and scheduling algorithms for optical networks. Journal of the ACM, 43(6) (1996), pp. 973--1001.
Jump to Paper No. 1 11 21 31 41
  1. L. Cai and B. Schieber, A linear-time algorithm for computing the intersection of all odd cycles in a graph. Discrete Applied Mathematics, 73(1) (1997), pp. 27--34.
  2. A. Blum, P. Raghavan and B. Schieber, Navigating in unfamiliar geometric terrain. SIAM Journal on Computing, 26(1) (1997), pp. 110--137.
  3. G. Barnes, J. Buss, W.L. Ruzzo and B. Schieber, A sub-linear space, polynomial time algorithm for directed s-t connectivity. To appear in SIAM Journal on Computing.
  4. A. Bar-Noy, A. Mayer, B. Schieber and M. Sudan, Guaranteeing fair service to persistent dependent tasks. To appear in SIAM Journal on Computing. Available as RC 19904, IBM T.J. Watson Research Center, Yorktown Heights (1995).
  5. A. Borodin, Y. Rabani and B. Schieber, Deterministic many-to-many hot-potato routing. To appear in IEEE Trans. on Parallel and Distributed Systems.
  6. G. Even, J. Naor, B. Schieber and M. Sudan, Approximating minimum feedback sets and multi-cuts in directed graphs. To appear in Algorithmica. Available as RC 20074, IBM T.J. Watson Research Center, Yorktown Heights (1995).
  7. A. Borodin, P. Raghavan, B. Schieber and E. Upfal, How much can hardware help routing? Submitted to Journal of the ACM, July 1994.
  8. B. Schieber, Finding a minimum weight K-link path in graphs with the concave Monge property. Submitted to Journal of Algorithms, Special Issue SODA 1995 papers, Feb. 1995 (editor Ken Clarkson).
  9. N. Bshouty, Y. Mansour, B. Schieber and P. Tiwari, A tight bound for approximating the square root. Submitted to Information Processing Letters, May 1995. June 1995.
  10. G. Even, J. Naor, B. Schieber and L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications to multicuts. Submitted to SIAM Journal on Discrete Mathematics, September 1995.
Jump to Paper No. 1 11 21 31 41
  1. G. Even, J. Naor, S. Rao and B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics. Submitted to Journal of the ACM, February 1996.
  2. A. Bar-Noy, S. Kipnis and B. Schieber, Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems. Submitted to Discrete Applied Mathematics, October 1996.
  3. G. Even, J. Naor, S. Rao and B. Schieber, Approximate Graph Partitioning Algorithms. Submitted to SIAM Journal on Computing, August 1996.
Jump to Paper No. 1 11 21 31 41

Technical reports

  1. B. Schieber and S. Moran, Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings. RC 11979, IBM T.J. Watson Research Center, Yorktown Heights (1986).
  2. N. Alon and B. Schieber, Optimal preprocessing for answering on-line product queries. TR 71/87, The Moise and Frida Eskenasy Institute of Computer Science, Tel Aviv University (1987).

CONFERENCES


Jump to Conference No. 1 11 21 31

  1. B. Schieber and S. Moran, Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings. Proc. 5th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1986), pp. 282--292.
  2. Y. Maon, B. Schieber and U. Vishkin, Parallel Ear Decomposition Search (EDS) and st-numbering in graphs. Proc. 2nd Aegean Workshop on Computing (AWOC), Lecture Notes in Computer Science 227, Springer-Verlag (1986), pp. 34--45.
  3. G.M. Landau, B. Schieber and U. Vishkin, Parallel construction of a suffix tree. Proc. 14th Int. Colloq. on Automata Lang. and Prog.(ICALP), Lecture Notes in Computer Science 267, Springer-Verlag (1987), pp. 314--325.
  4. B. Schieber and U. Vishkin, On finding lowest common ancestors: simplification and parallelization. Proc. 3rd Aegean Workshop on Computing (AWOC), Lecture Notes in Computer Science 319, Springer-Verlag (1988), pp. 111--123.
  5. Y. Afek, G.M. Landau, B. Schieber and M. Yung, The power of multimedia: combining point-to-point and multiaccess networks. Proc. 7th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1988), pp. 90--104.
  6. Y. Mansour, B. Schieber and P. Tiwari, Lower bounds for integer greatest common divisor computations. Proc. 29th Symp. on Foundations of Computer Science (FOCS) (1988), pp. 54--63.
  7. O. Berkman, D. Breslauer, Z. Galil, B. Schieber and U. Vishkin, Highly parallelizable problems. Proc. 21st ACM Symp. on Theory of Computing (STOC) (1989), pp. 301--319.
  8. Y. Mansour and B. Schieber, The intractability of bounded protocols for non-FIFO channels. Proc. 8th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1989), pp. 59--72.
  9. B. Schieber and M. Snir, Calling names on nameless networks. Proc. 8th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1989), pp. 319--328.
  10. P.K. Agarwal, A. Aggarwal, B. Aronov, S.R. Kosaraju, B. Schieber and S. Suri, Computing external-furthest neighbors for a simple polygon. Proc. 1st Canadian Conf. on Computational Geometry, 1989.
Jump to Conference No. 1 11 21 31
  1. Y. Mansour, B. Schieber and P. Tiwari, Lower bounds for computations with the floor operation. Proc. 16th Int. Colloq. on Automata Lang. and Prog. (ICALP) (1989), pp. 559--573.
  2. M.W. Bern, H.J. Karloff, P. Raghavan and B. Schieber, Fast approximation techniques and geometric embedding problems. Proc. 5th ACM Symp. on Computational Geometry (1989), pp. 292--301.
  3. S. Khuller and B. Schieber, Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs. Proc. 30th Symp. on Foundations of Computer Science (FOCS) (1989), pp. 288--293.
  4. Y. Mansour, B. Schieber and P. Tiwari, The complexity of approximating the square root. Proc. 30th Symp. on Foundations of Computer Science (FOCS) (1989), pp. 325--330.
  5. L.L. Larmore and B. Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure. Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA) (1990), pp. 503--512.
  6. A. Bar-Noy and B. Schieber, The Canadian traveller problem. Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms (SODA) (1991), pp. 261--270.
  7. A. Blum, P. Raghavan and B. Schieber, Navigating in unfamiliar geometric terrain. Proc. 23rd ACM Symp. on Theory of Computing (STOC) (1991), pp. 494--504.
  8. A. Borodin, S. Irani, P. Raghavan and B. Schieber, Competitive paging with locality of reference. Proc. 23rd ACM Symp. on Theory of Computing (STOC) (1991), pp. 249--259.
  9. Y. Mansour, J.K. Park, B. Schieber and S. Sen, Improved selection in totally monotone arrays. Proc. 11th Conf. on Foundations of Software Technology and Theoretical Computer Science (FST \& TCS), S. Biswas and K.V. Nori (Eds), Lecture Notes in Computer Science 590, Springer-Verlag (1991), pp. 347--359.
  10. D. Gusfield, G.M. Landau and B. Schieber, An efficient algorithm for Suffix-Prefix matching. Proc. Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De-Santis and U. Vaccaro (Eds), Springer-Verlag (1991), pp. 218--224.
Jump to Conference No. 1 11 21 31
  1. G. Barnes, J. Buss, W.L. Ruzzo and B. Schieber, A sub-linear space, polynomial time algorithm for directed s-t connectivity. Proc. 7th Symp. on Structure in Complexity Theory (1992), pp. 27--33.
  2. A. Aggarwal, A. Bar-Noy, D. Kravets, S. Khuller and B. Schieber, Efficient minimum cost matching using quadrangle inequality. Proc. 33rd Symp. on Foundations of Computer Science (FOCS) (1992), pp. 583--592.
  3. D. Coppersmith and B. Schieber, Lower bounds on the depth of monotone arithmetic computations. Proc. 33rd Symp. on Foundations of Computer Science (FOCS) (1992), pp. 288--295.
  4. A. Aggarwal, B. Schieber and T. Tokuyama, Finding a minimum weight K-link path in graphs with Monge property and applications. Proc. 9th ACM Symp. on Computational Geometry (1993), pp. 189--197.
  5. A. Borodin, P. Raghavan, B. Schieber and E. Upfal, How much can hardware help routing? Proc. 25th ACM Symp. on Theory of Computing (STOC) (1993), pp. 573--582.
  6. A. Bar-Noy, P. Raghavan, B. Schieber and H. Tamaki, Fast deflection routing for packets and worms. Proc. 12th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1993), pp. 75--86.
  7. A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber and M. Sudan, Efficient routing and scheduling algorithms for optical networks. Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA) (1994), pp. 412--423.
  8. A. Bar-Noy, J. Bruck, C-T. Ho, S. Kipnis and B. Schieber, Computing global combine operations in the Multi-Port Postal Model. Proc. 5th IEEE Symp. on Parallel and Distributed Processing (SPDP) (1993), pp. 336--343.
  9. A. Bar-Noy, S. Kipnis and B. Schieber, Optimal multiple message broadcasting in telephone-like communication systems. Proc. 6th IEEE Symp. on Parallel and Distributed Processing (SPDP) (1994), pp. 216--223.
  10. B. Schieber, Finding a minimum weight K-link path in graphs with the concave Monge property. Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA) (1995), pp. 405--411.
Jump to Conference No. 1 11 21 31
  1. A. Bar-Noy, A. Mayer, B. Schieber and M. Sudan, Guaranteeing fair service to persistent dependent tasks. Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA) (1995), pp. 243--252.
  2. A. Bar-Noy, R. Canetti, S. Kutten, Y. Mansour and B. Schieber, Bandwidth allocation with preemption. Proc. 27th ACM Symp. on Theory of Computing (STOC) (1995), pp. 616--625.
  3. G. Even, J. Naor, B. Schieber and M. Sudan, Approximating minimum feedback sets and multi-cuts in directed graphs. Proc. 4th MPS Conf. on Integer Prog. and Combinatorial Optimization (IPCO) (1995), pp 14--28.
  4. G. Even, J. Naor, S. Rao and B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics. Proc. 36th Symp. on Foundations of Computer Science (FOCS) (1995), pp. 62--71.
  5. G. Even, J. Naor, B. Schieber and L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications to multicuts. Proc. 4th Israeli Symp. on Theory of Computing and Systems (ISTCS) (1996), pp. 78--88.
  6. A. Aggarwal, D. Coppersmith, S. Khanna, R. Motwani and B. Schieber, The angular-metric traveling salesman problem. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms (SODA) (1997), pp. 221--229.
  7. G. Even, J. Naor, S. Rao and B. Schieber, Fast spreading metric based approximate graph partitioning algorithms. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms (SODA) (1997), pp. 639--648.
Jump to Conference No. 1 11 21 31
Baruch Schieber
sbar@watson.ibm.com



[Research home page]

[ IBM home page | Order | Search | ContactIBM | Legal ]