Marc Snir

If you made any changes in Pure these will be visible here soon.

Research Output

1977

A Direct Approach to the Parallel Evaluation of Rational Expressions with a Small Number of Processors

Snir, M. & Barak, A. B., 1977, In : IEEE Transactions on Computers. C-26, 10, p. 933-937 5 p.

Research output: Contribution to journalArticle

1979

On the depth complexity of formulas

Shamir, E. & Snir, M., Dec 1 1979, In : Mathematical Systems Theory. 13, 1, p. 301-322 22 p.

Research output: Contribution to journalArticle

The covering problem of complete uniform hypergraphs

Snir, M., 1979, In : Discrete Mathematics. 27, 1, p. 103-105 3 p.

Research output: Contribution to journalArticle

1980

On the size complexity of monotone formulas

Snir, M., Jan 1 1980, Automata, Languages and Programming - 7th Colloquium. de Bakker, J. & van Leeuwen, J. (eds.). Springer-Verlag, p. 621-631 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 85 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1981

On the complexity of simplifying quadratic forms

Snir, M., Oct 13 1981, In : Information Processing Letters. 12, 5, p. 217-220 4 p.

Research output: Contribution to journalArticle

Proving lower bounds for linear decision trees

Snir, M., Jan 1 1981, Automata, Languages and Programming - 8th Colloquium. Even, S. & Kariv, O. (eds.). Springer-Verlag, p. 305-315 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 115 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1982

CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).

Perl, Y. & Snir, M., Dec 1 1982, p. 80-84. 5 p.

Research output: Contribution to conferencePaper

Comparisons between linear functions can help

Snir, M., Sep 1982, In : Theoretical Computer Science. 19, 3, p. 321-330 10 p.

Research output: Contribution to journalArticle

New york university (nyu) ultracomputer — a general-purpose parallel processor

Gottlieb, A., Grishman, R., Kruskal, C. P., Mc Auliffe, K. P., Rudolph, L. & Snir, M., Jul 30 1982, In : Proceedings of SPIE - The International Society for Optical Engineering. 298, p. 64-73 10 p.

Research output: Contribution to journalArticle

ON PARALLEL SEARCHING.

Snir, M., Dec 1 1982, Unknown Host Publication Title. ACM, p. 242-253 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

On parallel searching (extended abstract)

Snir, M., Aug 18 1982, Proceedings of the 1st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 1982. Association for Computing Machinery, p. 242-253 12 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Some Exact Complexity Results for Straight-Line Computations over Semirings

Jerrum, M. & Snir, M., Jul 1 1982, In : Journal of the ACM (JACM). 29, 3, p. 874-897 24 p.

Research output: Contribution to journalArticle

SOME RESULTS ON PACKET-SWITCHING NETWORKS FOR MULTIPROCESSING (EXTENDED ABSTRACT).

Kruskal, C. P. & Snir, M., Dec 1 1982, p. 305-310. 6 p.

Research output: Contribution to conferencePaper

The NYU Ultracomputer - Designing a mimd, shared-memory parallel machine (extended abstract)

Gottlieb, A., Grishman, R., Kruskal, C. P., McAuliffe, K. P., Rudolph, L. & Snir, M., Apr 26 1982, In : Proceedings - International Symposium on Computer Architecture. p. 27-42 16 p.

Research output: Contribution to journalConference article

1983

Circuit partitioning with size and connection constraints

Perl, Y. & Snir, M., Jan 1 1983, In : Networks. 13, 3, p. 365-375 11 p.

Research output: Contribution to journalArticle

The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer

Gottlieb, A., Grishman, R., McAuliffe, K. P., Snir, M. & Kruskal, C. P., Feb 1983, In : IEEE Transactions on Computers. C-32, 2, p. 175-189 15 p.

Research output: Contribution to journalArticle

The Performance of Multistage Interconnection Networks for Multiprocessors

Kruskal, C. P. & Snir, M., Dec 1983, In : IEEE Transactions on Computers. C-32, 12, p. 1091-1098 8 p.

Research output: Contribution to journalArticle

1984

APPLICATIONS OF RAMSEY'S THEOREM TO DECISION TREES COMPLEXITY.

Moran, S., Snir, M. & Manber, U., Dec 1 1984, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 332-337 6 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

IMPORTANCE OF BEING SQUARE.

Kruskal, C. P. & Snir, M., 1984, Conference Proceedings - Annual Symposium on Computer Architecture. IEEE, p. 91-98 8 p. (Conference Proceedings - Annual Symposium on Computer Architecture).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

ON THE DISTRIBUTION OF DELAYS IN BUFFERED MULTISTAGE INTERCONNECTION NETWORKS FOR UNIFORM AND NONUNIFORM TRAFFIC.

Kruskal, C. P., Snir, M. & Weiss, A., 1984, Proceedings of the International Conference on Parallel Processing. Keller, R. M. (ed.). IEEE, p. 215-219 5 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1985

Applications of Ramsey's Theorem to Decision Tree Complexity

Moran, S., Snir, M. & Manber, U., Oct 1 1985, In : Journal of the ACM (JACM). 32, 4, p. 938-949 12 p.

Research output: Contribution to journalArticle

Computing on an anonymous ring

Attiya, C., Snir, M. & Warmuth, M., Aug 1 1985, Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985. Strong, R. & Malcolm, M. (eds.). Association for Computing Machinery, p. 196-203 8 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

ISSUES RELATED TO MIMD SHARED-MEMORY COMPUTERS: THE NYU ULTRACOMPUTER APPROACH.

Edler, J., Gottlieb, A., Kruskal, C. P., McAuliffe, K. P., Rudolph, L., Snir, M., Teller, P. J. & Wilson, J., 1985, Conference Proceedings - Annual Symposium on Computer Architecture. IEEE, p. 126-135 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lower bounds on probabilistic linear decision trees

Snir, M., 1985, In : Theoretical Computer Science. 38, C, p. 69-82 14 p.

Research output: Contribution to journalArticle

ON PARALLEL SEARCHING.

Snir, M., Jan 1 1985, In : SIAM Journal on Computing. 14, 3, p. 688-708 21 p.

Research output: Contribution to journalArticle

POWER OF PARALLEL PREFIX.

Kruskal, C. P., Rudolph, L. & Snir, M., Dec 1 1985, Proceedings of the International Conference on Parallel Processing. DeGroot, D. (ed.). IEEE, p. 180-185 6 p. (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

VLSI COMBINING NETWORK FOR THE NYU ULTRACOMPUTER.

Dickey, S., Kenner, R., Snir, M. & Solworth, J., Dec 1 1985, Unknown Host Publication Title. IEEE, p. 110-113 4 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1986

A unified theory of interconnection network structure

Kruskal, C. P. & Snir, M., 1986, In : Theoretical Computer Science. 48, C, p. 75-94 20 p.

Research output: Contribution to journalArticle

Depth-size trade-offs for parallel prefix computation

Snir, M., Jun 1986, In : Journal of Algorithms. 7, 2, p. 185-201 17 p.

Research output: Contribution to journalArticle

DISTRIBUTION OF WAITING TIMES IN CLOCKED MULTISTAGE INTERCONNECTION NETWORKS.

Kruskal, C. P., Snir, M. & Weiss, A., Dec 1 1986, Proceedings of the International Conference on Parallel Processing. Hwang, K., Jacobs, S. M. & Swartzlander, E. E. (eds.). IEEE, p. 12-19 8 p. (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

EFFICIENT PARALLEL ALGORITHMS FOR GRAPH PROBLEMS.

Kruskal, C. P., Rudolph, L. & Snir, M., Dec 1 1986, Proceedings of the International Conference on Parallel Processing. Hwang, K., Jacobs, S. M. & Swartzlander, E. E. (eds.). IEEE, p. 869-876 8 p. (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Efficient synchronization on multiprocessors with shared memory

Kruskal, C. P., Rudolph, L. & Snir, M., Nov 1 1986, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 218-228 11 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Exact balancing is not always good

Snir, M., Jan 18 1986, In : Information Processing Letters. 22, 2, p. 97-102 6 p.

Research output: Contribution to journalArticle

1987

HIERARCHICAL MEMORY WITH BLOCK TRANSFER.

Aggarwal, A., Chandra, A. K. & Snir, M., Jan 1 1987, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 204-216 13 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

MODEL FOR HIERARCHICAL MEMORY.

Aggarwal, A., Alpern, B., Chandra, A. K. & Snir, M., Dec 1 1987, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 305-314 10 p.

Research output: Contribution to journalConference article

OPTIMAL INTERCONNECTION NETWORKS FOR PARALLEL PROCESSORS: THE IMPORTANCE OF BEING SQUARE.

Kruskal, C. P. & Snir, M., 1987, Unknown Host Publication Title. p. 91-113 23 p.

Research output: Chapter in Book/Report/Conference proceedingChapter

1988

Better computing on the anonymous ring: Extended Abstract

Attiya, H. & Snir, M., Jan 1 1988, VLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings. Reif, J. H. (ed.). Springer-Verlag, p. 329-338 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 319 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Computing on an Anonymous Ring

Attiya, H., Snir, M. & Warmuth, M. K., Oct 1 1988, In : Journal of the ACM (JACM). 35, 4, p. 845-875 31 p.

Research output: Contribution to journalArticle

Efficient and Correct Execution of Parallel Programs that Share Memory

Shasha, D. & Snir, M., Apr 1 1988, In : ACM Transactions on Programming Languages and Systems (TOPLAS). 10, 2, p. 282-312 31 p.

Research output: Contribution to journalArticle

Efficient synchronization of multiprocessors with shared memory

Kruskal, C. P., Rudolph, L. & Snir, M., Oct 1 1988, In : ACM Transactions on Programming Languages and Systems (TOPLAS). 10, 4, p. 579-601 23 p.

Research output: Contribution to journalArticle

The Distribution of Waiting Times in Clocked Multistage Interconnection Networks

Kruskal, C. P., Snir, M. & Weiss, A., Nov 1988, In : IEEE Transactions on Computers. 37, 11, p. 1337-1352 16 p.

Research output: Contribution to journalArticle

TLB CONSISTENCY ON HIGHLY-PARALLEL SHARED-MEMORY MULTIPROCESSORS.

Teller, P. J., Kenner, R. & Snir, M., 1988, Proceedings of the Hawaii International Conference on System Science. IEEE, p. 184-193 10 p. (Proceedings of the Hawaii International Conference on System Science).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1989

Calling names on nameless networks

Schieber, B. & Snir, M., Dec 1 1989, Proc Eighth ACM Symp Princ Distrib Comput. Publ by ACM, p. 319-328 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Cost-bandwidth tradeoffs for communication networks

Kruskal, C. P. & Snir, M., Mar 1 1989, Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989. Leighton, F. T. (ed.). Association for Computing Machinery, Inc, p. 32-41 10 p. (Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Memory versus randomization in on-line algorithms: Extended abstract

Raghavan, P. & Snir, M., Jan 1 1989, Automata, Languages and Programming - 16th International Colloquium, Proceedings. Dezani-Ciancaglini, M., Della Rocca, S. R. & Ausiello, G. (eds.). Springer-Verlag, p. 687-703 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 372 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

On communication latency in PRAM computations

Aggarwal, A., Chandra, A. K. & Snir, M., Mar 1 1989, Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989. Leighton, F. T. (ed.). Association for Computing Machinery, Inc, p. 11-21 11 p. (Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Techniques for parallel manipulation of sparse matrices

Kruskal, C. P., Rudolph, L. & Snir, M., May 7 1989, In : Theoretical Computer Science. 64, 2, p. 135-157 23 p.

Research output: Contribution to journalArticle

1990

A complexity theory of efficient parallel algorithms

Kruskal, C. P., Rudolph, L. & Snir, M., Mar 13 1990, In : Theoretical Computer Science. 71, 1, p. 95-132 38 p.

Research output: Contribution to journalArticle

Communication complexity of PRAMs

Aggarwal, A., Chandra, A. K. & Snir, M., Mar 13 1990, In : Theoretical Computer Science. 71, 1, p. 3-28 26 p.

Research output: Contribution to journalArticle

Efficient parallel algorithms for graph problems

Kruskal, C. P., Rudolph, L. & Snir, M., Mar 1 1990, In : Algorithmica. 5, 1, p. 43-64 22 p.

Research output: Contribution to journalArticle