✦ LIBER ✦

GUEST EDITORS' FOREWORD

✍ Scribed by Pankaj K. Agarwal; Stephen Cook

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 33 KB
Volume: 58
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1999.1631

No coin nor oath required. For personal study only.

✦ Synopsis

Beals gives a polynomial time decision procedure for an alternative proved by Tits: Given a finitely generated linear group, determine whether it contains a nonabelian free group or has a solvable subgroup of finite index.

Cai and Sivakumar resolve a conjecture of Hartmanis: If there exists a sparse hard set for P under logspace many one reductions, then P=LOGSPACE.

Dey and Guha present an optimal algorithm to decide whether two triangulated 2-manifolds are homotopic, i.e., whether one can be continuously transformed to the other.

Haken and Cook prove an exponential lower bound on the size of monotone arithmetic circuits that solve an NP problem related to clique detection.

Naor and Reingold describe a new cryptographic primitive called pseudorandom synthesizer, which is essential for encryption and authentication, and they use it to obtain a parallel construction (in NC 2 ) of a pseudo-random function.

Saks and Zhou prove that any language that can be recognized by a randomized algorithm that runs in space O(S) and always terminates can be recognized by a deterministic algorithm running in space O(S 3Â2 ), thus beating the previously known bound of O(S 2 ).

We thank the authors for agreeing to submit their papers to this special issue and the referees for their hard work in reviewing the papers.

📜 SIMILAR VOLUMES

Guest editors’ foreword

✍ M. L. Martin; G. J. Martin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 59 KB

## Guest EditorsÏ Foreword The "Third International Conference on the Applications of Magnetic Resonance to Food ScienceÏ which took place in Nantes in September 1996 has been the main stimulation for this Special Issue of Magnetic Resonance in Chemistry. Most papers in this issue describe origina

GUEST EDITORS' FOREWORD

✍ Yannis Ioannidis; Christos Papadimitriou 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 30 KB

call for papers attracted 116 submissions. The nine papers in this special issue were selected from the thirty-two papers presented in Philadelphia. Their authors were invited to submit more complete and revised versions for this issue for a round of careful refereeing. The paper titled ''Tracking

GUEST EDITORS' FOREWORD

✍ Richard Beigel; Roberto Tamassia 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 148 KB

The authors of these four papers were invited to submit finished versions of their conference extended abstracts, which were then refereed according to the usual standards of the Journal of Computer and System Sciences. We thank the authors for contributing their papers to this special issue, the re

GUEST EDITORS' FOREWORD

✍ Joan Feigenbaum; Alan Selman 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 31 KB

The program committee invited submissions for the special issue that, individually, are high quality and that, collectively, represent the breadth, depth, and vitality that characterize computational complexity as a field. All submissions went through the standard Journal of Computer and System Scie

Guest Editors' Foreword

✍ Julio C. Facelli; Robin K. Harris; Anita M. Orendt; Kurt W. Zilm 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 43 KB

Guest editors' foreword: desertification

✍ J. Sevink; A. C. Imeson 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 53 KB

## FOREWORD: DESERTIFICATION With deserti®cation now being acknowledged as a major environmental problem, it seemed an appropriate time for the Study Group on Erosion and Deserti®cation in Mediterranean Regions (MED) and the Commission on Geomorphological Response to Environmental Change (GERTEC)