PRELIMINARY CALL FOR PAPERS APPROX 2003+ RANDOM 2003 6th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th. International Workshop on Randomization and Approximation Techniques in Computer Science 24-26 August 2003 Princeton University SCOPE The 6th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX'2003 - and the 7th. International Workshop on Randomization and Approximation Techniques in Computer Science -RANDOM'2003- will colocate at the Computer Science Department of Princeton University, Princeton on August 24-26, 2003. APPROX'2003 focuses on algorithmic and complexity aspects arising in the development of efficient approximate solutions to computationally difficult problems, while RANDOM'2003 focuses on applications of randomness to computational and combinatorial problems. RANDOM'2003 is the seventh workshop in the series after Bologna, Barcelona, Berkeley, Geneva, Berkeley again and Harvard; APPROX'2001 is the sixth in the series after Aalborg, Berkeley, Saarbrücken, Berkeley again and Rome. TOPICS Papers are solicited in all research areas related to randomization and approximation, including, but not limited to: * design and analysis of randomized algorithms * randomized complexity theory * design and analysis of approximation and online algorithms * complexity of approximation problems * random combinatorial structures * error-correcting codes * pseudorandomness and derandomization * network models and algorithms * average-case analysis * property testing * expander graphs and randomness extractors * random walks/Markov chains * probabilistic proof systems * random projections and embeddings * computational learning * various applications PUBLICATION Proceedings will be published in the Springer-Verlag series Lecture Notes in Computer Science. Previous proceedings of RANDOM appeared as LNCS 1269, 1518 1671, 2129, 2483 and as Proceedings in Informatics 8 while proceedings of APPROX appeared as LNCS 1444, 1671, 1913, 2129 and 2462. GUIDELINE FOR SUBMISSION Electronic submissions are solicited. To submit electronically a paper or for more specific instructions about APPROX, please consult: http://sigact.acm.org/~approx03/approx03.html To submit electronically a paper or for more specific instructions about RANDOM, please consult: http://sigact.acm.org/~random03/random03.html The postscript must be received by 11:59pm (PDT) of April 14th for your submission to be considered. In extreme cases, contributions may be submitted by sending 6 hard copies to: APPROX-RANDOM 2003 Computer Science Department Princeton University 35 Olden St Princeton NJ 08544 Simultaneous submission to other conferences with published proceedings is not allowed. Abstract format: Authors should submit an extended abstract (not a full paper). An abstract should start with the title of the paper, each author's name, affiliation, and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work. The abstract should not exceed 10 single-spaced pages on letter-size paper, using reasonable margins and at least 11-point font. If the authors believe that more details are essential to substantiate the main claims of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee. IMPORTANT DATES Submission Deadline: April 14th, 2003 Notification: May 28th, 2003 Camera ready: June 17th, 2003 PROGRAM COMMITTEES APPROX: Sanjeev Arora, Princeton, chair Yossi Azar, Tel Aviv U. Gruia Calinescu, Illinois IT Chandra Chekuri, Bell Labs Anupam Gupta, CMU George Karakostas, McMaster University Philip Klein, Brown University Robert Krauthgamer, ICSI/UC Berkeley Kamal Jain, Microsoft Research Stefano Leonardi, Rome University Yuri Rabinovich, University of Haifa David Williamson, IBM Almaden RANDOM: Amit Sahai, Princeton, chair Paul Beame, University of Washington, Seattle Bernard Chazelle, Princeton Alan Frieze, CMU Joe Kilian, NEC Eyal Kushilevitz, Technion Dana Randall, Georgia Tech Ran Raz, Weizmann and IAS Dana Ron, Tel-Aviv Michael Saks, Rutgers Alistair Sinclair, UC Berkeley Chris Umans, CalTech WORKSHOP CHAIRS Klaus Jansen, U. of Kiel e-mail: kj@informatik.uni-kiel.de José Rolim, U. of Geneva e-mail: rolim@cui.unige.ch STEERING COMMITTEE APPROX Susanne Albers, U. of Freiburg Dorit Hochbaum, UC Berkeley Klaus Jansen, U. of Kiel Samir Khuller, Maryland Jose Rolim, U. of Geneva Vijay Vazirani, Georgia Tech RANDOM Josep Diaz, UPC Barcelona Oded Goldreich, Weizmann Klaus Jansen, U. of Kiel Michael Luby, Digital Fountain Christos Papadimitriou, UC Berkeley José Rolim, U. of Geneva Paul Spirakis, U. of Patras CONFERENCE PAGE http://cui.unige.ch/tcs/random-approx