### Today's Editor:

- Cleve Moler
- The MathWorks, Inc.
- moler@mathworks.com

- Change of Address for Bert Pohl
- Direct Poisson Solvers / Rapid Elliptic Solvers
- New Computational Science & Engineering Degree at Rice University
- Computational Problems in Liquid Crystals
- ICBGM'93: International Conference on Bond Graph Modeling
- Conference on Large Scale Optimization
- Dundee Biennial Conference 1993
- Householder Fellowship at ORNL
- Postdoctoral Position at SUNY Stony Brook
- Position at University of Waterloo
- Chairperson Position at West Virginia
- Contents: SIAM Computing

-------------------------------------------------------

From: Bert Pohl <bp@maths.uq.oz.au>

Date: Tue, 27 Oct 92 10:10:11 EST

**Subject: Change of Address for Bert Pohl**

My new address is:

Bert Pohl

Department of Mathematics

University of Queensland

St. Lucia

Brisbane, 4072

Australia

Tel.: ++61 - 7 - 365 3487

Fax.: ++61 - 7 - 870 2272

------------------------------

From: Atul Chhabra <atul@nynexst.com>

Date: Sat, 31 Oct 92 14:47:05 EST

**Subject: Direct Poisson Solvers / Rapid Elliptic Solvers**

In 1975, Bank and Rose [1] proposed an O(N*N) method for solving Poisson or

Helmholtz equations on a two dimensional square grid. They showed that this

mathod was unstable with respect to round off errors and therefore it could

not be used in practice. The well known Poisson sovlers that work are the

O(N log N) cyclic reduction method of Buneman [2], the O(N log N) cyclic

reduction or Fourier analysis methods of Buzbee, Golub, and Nielson [3] and

the O(N log log N) Fourier analysis and cylic reduction method of Swarztrauber

[4]. These methods are also applicable to separable second order linear

elliptic partial differential equations.

I have two questions:

1. Has more work been done since 1975 on the O(N*N) direct Poisson solver [1]

to make it numerically stable? Or have other O(N*N) methods been proposed

since?

2. Concus and Golub [5], in 1973, proposed using the direct solvers for

iteratively solving nonseparable elliptic equations. However, in order to

converge rapidly, this method required the coefficient to vary smoothly

and to satisfy

coeff_max - coeff_min

----------------------------------------------- << 1.

2 * PoissonEigenval_min + coeff_max + coeff_min

I have an application where coeff_max is of the order of 10^4, coeff_min

is zero, and the minimum eigenvalue of the discrete Poisson operator is

close to zero. Therefore, using the Concus and Golub method [5] results in

very very slow convergence.

Has this kind of problem been addressed by direct solvers? Has there been

any recent work on solving nonseparable elliptic equations using direct

Poisson/Helmholtz solvers? Of course, I know of multigrid methods,

conjugate gradient methods, and Chebyshev acceleration? I am looking for

direct or almost direct methods for nonseparable equations.

[1] R.E. Bank and D.J. Rose, "An O(N*N) method for solving constant coefficient

boundary value problems in two dimensions," SIAM Journal of Numerical

Analysis, 12:529-540, 1975.

[2] O. Buneman, "A compact non-iterative poisson solver," Technical Report 294,

Stanford University Institute for Plasma Research, Stanford, CA, 1969.

[3] B.L. Buzbee, G.H. Golub, and C.W. Nielson, "On direct methods for solving

Poission's equation," SIAM Journal of Numerical Analysis, 7(4):627-656,

1970.

[4] P.A. Swarztrauber, "The methods of cyclic reduction, Fourier analysis and

the FACR algorithm for the discrete solution of Poisson's equation on a

rectangle," SIAM Review, 19(3):490-501, 1977.

[5] P. Concus and G.H. Golub, "Use of fast direct methods for the efficient

numerical solution of nonseparable elliptic equations," SIAM Journal of

Numerical Analysis, 10(6):1103-1120, 1973.

Thanks in advance for any help.

--Atul

Atul K. Chhabra Phone: (914)644-2786

Member of Technical Staff Fax: (914)644-2404

NYNEX Science & Technology Internet: atul@nynexst.com

500 Westchester Avenue

White Plains, NY 10604

------------------------------

From: Dan Sorensen <sorensen@masc22.rice.edu>

Date: Mon, 26 Oct 92 13:15:22 CST

**Subject: New Computational Science & Engineering Degree at Rice University**

THE COMPUTATIONAL SCIENCE AND ENGINEERING DEGREE PROGRAM AT RICE

UNIVERSITY, HOUSTON , TEXAS

Rice University announces the Computational Science And Engineering (CSE)

Graduate Degree Program, designed to provide interdisciplinary research and

education in the area of scientific computing.

THE MASTER'S DEGREE PROGRAM

The intent of the master's degree program is to graduate professional

experts in scientific computing who will be able to work as technical

specialists within an interdisciplinary research team. Degree candidates

will be offered: training in the use of state-of-the-art numerical methods,

high performance computer architectures, and software development tools for

parallel and vector computers; application of these techniques to at least

one scientific or engineering area; a curriculum consisting of topics from

computer science, computational and applied mathematics, and a selected

application area; and hands-on experience with leading-edge parallel

supercomputers.

THE PH.D. DEGREE PROGRAM

The Ph.D. degree program offers the same interdisciplinary approach as the

master's degree program but with greater specialization. An original thesis,

in addition to the completion of either an advanced schedule of

courses or a computational project in an application area other than

computer science or computational and applied mathematics, are required for

the Ph.D. in this program.

PARTICIPATING DEPARTMENTS

Biochemistry and Cell Biology (expected)

Chemical Engineering

Computational and Applied Mathematics

Computer Science

Electrical and Computer Engineering

Statistics (expected)

ADMISSION

Students must be admitted into one of the academic departments listed above

to be considered for participation in the CSE graduate degree program. The

student participates as a graduate student within that department in every

way except that the curriculum and examination requirements will be set by

guidelines for the CSE graduate degree program. All applications must be

received by January 15th.

STUDENT SUPPORT

First-year funding for Ph.D. candidates is provided by fellowships from the

Center for Research on Parallel Computation, a National Science Foundation

Science and Technology Center at Rice. After the first year, support for

Ph.D. students is provided by research fellowships.

FACILITIES

Students participating in the CSE graduate degree program will have access

to several advanced computational resources: Intel Paragon, Delta, and

iPSC/860; Cray machines; and Thinking Machines CM-2 and CM-5.

ADDITIONAL INFORMATION

To request information and application materials for the new CSE Graduate

Degree Program, please contact:

Theresa Chatman

Computational Science and Engineering Graduate Degree Program

Center for Research on Parallel Computation

Rice University

6100 South Main Street

Houston, TX 77005

Theresa Chatman

Phone: 713-285-5180

Electronic mail: tlc@rice.edu

------------------------------

From: E.C. Gartland <gartland@mcs.kent.edu>

Date: Mon, 26 Oct 92 11:33:33 EST

**Subject: Computational Problems in Liquid Crystals**

FINAL ANNOUNCEMENT

A Conference on

COMPUTATIONAL PROBLEMS IN LIQUID CRYSTALS

November 13-14, 1992

Kent State University

Kent, Ohio

Preliminary Schedule

Friday (Nov 13):

AM: Invited Talks - Dan Frenkel (Inst. for Atomic & Mol. Phys.)

Mitch Luskin (Univ. of Minnesota)

Solicited Talks - Robert Cohen (Univ. of North Carolina)

Robert Guenette (Univ. of Laval)

Tim Sluckin (Univ. of Southampton)

PM: Invited Talks - Frank Leslie (Univ. of Strathclyde)

Richard Varga (Kent State Univ.)

Solicited Talks - Carme Calderer (Penn State Univ.)

Epifanio Virga (Univ. di Pisa)

Axel Kilian (Tech. Univ. Berlin)

Saturday (Nov 14):

AM: Invited Talks - Ole Mouritsen (Tech. Univ. of Denmark)

David Kinderlehrer (Carnegie Mellon Univ.)

Solicited Talks - Claudio Zannoni (Univ. di Bologna)

Phil Taylor (Case Western Reserve Univ.)

Chuck Gartland (Kent State Univ.)

PM: Invited Talks - Greg Ryskin (Northwestern Univ.)

Maurice Kleman (Univ. de Paris-Sud)

Solicited Talks - Slobodan Zumer (Univ. of Ljubljana)

Dwight Berreman (AT&T Bell Labs (retired))

Tom Lubensky (Univ. of Pennsylvania)

Birger Bergersen (Univ. of British Columbia)

The Conference is interdisciplinary in nature, bringing together

computational and theoretical physicists, chemists and engineers, and

applied and numerical analysts, to explore some of the many challenging

computational problems in the area of liquid crystals. In addition to

the talks above, there will be a session of contributed posters.

The Conference is being co-sponsored by the Department of Mathematics

and Computer Science and the Liquid Crystal Institute at Kent State

University. Sources of primary support are the Institute for

Mathematics and its Applications (IMA) at the University of Minnesota

and the NSF Science and Technology Center for ``Advanced Liquid

Crystalline Optical Materials'' (ALCOM), a consortium of Kent State

University, Case Western Reserve Univerity, and the University of Akron.

The Conference is being organized in cooperation with the Society for

Industrial and Applied Mathematics (SIAM).

For further information, contact the Conference Secretary:

Brenda L. Buck Phone: 216-672-2654

Liquid Crystal Institute FAX: 216-672-2796

Kent State University e-mail: brenda@whiterabbit.kent.edu

Kent, OH 44242

Organizing Committee

E.C. Gartland, Jr (Co-chair) M.B. Luskin P. Palffy-Muhoray (Co-chair)

Dept of Math & CS School of Math Liq Cryst Inst & Dept of Phys

Kent State Univ Univ of Minn Kent State Univ

------------------------------

From: Francois Cellier <cellier@hermes.ece.arizona.edu>

Date: Mon, 26 Oct 1992 13:34:19 -0700 (MST)

**Subject: ICBGM'93: International Conference on Bond Graph Modeling**

INTERNATIONAL CONFERENCE ON BOND GRAPH MODELING (ICBGM'93)

Part of the 1993 Western Simulation Multiconference

Sponsored by the SCS

January 18-20, 1993

Hyatt Regency, La Jolla, California, USA

The International Conference on Bond Graph Modeling (ICBGM) is a new forum for

knowledge exchange among Bond Graphers and for promoting the Bond Graph

methodology to the modeling world through its Proceedings. We are very proud

of the enthusiastic response received to our Call for Papers. We are happy

that a large majority of today's Bond Graph experts have agreed to support this

conference either by serving on its Program Committee or by sending

contributions. We are particularly proud that the spiritual father of the

Bond Graph methodology, Hank Paynter, agreed to speak to us, and also to write

a preface to the Proceedings of this conference.

Bond Graphs, as a methodology for modeling lumped continuous-time physical

processes, have been around for more than 30 years. Bond Graphs describe the

power flow through a physical system. They preserve the topological structure

of the processes they describe, i.e., they are object-oriented, yet allow to

quickly examine the computational structure as well through the introduction of

so-called causality strokes.

Bond graphs, as an educational tool for teaching students how to make good

models, have been very successful. As teachers, we have been able to observe

that students grasp the concepts behind Bond Graph modeling quickly, and they

love it. Students who use Bond Graphs as a tool for designing their models are

much more likely to come up with correct answers than students who don't.

Bond graphs, as a research tool in the principles of modeling, have been

fashionable all along. Hundreds, maybe thousands, of archival research papers

on various aspects of Bond Graph modeling have been published over the years.

Bond Graphs have been understood not only as a tool for deriving simulation

models, but also as a means to concisely and unambiguously describe physical

phenomena. In our view, Bond Graph modelers are simply better physicists.

Bond graphs, as an engineering tool for modeling real-life physical processes

were however slow in coming. Most of the early Bond Graph software tools did

not allow to model nonlinear phenomena at all, others did not lend themselves

to a convenient description of such phenomena; and yet, our real world is

utterly nonlinear indeed. Few of the software tools available did allow the

user to describe subsystems in a modular fashion, enabling him to hierarchically

structure his models; and yet, it is quite unrealistic to assume that engineers

will be willing to describe complex processes monolithically at a single

modeling layer. Such models would be extremely difficult to debug and maintain.

However, Bond Graph software has meanwhile matured to a state where complex

engineering processes can indeed be described elegantly and efficiently as

demonstrated by many of the application-oriented papers presented at this

conference.

If you wish to received an E_Mail copy of the Preliminary Program of this

conference, please, send a request via E_Mail to:

Cellier@ECE.Arizona.Edu

or: na.Cellier@na-net.ORNL.Gov

General Chairman Program Chairman

Jose J. Granda Francois E. Cellier

Department of Mechanical Engineering Dept. of Electr. and Computer Engr.

California State University, Sacramento University of Arizona

Sacramento, Calif. 95819 Tucson, Ariz. 85721

Phone: (916) 278-5711 Phone: (602) 621-6192

FAX: (916) 278-5949 FAX: (602) 621-8076

EMail: GrandaJJ@ECS.CSUS.Edu EMail: Cellier@ECE.Arizona.Edu

International Program Committee

Jan Broenink Tech. University of Twente Netherlands

Peter Breedveld Tech. University of Twente Netherlands

Marisol Delgado Universidad Simon Bolivar, Caracas Venezuela

Hallvard Engja Norwegian Institute of Technology, Trondheim Norway

Peter Gawthrop University of Glasgow, Scottland United Kingdom

Dean Karnopp University of California, Davis U.S.A.

Lennart Ljung Linkoping University Sweden

Francis Lorenz Lorenz Consulting, Liege Belgium

Donald Margolis University of California, Davis U.S.A.

Fernando Mejia Universidad Nacional de Colombia, Bogota Colombia

Henry Paynter formerly at M.I.T. U.S.A.

Jean Thoma Thoma Consulting, Zug Switzerland

Tong Zhou California State University, Sacramento U.S.A.

------------------------------

From: Bill Hager <hager@math.ufl.edu>

Date: Thu, 29 Oct 92 16:34:08 EST

**Subject: Conference on Large Scale Optimization**

Conference on Large Scale Optimization

University of Florida, Gainesville, Florida

February 15-17, 1993

The conference will bring together researchers who are

working on many different aspects of large scale optimiza-

tion: algorithms, applications and software. Currently, the

list of invited speakers includes the following people:

Dimitri Bertsekas John Birge Christian Bischof Andrew Conn

Jann Cook Thomas Coleman George Dantzig Renato DeLeone

Joseph Dunn Chris Floudas Anders Forsgren Masao Fukushima

David Gay Philip Gill Jean-Louis Goffin Donald Goldfarb

Masao Iri Narendra Karmarkar C.T. Kelley Hiroshi Konno

Leon Lasdon S. Lawphongpanich P. O. Lindberg Robert Meyer

Jorge More' Walter Murray Anna Nagurney George Nemhauser

James Orlin Michael Overton P. Panagiotopoulos Jong-Shi Pang

Roman Polyak Aubrey Poore Mauricio Rescende K. Ramakrishnan

J. B. Rosen Ekkehard Sachs Michael Saunders Robert Schnabel

David Shanno Richard Tapia Andre Tits Philippe Toint

Yinyu Ye Stavros Zenios

Although only invited talks will be presented at the confer-

ence, everyone is welcome to attend the conference. More-

over, it is anticipated that some funds will be available

for the support of graduate students, and to support the

participation of women, minorities, and persons with disa-

bilities; please contact the organizers. To obtain the

latest information concerning the conference, send an email

message to "coap@math.ufl.edu" and in the body of the email

message, put the phrase "send meeting". The contact people

for the conference are Bill Hager (fax: 904-392-6254), Don

Hearn (email: hearn@ise.ufl.edu), and Panos Pardalos (phone:

904-392-9011).

------------------------------

From: D. F. Griffiths <dfg@mcs.dundee.ac.uk>

Date: Sat, 31 Oct 92 12:26:50 GMT

**Subject: Dundee Biennial Conference 1993**

15th

BIENNIAL CONFERENCE

ON

NUMERICAL ANALYSIS

UNIVERSITY OF DUNDEE, SCOTLAND, UK

29th June - 2nd July 1993

The A R Mitchell lecture will this year be given by

M J D Powell (Cambridge).

Other Principal Speakers will include

J W Barrett I S Duff C M Elliott

P Gill D J Higham N K Nichols

P Townsend J M Sanz-Serna M N Spijker

G W Stewart A M Stuart R Temam

M J Todd

A limited number of submitted papers will be presented. Full details

of submission dates, conference fees, etc. will be available towards

the end of 1992 and may be obtained by writing to either

Dr D F Griffiths or Professor G A Watson:

The Organizing Secretaries

Biennial Conference on Numerical Analysis

Department of Mathematics and Computer Science

The University

Dundee, DD1 4HN

Scotland, UK

Tel: (0382) 23181 ext 4467/4474

FAX: (0382) 201 604

e-mail: dfg@uk.ac.dund.mcs

or: na.griffiths@na-net.ornl.gov

David F Griffiths Tel: (0382) 23181 EXT 4467

Dept of Maths & Computer Science FAX: (0382) 201 604

The University

Dundee DD1 4HN email: dfg@uk.ac.dund.mcs

Scotland, UK na.griffiths@na-net.ornl.gov

------------------------------

From: Richard Sincovec <sincovec@sirius.EPM.ORNL.GOV>

Date: Fri, 30 Oct 92 14:37:27 -0500

**Subject: Householder Fellowship at ORNL**

HOUSEHOLDER FELLOWSHIP IN SCIENTIFIC COMPUTING

Mathematical Sciences Section

Oak Ridge National Laboratory

The Mathematical Sciences Section of Oak Ridge National Laboratory invites

outstanding candidates to apply for the 1993 Alston S. Householder

Fellowship in Scientific Computing.

Alston S. Householder was the organizer and founding Director of the

Mathematics Division (precursor of the current Mathematical Sciences

Section) at Oak Ridge National Laboratory (ORNL). In recognition of the

seminal research contributions of Dr. Householder to the fields of

numerical analysis and scientific computing, a distinguished postdoctoral

fellowship program has been established at ORNL and named in his honor.

The Householder Fellowship is supported by the Applied Mathematical

Sciences Subprogram of the U.S. Department of Energy.

The purposes of the Householder Fellowship are to promote innovative

research in scientific computing on advanced computer architectures and to

facilitate technology transfer from the laboratory research environment to

industry and academia through advanced training of new computational

scientists. The Householder Fellowship is normally for a term of two

years. Benefits of the Fellowship include a competitive salary, fringe

benefits, travel opportunities, access to state-of-the-art computational

facilities (including both parallel architectures and high-performance

personal workstations), and collaborative research opportunities in a very

active research program in advanced scientific computing. Competition for

the appointment is open to U.S. citizens and permanent residents.

Applicants should have completed a doctoral degree in computer science,

mathematics, or statistics within three years prior to the appointment and

have a strong background and research interest in large-scale scientific

computing.

ORNL's Mathematical Sciences Section has research programs in

Computational Mathematics, Computer Performance Characterization, Applied

Analysis, Global Climate Modeling, and Computational Statistics. The

precise research emphasis of the Householder Fellow would necessarily

depend to a great degree on the research interests of the selected Fellow.

Areas of particular interest at ORNL, and in which applicants would be

especially encouraged, include: computational linear algebra,

parallel algorithms for partial differential equations including fluid

flow through porous media, tools for the development and analysis of

parallel algorithms, computational statistics, scientific visualization,

and "grand challenges" in computational science.

Applicants should send a resume, statement of research goals, and three

letters of recommendation to Carl Ludemann, PhD Employment, Oak Ridge

National Laboratory, P.O. Box 2008, Oak Ridge, TN 37831-6216, marked

"ATTN: Householder Fellowship." The deadline for applying is

January 13, 1993. Finalists will be invited to visit ORNL in

February 1993, and the selection committee's decision on the winning

candidate will be announced in March 1993. The fellowship will

commence in 1993.

For further information, contact Richard F. Sincovec by phone at

615-574-3125 or by electronic mail at sincovecrf@ornl.gov.

------------------------------

From: John Grove <grove@ams.sunysb.edu>

Date: Mon, 26 Oct 92 07:56:15 EST

**Subject: Postdoctoral Position at SUNY Stony Brook**

POSTDOCTORAL POSITION IN APPLIED MATHEMATICS

UNIVERSITY AT STONY BROOK

Department of Applied Mathematics and Statistics

The Department of Applied Mathematics and Statistics at the University

at Stony Brook expects to have one or more postdoctoral positions

available for the academic year of 1993/94. We are seeking qualified

applicants in any of the following fields; computational fluid

dynamics, parallel computing, hyperbolic conservation laws, flows in

elastic and plastic media, or flows in porous media. We are

particularly interested in candidates who will pursue manufacturing and

industrial applications of these areas.

A vita, a brief description of research interests, and at least three

letters of recommendation and any supporting materials should be sent to

Prof. James Glimm

Chair, Department of Applied Mathematics and Statistics

University at Stony Brook

Stony Brook, NY 11794-3600.

Applications in the form of plain TeX or LaTeX files can be sent via

electronic mail to

glimm@ams.sunysb.edu.

Hiring decisions are expected in January or February of 1993, although

all applications received before the position is filled will be

considered. The University at Stony Brook is an Equal Opportunity

Employer. We especially solicit applications by women and minorities.

------------------------------

From: Wei Pai Tang <wptang@lady.uwaterloo.ca>

Date: Mon, 26 Oct 1992 10:15:37 -0400

**Subject: Position at University of Waterloo**

UNIVERSITY OF WATERLOO

Department of Computer Science

The University of Waterloo invites applications for a one-year

definite term lecturing position in Computer Science with possi-

bility of renewal. The Department is looking for candidates in

numerical analysis who will participate in teaching courses

related to scientific computation at the intermediate and

advanced undergraduate level. Evidence of teaching skills is

required, and a Ph.D. in Computer Science or equivalent is an

asset. Candidates can expect to be appointed at the rank of lec-

turer or assistant professor, depending on qualifications.

Effective date of appointment: January or May 1993.

The Department of Computer Science comprises over 40 full-time

faculty members engaged in research and teaching covering a broad

spectrum. The Department and its research laboratories are

housed in the new 300,000 sq. ft. William G. Davis Computer

Research Centre. The Department is a key participant in ITRC:

Information Technology Research Centre (a Centre of Excellence

funded by the government of the Province of Ontario) that sup-

ports basic and applied research in information technology.

Applications should include a curriculum vitae and the names of

three references and should be directed to the chair: Professor

Frank Tompa, Department of Computer Science, University of

Waterloo, Waterloo, Ontario, Canada N2L 3G1; fwtompa@uwaterloo.ca

In accordance with Canadian Immigration requirements, this adver-

tisement is directed to Canadian Citizens and Permanent

Residents. The University of Waterloo encourages applications

from qualified women and men, members of visible minorities,

native peoples, and persons with disabilities.

This appointment is subject to the availability of funds.

October 1992

------------------------------

From: Ian Christie <U0ACB@WVNVM.WVNET.EDU>

Date: Wednesday, 28 Oct 1992 15:17:52 EST

**Subject: Chairperson Position at West Virginia**

Chairperson

Department of Mathematics

West Virginia University

Applications and nominations are invited for the position of

Chairperson. The position requires a Ph.D. in mathematics or its equivalent,

administrative experience, and research credentials sufficient to justify a

tenured appointment at the Associate Professor or Professor level. It is

expected that the successful applicant will continue his/her research

program while serving as chairperson. The Department is searching for a

person with a desire for administrative responsibility who will continue to

strengthen the Department's research program while maintaining a substantial

commitment to quality teaching.

The Department consists of 32 faculty, 5 support staff, and 25 graduate

teaching assistants, and offers the B.A., M.S., and a newly established

Ph.D. degree. The Department is located in newly refurbished facilities that

include its own departmental research library, a mathematics learning center

with CAI capacity, and fully integrated computer offices, classrooms, and

computer laboratories. Faculty have direct access to the University's

mainframe computer facilities and to Internet. The Department has faculty

active in various areas of pure and applied mathematics and in mathematics

education. West Virginia University has an enrollment of 22,500. Morgantown

is a culturally diverse college community with a population of about 40,000,

and is located on the Monongahela River, 70 miles south of Pittsburgh and

200 miles west of Washington D.C.

Applicants should provide a vita and the names of five references.

Applications and inquiries should be sent to Dr. Bernard Cooper, Benedum

Professor of Physics, Chair of the Search Committee, 201 Woodburn Hall, West

Virginia University, PO BOX 6286, MORGANTOWN WV 26506-6286. Screening of

applicants will begin on January 15, 1993 and will continue until a

successful candidate is chosen.

WVU is an equal opportunity/affirmative action/Title IX employer.

------------------------------

From: SIAM <norris@siam.org>

Date: Mon, 26 Oct 92 15:29:04 EST

**Subject: Contents: SIAM Computing**

CONTENTS

SIAM Journal on Computing

February 1993 Volume 22, Number 1

Implicit O(1) Probe Search

Amos Fiat and Moni Naor

Maintaining the 3-Edg

On the Boundedness of Constant-Time-Maintainable Database

Schemes

Hctor J. Hern ndez and Ke Wang

Tight Worst-Case Performance Bounds for Next-k-Fit Bin

Packing

Weizhen Mao

A Note on the Complexity of a Simple Transportation

Problem

Greg N. Frederickson

A Lower Bound on the Size of Shellsort Sorting Networks

Robert Cypher

A Note on Poset Geometries

Joel Friedman

An O(n) Algorithm for Determining the Subregion-Tree

Representation of a Rectangular Dissection

Sukhamay Kundu

Tally Versions of the Savitch and Immerman--Szelepcsenyi

Theorems for Sublogarithmic Space

Viliam Geffert

NV-Sequentiality: A Decidable Condition for Call-by-Need

Computations in Term-Rewriting Systems

Michio Oyamaguchi

ASPACE(o(log log n)) Is Regular

Kazuo Iwama

The Complexity of Malign Measures

Peter Bro Miltersen

Scan-First Search and Sparse Certificates: An Improved

Parallel Algorithm for k-Vertex Connectivity

Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna

Thurimella

Decomposing Finite-Valued Transducers and Deciding Their

Equivalence

Andreas Weber

One More Occurrence of Variables Makes Satisfiability

Jump from Trivial to NP-Complete

Jan Kratochv!l, Petr Savicky, and Zsolt Tuza

Rounds in Communication Complexity Revisited

Noam Nisan and Avi Wigderson

------------------------------

End of NA Digest

**************************

-------