Journal of the ACM, Volume 50, 2003

Volume 50, Number 1, January 2003

• Joseph Y. Halpern:
  JACM's 50th anniversary. 3-7
  
• JACM editors-in-chief. 9
  
• Franz L. Alt:
  Journal of the ACM - the beginnings. 10-11
  
• Mario L. Juncosa:
  Transitions 1959-1964. 12-13
  
• C. C. Gotlieb:
  A Golden Age for JACM. 14
  
• Raymond E. Miller:
  JACM 1973-1975. 15
  
• Edward G. Coffman Jr.:
  JACM 1976-1979. 16
  
• Michael J. Fischer:
  JACM 1983-1986. 17
  
• Daniel J. Rosenkrantz:
  JACM 1986-1990. 18
  
• Frank Thomson Leighton:
  JACM 1991-1997. 19
  
• Mark Mandelbaum:
  A report from Headquarters. 21-23
  
• Frederick P. Brooks Jr.:
  Three great challenges for half-century-old computer science. 25-26
  
• Stephen A. Cook:
  The importance of the P versus NP question. 27-29
  
• Fernando J. Corbató:
  On computer system challenges. 30-31
  
• Edward A. Feigenbaum:
  Some challenges and grand challenges for computational intelligence. 32-40
  
• Jim Gray:
  What next?: A dozen information-technology research goals. 41-57
  
• Juris Hartmanis:
  Separation of complexity classes. 58-62
  
• C. A. R. Hoare:
  The verifying compiler: A grand challenge for computing research. 63-69
  
• Butler W. Lampson:
  Getting computers to understand. 70-72
  
• John McCarthy:
  Problems and projections in CS for the next 49 year. 73-79
  
• Alexander A. Razborov:
  Propositional proof complexity. 80-82
  
• Raj Reddy:
  Three open problems in AI. 83-86
  
• Peter W. Shor:
  Why haven't more quantum algorithms been found?. 87-90
  
• Richard Edwin Stearns:
  Deterministic versus nondeterministic time and lower bound problems. 91-95
  
• Leslie G. Valiant:
  Three problems in computer science. 96-99
  
• Andrew Chi-Chih Yao:
  Classical physics and the Church-Turing Thesis. 100-105
  

Volume 50, Number 2, March 2003

• Rina Dechter, Irina Rish:
  Mini-buckets: A general scheme for bounded inference. 107-153
  
• Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
  Time-space trade-off lower bounds for randomized computation of decision problems. 154-195
  
• Amit Sahai, Salil P. Vadhan:
  A complete problem for statistical zero knowledge. 196-249
  
• D. N. Jayasimha, Loren Schwiebert, D. Manivannan, Jeff A. May:
  A foundation for designing deadlock-free routing algorithms in wormhole networks. 250-275
  

Volume 50, Number 3, May 2003

• Yuanlin Zhang, Roland H. C. Yap:
  Erratum: P. van Beek and R. Dechter's theorem on constraint looseness and local consistency. 277-279
  
• Adnan Darwiche:
  A differential approach to inference in Bayesian networks. 280-305
  
• Bruce A. Reed:
  The height of a random binary search tree. 306-332
  
• Michael Drmota:
  An analytic approach to the height of binary search trees II. 333-374
  
• Gianfranco Bilardi, Keshav Pingali:
  Algorithms for computing the static single assignment form. 375-425
  

Volume 50, Number 4, July 2003

• Prabhakar Raghavan:
  Editorial: Preserving excellence through change. 427-428
  
• Manindra Agrawal, Somenath Biswas:
  Primality and identity testing via Chinese remaindering. 429-443
  
• Hagit Attiya, Arie Fouren:
  Algorithms adapting to point contention. 444-468
  
• Ning Zhong, Klaus Weihrauch:
  Computatbility theory of generalized functions. 469-505
  
• Avrim Blum, Adam Kalai, Hal Wasserman:
  Noise-tolerant learning, the parity problem, and the statistical query model. 506-519
  
• Emilio Leonardi, Marco Mellia, Fabio Neri, Marco Ajmone Marsan:
  Bounds on delays and queue lengths in input-queued cell switches. 520-550
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Minimizing flow time nonclairvoyantly. 551-567
  
• Berthold Vöcking:
  How asymmetry helps load balancing. 568-589
  

Volume 50, Number 5, September 2003

• Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
  Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. 591-640
  
• Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe:
  The geometric maximum traveling salesman problem. 641-664
  
• Wei Biao Wu, Chinya V. Ravishankar:
  The performance of difference coding for sets and relational tables. 665-693
  
• Michael Benedikt, Leonid Libkin, Thomas Schwentick, Luc Segoufin:
  Definable relations and first-order query languages over strings. 694-751
  
• Edmund M. Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, Helmut Veith:
  Counterexample-guided abstraction refinement for symbolic model checking. 752-794
  

Volume 50, Number 6, November 2003

• Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani:
  Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. 795-824
  
• Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo:
  Improving table compression with combinatorial optimization. 825-851
  
• Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer:
  Magic Functions. 852-921
  
• Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal:
  Conditions on input vectors for consensus solvability in asynchronous distributed systems. 922-954
  
• Marie-Pierre Béal, Dominique Perrin:
  On the generating sequences of regular languages on k symbols. 955-980