📄 http:^^www.cs.rochester.edu^u^joel^
字号:
Date: Thursday, 21-Nov-96 21:01:09 GMTServer: NCSA/1.3MIME-version: 1.0Content-type: text/htmlLast-modified: Tuesday, 19-Sep-95 14:08:24 GMTContent-length: 3292<HTML><HEAD><TITLE>Joel Seiferas's Public Page</TITLE></HEAD><BODY><!WA0><IMG ALIGN=TOP SRC="http://www.cs.rochester.edu/images/urcslogo.gif"><!WA1><IMG ALIGN=TOP SRC="http://www.cs.rochester.edu/u/joel/joel.gif"><P><H1>Joel I. Seiferas, URCS Faculty Member</H1><P>b. 1947. Ph.D. (1974) Massachusetts Institute of Technology. AssistantProfessor (74-79), Associate Professor (79); The Pennsylvania StateUniversity. Associate Professor (79-present), Department Chair(81-84); University of Rochester.<P>How can we characterize the structure and complexity of the range ofalgorithms that solve a fundamental computational problem? What areupper and lower bounds on the computational resources (especially timeand space) that are needed, and how do these relate to thecapabilities of the computer model being used? What are the rightarchitectures to consider, and what are the best techniques forproving such bounds? These and related questions continue to motivateJoel's interest and research in computer science.<P>Recent research has involved an information-theoretic lower-boundtechnique based on descriptional complexity and algorithmicallyincompressible data. Upper bound work has included algorithms forstring matching and text indexing, and counter-intuitive real-timesimulations of counters and multihead tapes. Recent researchsupervision and topics courses have involved circuit complexity,probabilistic automata, on-line load balancing, the geometry ofstring-edit distances, cryptography and multi-party computation, andparallel string matching.<P>Research with current students involves lower and upper bounds onredistribution cost for on-line density control, and space-efficienttechniques useful in the simulation of probabilistic automata.<P><H2>Selected Publications</H2><UL><LI> J. I. Seiferas, ``Machine-Independent Complexity'', in Jan Van Leeuwen (ed.), Handbook of Theoretical Computer Science A: Algorithms and Complexity, 163-186, Elsevier Science Publishers and The MIT Press, 1990. <LI> J. I. Seiferas and A. R. Meyer, ``Characterization of Realizable Space Complexities'', Annals of Pure and Applied Logic 73, 2 (1 June 1995), 171-190.<LI> P. F. Dietz, I. I. Macarie, and J. I. Seiferas, ``Bits and Relative Order from Residues, Space Efficiently'', Information Processing Letters 50, 3 (9 May 1994), 123-127.<LI> P. F. Dietz, J. I. Seiferas, and J. Zhang, ``A Tight Lower Bound for On-line Monotonic List Labeling'', Algorithm Theory -- SWAT '94 (Proceedings of 4th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 824, Springer-Verlag) (Aarhus, Denmark, July 7, 1994), pp. 131-142.<LI> R. Paturi, J. I. Seiferas, J. Simon, and R. Newman-Wolfe, ``Milking the Aanderaa Argument'', Information and Computation 88, 1 (September 1990), 88-104. <LI> T. Jiang, J. I. Seiferas, and P. M. B. Vitanyi, ``Two Heads are Better than Two Tapes'', Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing (Montreal, Quebec, Canada, May 25, 1994), pp. 668--675.</UL><!WA2><A HREF="http://www.cs.rochester.edu/users/faculty.html"> <!WA3><IMG ALIGN=TOP SRC="http://www.cs.rochester.edu/images/up.gif">Back to URCS Faculty directory</A><P><!WA4><A HREF="http://www.cs.rochester.edu/urcs.html"> <!WA5><IMG ALIGN=TOP SRC="http://www.cs.rochester.edu/images/home.gif">Back to URCS Home Page</A><P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -