From - Sun Jun 22 15:42:10 1997 Path: Radon.Stanford.EDU!news.Stanford.EDU!su-news-hub1.bbnplanet.com!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!newsfeed.internetmci.com!news-was.dfn.de!news-fra1.dfn.de!news-ge.switch.ch!news.unige.ch!news From: "Jose D. P. Rolim" Newsgroups: comp.theory Subject: RANDOM97: Program Date: Thu, 19 Jun 1997 15:34:27 +0200 Organization: University of Geneva Lines: 130 Distribution: inet Message-ID: <33A93563.78D5@cui.unige.ch> NNTP-Posting-Host: cuisun50.unige.ch Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; name="program.txt" Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (X11; I; SunOS 5.5.1 sun4m) Content-Disposition: inline; filename="program.txt" Xref: Radon.Stanford.EDU comp.theory:11994 X-Mozilla-Status: 0001 Content-Length: 2932 RANDOM'97 1st International Symposium on Randomization and Approximation Techniques in Computer Science 11-12 July 1997 University of Bologna, Italy Program Friday afternoon: 14:30 - 15:15 INVITED TALK: Polynomial Time Approximations Schemes for Some Dense Instances of NP-Hard Optimization Problems Marek Karpinski 15:15 - 15:40 Probabilistic approximation of some NP optimization problems by finite-state machines Dawei Hong and Jean-Camille Birget 15:40 - 16:05 Approximation Algorithms for Covering Polygons with Squares and Similar Problems Christos Levcopoulos and Joachim Gudmundsson 16:05 - 16:30 Greedily approximating the r-independent set and k-center problems on random instances Bernd Kreuter and Till Nierhoff 16:30 - 17:00 Coffee Break 17:00 - 17:45 INVITED TALK: Nearly Linear Time Approximation Schemes for Euclidean TSP, Steiner Tree and Other Geometric Problems Sanjeev Arora 17:45 - 18:10 Random Sampling of Euler Tours Prasad Tetali and Santosh Vempala 18:10 - 18:35 A Combinatorial Consistency Lemma with application to the PCP Theorem Oded Goldreich and Muli Safra 18:35 - 19:00 Super-bits, Demi-bits, and NQP-natural Proofs Steven Rudich 19:00 - 19:25 Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols Michael Saks and Shiyu Zhou Saturday morning: 08:30 - 09:15 INVITED TALK: Approximation on the web: a compendium of NP optimization problems Pierluigi Crescenzi and Viggo Kann 09:15 - 09:40 On the average-case complexity of shortest-paths problems in the vertex-potential model C. Cooper, A. Frieze, K. Mehlhorn and V. Priebe 09:40 - 10:05 Random-Based Scheduling: New Approximations and LP Lower Bounds Andreas S. Schulz and Martin Skutella 10:05 - 10:30 'Go with the winners' Generators with Applications to Molecular Modeling Thomas Lengauer and Marcus Peinado 10:30 - 11:00 Coffee Break 11:00 - 11:45 INVITED TALK: Using Hard problems to De-randomize Algorithms Russell Impagliazzo 11:45 - 12:10 Weak and Strong Recognition by 2-way Randomized Automata Andris Ambainis, Rusins Freivalds and Marek Karpinski 12:10 - 12:35 Tally languages accepted by Monte Carlo pushdown automata Janis Kaneps, Dainis Geidmanis and Rusins Freivalds 12:35 - 13:00 Resource-bounded randomness and compressibility with respect to nonuniform measures Steven M. Kautz 13:00 - 13:25 Randomneess, Stochasticity and Approximations Yongge Wang