Article: 1987 of cmu.cs.theory Newsgroups: cmu.cs.theory Path: cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!ECCC@penthesilea.uni-trier.de From: ECCC@penthesilea.uni-trier.de ( Electronic Colloquium in Computational Complexity) Subject: STACS'96 - Program, registration, accomodation Status: RO Message-ID: <9601191009.AA00280@penthesilea.Uni-Trier.DE> X-Mozilla-Status: 0001 Sender: news+@cs.cmu.edu Original-To: Local Distribution Reply-To: Theory-A - TheoryNet World-Wide Events , Electronic Colloquium in Computational Complexity Approved-By: Theory-A - TheoryNet World-Wide Events Organization: Unavailable Original-Sender: TheoryNet List Date: Sat, 3 Feb 1996 04:23:03 GMT Approved: bboard-news_gateway Comments: To: Multiple recipients of list THEORY-A Lines: 390 PLEASE POST *** PLEASE POST *** PLEASE POST *** PLEASE POST *** PLEASE POST *** ==================== STACS'96 Grenoble, France February 22-24, 1996 ==================== The Symposium on Theoretical Aspects of Computer Science is held annually, alternating between Germany and France. STACS is organized jointly by the Special Interest Group for Theoretical Computer Science of Gesellschaft fuer Informatik (GI) and the Special Interest Group for Applied Mathematics of afcet. STACS '96, the 13th in this series, will be held in Grenoble, France, February 22-24, 1996. The symposium will feature the presentation of 52 original research papers (selected from 185 submitted papers) . Three invited speakers, Gilles Brassard (Montreal), Joseph Sifakis (Grenoble) and Emo Welzl (Berlin) will share their insights on some new very exciting developments. The proceedings will be published by Springer in Lecture Notes in Computer Science. Please find below + STACS'96 Program + STACS'96 Registration Form + Accomodation Information More information can be found on the Web at URL: http://www.imag.fr/stacs96.html The Program Committee for STACS'96 consisted of: L. Bouge' (Lyon), V. Bruye`re (Mons), H. Comon (Orsay), S. Fenner (Portland), A. Gibbons (Warwick), E. Grandjean (Caen), T. Hagerup (Saarbr"ucken), M. Krause (Dortmund), K.J. Lange (T"ubingen), I. Litovky (Nice), C. Puech (Grenoble, co-chair), H. Reichel (Dresden), R. Reischuk (L"ubeck, co-chair), P. Van Emde Boas (Amsterdam), S. Varrichio (L'Aquila). >>>>>>>>>>==========================================================<<<<<<<<<< STACS'96 - PROGRAM >>>>>>>>>>==========================================================<<<<<<<<<< PROGRAM ======= Thursday, February 22, 1996 =========================== 8.25 Welcome 8.30 Invited Talk: New Trends in Quantum Computing Gilles Brassard Session 1A: Complexity Theory I 9.30 Compressibility and Resource Bounded Measure Harry Buhrman, Luc Longpre 9.55 On the Complexity of Random Strings Martin Kummer Session 1B: Automata Theory I 9.30 Remarks on Generalized Post Correspondence Problem Tero Harju, J. Karhumaki, Daniel Krob 9.55 Cyclic Languages and Strongly Cyclic Languages Marie-Pierre Bel, Olivier Carton, Christophe Reutenauer 10.20 Coffee Break Session 2A: Complexity Theory II 10.50 Resource-Bounded Dense Genericity, Stochasticity and Weak Randomness Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng 11.15 The Complexity of Generating and Checking Proofs of Membership Harry Buhrman, Thomas Thierauf 11.40 Observations on Measure and Lowness for $\Delta ^{P} _{2}$ Jack H. Lutz 12.05 Solvable Black-Box Group Problems are Low for PP V. Arvind, N.V. Vinodchandran Session 2B: Automata Theory II 10.50 Languages Recognized by Finite Aperiodic Groupoids Martin Beaudry 11.15 Star-Height of an N-Rational Series Fridirique Bassino 11.40 An Aperiodic Set of Wang Cubes Karel Culik II, Jarkko Kari 12.05 Lyndon Factorization of Infinite Words Guy Melangon 12.30 Lunch Session 3A: Parallel Algorithms 14.00 Embedding Graphs with Bounded Treewidth into Optimal Hypercubes Volker Heun, Ernst W. Mayr 14.25 From Parallel Comparability Graph Recognition to Parallel Modular Decomposition Michel Morvan, Laurent Viennot 14.50 Fault-Tolerant Shared Memory Simulations Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann 15.15 On Word-Level Parallelism in Fault-Tolerant Computing Piotr Indyk Session 3B: Learning 14.00 Learning with Confidence Janis Barzdins, Rusins Freivalds, Carl H. Smith 14.25 Extracting Best Consensus Motifs from Positive and Negative Examples Erika Tateishi, Osamu Maruyama, Satoru Miyano 14.50 PAC Learning with Simple Examples Francois Denis, Cyrille D'Halluin, Remi Gilleron 15.15 General Inductive Inference Types Based on Linearly-Ordered Sets Andris Ambainis, Rusins Fraivalds, Carl H. Smith 15.40 Coffee Break Session 4A: Parallel and Distributed Systems I 16.10 On the Power of Non Observable Actions in Timed Automata Beatrice Berard, Antoine Petit, Paul Gastin 16.35 Trace Rewriting: Computing Normal Forms in Time $O(n log n)$ Michael Bertol. Volker Diekert 17.00 A Decision Procedure for Well-Formed Linear Quantum Cellular Automata Christoph Dur, Huong LeThanh, Miklos Santha 17.25 On the Definition of Back and Forth Bisimulation Notion in Petri Nets Rachid Hamadi, Zoubir Belmesk Session 4B: Complexity Theory III 16.10 On the Complexity of Worst Case and Expected Time in a Circuit Andreas Jakoby, Christian Schindelhauer 16.35 On the Existence of Hard Sparse Sets under Weak Reductions Jin-Yi Cai, Ashish V. Naik, D. Sivakumar 17.00 Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardness Alexander E. Andreev, Andrea E.F. Clementi, Josi D. P. Rolim 17.25 Fine Separation of Average Time Complexity Classes Jin-Yi Cai, Alan L. Selman Friday, February, 23, 1996 ========================== 8.30 Invited Talk: Compositional Specification of Timed Systems Joseph Sifakis (and Sergio Yovine) Session 5A: Cryptography 9.30 Optimal Tree-based One-time Digital Signatures Schemes Daniel Bleichenbacher, Ueli Maurer 9.55 The Action of a New Random Permutation on r-tuples and an Application to Cryptography Joel Friedman, Antoine Joux, Yuval Roichman, Jacques Stern, Jean-Pierre Tillich 10.20 A Unified and Generalized Treatment of Authentication Theory Ueli M. Maurer Session 5B: Logic & Data Base Theory 9.30 Monadic Second Order Logic on Tree-like Structures Igor Walukiewicz 9.55 On Bijections vs. Unary Functions Thomas Schwentick 10.20 The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs Jerzy Marcinkowski 10.45 Coffee Break Session 6A: Algorithms 11.15 A Combinatorial Design Approach to MAXCUT Thomas Hofmeister, Hanno Lefmann 11.40 Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width Arvind Gupta, Naomi Nishimura 12.05 A Characterization of Thequadrilateral Meshes of a Surface which Admit a Compatible Hexahedral Mesh of the Enclosed Volume Scott A.Mitchell Session 6B: Semantics & Program Verification 11.15 On the Complexity of Infinite-state Model-checking J.C. Bradfield 11.40 Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams Beate Bollig, Ingo Wegener 12.05 "Optimal" Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics Roberto Giacobazzi 12.30 Lunch Session 7A: Parallel and Distributed Systems II 14.00 Flip-Flop Nets Vincent Schmitt 14.25 Lower Bounds for Compact Routing Evangelos Kranakis, Danny Krizanc Session 7B: Automata Theory III 14.00 On the Successor Function in Non-classical Numeration Systems Christiane Frougny 14.25 Minimal Forbidden Words and Symbolic Dynamics Marie-Pierre Bial, Filippo Mignosi, Antonio Restivo 15.45 Social Event (to be announced) 19.00 Conference Dinner Saturday, February 24, 1996 =========================== Session 8A: Algorithms II 9.00 Universal Hashing and k-wise Independent Random Variables via Integer Arithmetic without Primes Martin Dietzfelbinger 9.25 Ranking and Unranking Trees Using Regular Reductions Pierre Kelsen 9.50 On Competitive On-Line Paging with Lookahead Dany Breslauer 10.15 Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters Jens Lagergren Session 8B: Communication Complexity 9.00 The "log rank" Conjecture for Modular Communication Complexity Christoph Meinel, Stephan Waack 9.25 Upper Bounds on Multiparty Communication Complexity of Shifts Andris Ambainis 9.50 Some Bounds on Multiparty Communication Complexity of Pointer Jumping Carsten Damm, Stasys Jukna, Ji\v{r}m Sgall 10.15 Optimal Schedules for d-D Grid Graphs with Communication Delays E. Bampis, C. Delorme, J.-C. Kvnig 10.40 Coffee Break 11.10 Invited Talk: Linear Programming - Randomized Algorithms and Abstract Framework Emo Welzl (and Bernd Gaertner) >>>>>>>>>>==========================================================<<<<<<<<<< Symposium Registration Form - STACS'96 >>>>>>>>>>==========================================================<<<<<<<<<< ====================================== Symposium Registration Form - STACS'96 ====================================== Please return this form with proof of payment to : AFCET - STACS'96 AFCET, 156 Bd. Pereire, 75017 Paris, FRANCE Fax : +33(1)42 67 93 12 Tel: +33(1)47 66 24 19 e-mail: Afcet.Congres@ibp.fr Last Name: _______________________ First name :_____________________ Institute __________________________________________________________ Address*: __________________________________________________________ City: _______________ Country : ________________ ZIP-code : ________ Tel.: ____________, Fax : ____________, E-mail : __________________ *Please indicate if it is your personal __ or professional__ address Payment enclosed : ================= Copy of banker's draft ___ Purchase order ___ Cheque ___ CCP ___ Official order form ___ I duly authorize you to charge my Visa Intl ___ Master Card ___ Credit card # __________________ Expiration ____________________ Cardholder's name ______________ Date ___________________________ Signature ______________________ Number of invoice copies requested : ___ Invoice to be sent to (if different from above) : ___________________ _____________________________________________________________________ LUNCHES ======= I will take lunch on Feb. 22 Yes __ No __, on Feb. 23 Yes __ No __ TRAVEL * ====== Please send me a local railway discount ticket ___ Please send me a local flight discount ticket ___ * both available for the conference dates ================= Registration fees (including French VAT @ 20.6 %, ================= last prevailing rate into effect). Before February 9 After February 9 AFCET-GI member (1) 1400 FF 1600 FF (inc. VAT 20.6%: 239,13 (inc. VAT 20,6 % : 273,30) Non member 1650 FF 1850 FF (inc. VAT 20,6% : 281,84) (inc. VAT 20,6% : 316,00) Student (2) 785 FF 985FF (inc. VAT 20,6% : 134,08) (inc. VAT 20,6% : 168,25) (1) Please indicate if you are a member of GI ___ AFCET ___ (2) Please attach a copy of your student card for the ongoing year Fees include sessions attendance, one copy of the proceedings, the symposium dinner, lunches and breaks. Proceedings and symposium dinner are not included in students registration fees. + For a restricted number of students there will be the possibility to + get a student subsidy in the form of a reduced conference fee. If interested + please check here ___ and provide information on the reasons for applying. Date ____________________ Signature _______________________ >>>>>>>>>>==========================================================<<<<<<<<<< Accomodation Information for STACS'96 >>>>>>>>>>==========================================================<<<<<<<<<< For reservation of an hotel room, you can either + contact directly one of the hotels listed on STACS WWW page (URL http://www.imag.fr/stacs96.html) + or use the services of Wagonlit Evenement and return the following Accomodation Reservation Form ======================================== Accomodation Reservation Form - STACS'96 ======================================== Please return this form to : Wagonlit Evenements - Mrs Anne Deschamps Dipt. Congrhs/Conventions - 50 rue de Londres 75008 Paris, France Fax : +33 1 44 90 33 15 Til : +33 1 44 90 33 16 Last Name: _______________________ First name :_____________________ Institute __________________________________________________________ Address*: __________________________________________________________ City: _______________ Country: ________________ ZIP-code : _________ Phone: _________________ Fax: ________________ Hotel category Rate Compulsory hotel deposit per room -------------- ---- --------------------------------- 2 ** FF 230/320 FF 350 3 *** FF 450/505 FF 550 The hotel deposit will be transmited to the reserved hotel minus FF 90 for reservation fees and deducted from your final bill which you must settle before leaving. Please reserve: -------------- ___ ...... twin bed room(s) shared by 2 persons ___ ...... single room(s) in a ** ___ *** ___ hotel from.............................. to ............................... am .............................. nights Settlement ---------- Hotel deposit ................ FF Please find enclosed : __ cheque payable in FF to Wagons-Lits Evenements __ copy of my bank transfer sent to the account : 00021935201 BNP Saint Lazare - code banque 30004 - code guichet 00819 WAGONLIT/SEAVT - Dept. Congres/Conventions - code comptable 04/670 The bank charges must be added to the above amount. Any difference will be settled on locally. ___ I duly authorize you to charge my Visa Intl ___ Eurocard ___ Mastercard ___ Credit card # __________________ Expiration ____________________ Cardholder's name ______________ Date ___________________________ Signature ______________________ + Very important : no reservation will be made if the present form + is not accompanied by he right amount Cancellation : Before February 9, 1996 ; refund minus FF 90 registration fees After February 9 : no refund Date ______________ Signature ___________________________ >>>>>>>>>>==========================================================<<<<<<<<<<