% The 98 Complexity brochure --- preliminary version %\documentstyle[draft]{article} %% comment out for two columns \documentstyle[draft,proc,twocolumn]{article} %% comment in for two columns \pagestyle{empty} \hfuzz=4pt \vfuzz=4pt % \input{epsf} %%%%%%%%%%%% EPS Stuff %%%%%%%%%%%%%%%% % \epsfxsize=40pt %%%%%%%%%%%% EPS Stuff %%%%%%%%%%%%%%%% % \setlength{\oddsidemargin}{-.5in} %% comment out for two columns % \setlength{\topmargin}{-1in} %% comment out for two columns % \setlength{\textwidth}{3.15in} %% comment out for two columns \setlength{\topmargin}{0.in} %% comment in for two columns \setlength{\textwidth}{6.625in} %% comment in for two columns \setlength{\columnsep}{0.375in} %% comment in for two columns \setlength{\textheight}{7.75in} \parindent=0pt \newcommand{\when}[1]{\makebox[.75in][l]{\sf #1}} \newcommand{\stub}[1]{\typeout{*** Stub! ***} $\langle${\bf Stub:} {\em #1}$\rangle$} \newcommand{\topic}[1]{\smallskip{\bf #1}\enspace} %%% complexity classes \newcommand{\NP}{{\rm NP}} \newcommand{\sqr}[1]{{\vcenter{\hrule height.#1pt \hbox{\vrule width.#1pt height#1pt \kern#1pt \vrule width.#1pt} \hrule height.#1pt}}} %\newcommand{\thickbar}{\rule{\textwidth}{1pt}} %% comment out for two columns \newcommand{\thickbar}{\rule{3.1875in}{1pt}} %% comment in for two columns \tolerance 10000 \begin{document} \typeout{ } \typeout{***************************************************} \typeout{The Complexity Brochure} \typeout{Draft: March 17} \typeout{} \typeout{Warnings: This LaTeXs very noisily.} \typeout{Also, the eps stuff may not work at your site.} \typeout{***************************************************} \typeout{ } \vspace{.4in} \begin{center} {\huge\bf Computational Complexity\\} \vspace{.3in} {\Large Thirteenth Annual IEEE\\[4pt] Conference}\\ \vspace{.3in} {\large Sponsored by} \\[1ex] {\Large The IEEE Computer Society \\[-1pt] Technical Committee on \\[-1pt] Mathematical Foundations \\[4pt] of Computing \\[.6ex] {\large and}\\[1ex] University at Buffalo\\[4pt] State University of New York} \\ \vspace{.7in} %%% IEEE-CS logo % \ \epsfbox{ieee-cs.eps} \ \\ %%%%%%%%%%%% EPS Stuff %%%%%%%%%%%%%%%% \vspace{.7in} {\large In cooperation with \\[1ex] ACM-SIGACT and EATCS \\ \vspace{.7in} June 15 --- 18, 1998 \\ \vspace{.25in} Buffalo, NY, USA} \end{center} \newpage \begin{center}\large\bf ADVANCE REGISTRATION FORM \end{center} Last name \hrulefill \ \\[5pt] First name \hrulefill \ \\[5pt] Affiliation \hrulefill \ \\[5pt] Mailing address \hrulefill \ \\[5pt] \_\hrulefill \ \\[5pt] \_\hrulefill \ \\[5pt] \_\hrulefill \ \\[5pt] EMail address \hrulefill \ \\[5pt] Homepage \hrulefill \ \\[5pt] Telephone \hrulefill \ \\[5pt] Special dietary needs \hrulefill \ \\[5pt] Special accessibility needs \hrulefill \ \\[5pt] \thickbar\\[5pt] \begin{tabular}{lcc}\footnotesize \kern-5pt{\large\bf Conference Fees${}^*$} &Advance${}^{\dagger}$& Late\\[1ex] Members${}^\ddagger$ & \$\makebox[2em][r]{235} & \$\makebox[2em][r]{290} \\ Nonmembers & \$\makebox[2em][r]{295} & \$\makebox[2em][r]{360} \\ Students & \$\makebox[2em][r]{115} & \$\makebox[2em][r]{140} \\ Extra Proceedings & \$\makebox[2em][r]{40} & \$\makebox[2em][r]{40}\\[0.5ex] %% faked footnotes \makebox[0pt][l]{\footnotesize${}^*$The registration fee includes lunches, a proceedings, and}\\[-0.5ex] \makebox[0pt][l]{\footnotesize\hspace{2pt} all social events.}\\[-0.5ex] \makebox[0pt][l]{\footnotesize${}^{\dagger}$The advance registration deadline is May 29.}\\[-0.5ex] \makebox[0pt][l]{\footnotesize${}^{\ddagger}$ACM, EATCS, IEEE, or SIGACT members.} \end{tabular}\\ \thickbar\\[5pt] {\large\bf Payment computation} \\[10pt] Registration fee \hfill \$\ \rule{2cm}{0.25pt} \\[5pt] Extra Proceedings ( \rule{0.7cm}{0.25pt}\ ) \hfill \$\ \rule{2cm}{0.25pt} \\[5pt] Voluntary contribution \hfill \$\ \rule{2cm}{0.25pt} \\[5pt] Total \hfill \$\ \rule{2cm}{0.25pt} \\[5pt] \begin{center} {\it (Please fill in the next page too)} \end{center} \newpage {\large\bf Social events}\\[10pt] Estimated number of family members (including you) attending. Family of registrants included FREE:\\[5pt] \makebox[1.5in][l]{Welcoming Barbecue} \rule{2cm}{0.25pt} \\[5pt] \makebox[1.5in][l]{Niagara Falls excursion} \rule{2cm}{0.25pt} \thickbar\\[5pt] {\large\bf Methods of Payment}\\[5pt] \begin{tabular}{ll} $\sqr{8}$ Check Enclosed & $\sqr{8}$ Money Order Enclosed \end{tabular}\\[5pt] Make check payable to ``UB Foundation/CCC'98'' {\it Do not send cash}\\[5pt] \begin{tabular}{ll} $\sqr{8}$ VISA & $\sqr{8}$ American Express \\ $\sqr{8}$ MasterCard & $\sqr{8}$ Discover \\ $\sqr{8}$ Carte Blanche & $\sqr{8}$ Diner's Club \end{tabular}\\[5pt] Credit Card Number \hrulefill \\[5pt] Exp.\ Date \hrulefill \\[5pt] Name on Card \hrulefill \\[5pt] Signature \hrulefill \thickbar\\[5pt] {\large\bf Electronic registration} \smallskip Electronic registration is possible through the web site for this year's conference. Check the conference web site for latest information. If not paying through the web site, you need to return the registration form by mail or fax. \thickbar\\[5pt] {\large\bf Return registration form to:} \begin{center}\frenchspacing\begin{tabular}{l} IEEE Conference on Computational Complexity \\ University at Buffalo \\ Office of Conference Operations \\ 120 Center For Tomorrow \\ Buffalo, NY 14260 \end{tabular}\end{center} {\large\bf or FAX to:} 1-716-645-3869. \newpage {\large\bf Conference homepage} \smallskip Information about this year's conference is available on the web at\\ {\sf http://www.cs.buffalo.edu/{$\sim$}regan/ccc98/} Information about the Computational Complexity conference is available at\\ {\sf http://cs.utep.edu/longpre/complexity.html} \bigskip {\large\bf Lodging} \smallskip The first two hotels below have been chosen as standard lodging for the conference. Hotel reservations, either at the standard or at the alternate hotels, should be handled directly by contacting the hotel. Standard lodging has guaranteed rates until May 29 and you must mention the conference name to get those guaranteed rates. All hotels are within easy walking distance, except the University Inn, which provides free van service. Hotels 1, 2 and 3 have free shuttles from the airport. Use courtesy phones. \begin{enumerate} \item Hampton Inn, 10 Flint Road, Amherst, NY 14226. Rate: \$79 (double). Reservations: 1-800-HAMPTON (1-800 426-7866). Local: (716) 689-4414. FAX (716) 689-4382. {\sf http://www.hamptoninn.com/} \item University Inn \& Conference Center, 2401 N. Forest Road, Amherst, NY 14226. Rate: \$62 (double). (716) 636-7500; FAX (716) 636-8296 {\sf http://www.universityinn.com/} \end{enumerate} We have not arranged for special conference rates at the following alternate hotels. Current single-room rates for June 15 are shown, and are subject to change. Certain discounts may apply for you. \begin{enumerate} \item[3.] Buffalo/Niagara Marriott, 1340 Millersport Hwy., Amherst, NY 14221. Rate \$129, \$109 with AAA. (716) 689-6900; FAX (716) 689-0483. Reservations: 1-800-334-4040, 1-800-228-9290 {\sf http://www.marriott.com/marriott/BUFNY/} \item[4.] Red Roof Inn Buffalo(Amherst); 42 Flint Road, Amherst, NY; Rate \$57. (716) 689-7474; FAX (716) 689-2051. Reservations: 1-800-843-7663. {\sf http://www.redroof.com/} \item[5.] Buffalo/Amherst Super 8 Motel; 1 Flint Road, Amherst, NY 14226; Rate \$49. (716) 688-0811; FAX (716) 688-2365. Reservations: 1-800-800-8000. {\sf http://www.super8.com/} \end{enumerate} There is also a dorm option at Governor's Residence Halls. The Halls are located 3/4 mile from the conference site; transportation will be provided in case of need. They are not air conditioned; while June is usually temperate in Buffalo, a heat wave is possible. 1 communal bathroom for every 4 rooms. Rates are \$22.98/night single occupancy, or \$18.50 per person/night double occupancy. Payment must be at time of check-in, but can be VISA, MASTERCARD, travelers' checks, or personal checks drawn on a US bank. You must fill a request form available from the conference homepage, or request the form with your registration. \bigskip {\large\bf Voluntary Contributions} \smallskip \begin{sloppypar} In order to support expenses of a few interested researchers from currency-poor countries, each year, the Complexity Conference is seeking donations (any amount) from its participants. Please help continue this practice by including a donation with your registration fee. \end{sloppypar} \bigskip {\large\bf Special Dietary/Accessibility Needs} \smallskip UB Conference Operations can handle special dietary or accessibility needs. Please indicate special needs on the advance registration form. Contact the local arrangement chair if questions arise. \bigskip {\large\bf Additional Proceedings} \smallskip These can be ordered on the registration form and will also be available for purchase on-site at \$40. \bigskip {\large\bf Conference Information} \smallskip \topic{Location} Amherst is a big suburb of Buffalo. All conference functions will be held in the Center For Tomorrow, which is on the Amherst (``North'') Campus, about a half-mile from its academic buildings. As often with U.S.\ suburbia, a car is required to reach most places of entertainment. Downtown Buffalo is reachable by bus-to-subway. The Hampton, Marriott, and University Inn can arrange excursions for their guests. The conference web pages have more information about local attractions. \topic{Social Program} {\sl Sunday Night:} There will be a Welcoming Barbecue, Center For Tomorrow, 4pm to 9pm. Family of registered participants are invited at no extra cost. {\sl Tuesday Afternoon:} Excursion to Niagara Falls. Departure at 2pm from Center For Tomorrow. Family of participants are invited to join at no extra cost. Although no meal is included in this excursion, one can eat in the Falls area. Schedule for returning busses will be determined later. {\sl Wednesday Night:} Business Meeting at 6:00pm in Center For Tomorrow. Food will be served. \bigskip {\large\bf Getting There} \smallskip \topic{By airplane:} The conference is only about 7 miles from Buffalo airport. Car rentals and airline reservations for conference attendees can be made at discount rates through NFT Travel, 1 800 633 6782, STAR FILE BUFMTG, {\sf www.nfttravel.com}. \topic{By car:} To drive from the airport, exit airport right (west) on Genesee St., left onto 33; first exit on right gets you onto 90 east; Exit 50 ``290 Niagara Falls'' (exit on right again); Exit 5B: Millersport Hwy North; get over 3 lanes and make first left at light onto Flint Road. The Marriott, Red Roof, Hampton, and Super-8 are there, and the Center For Tomorrow is just across Maple Road off Flint on the left. To reach the University Inn, continue on Flint into campus, left at the first light onto Audubon, right at the 4th light onto N. Forest, and it is on your right. \bigskip {\large\bf Complexity Abstracts} \smallskip Each year, brief abstracts on current research on topics covered by the conference are made available electronically a week before the conference. Submission is open to all. June 10 is the submission deadline. For details of submissions format send email to {\sf abstract@cs.umd.edu} or contact the Abstracts Editor: William Gasarch; Dept.~of Comp.~Sci.; Univ.~of Maryland at College Park; College Park, Maryland, 20742, Email: {\sf gasarch@cs.umd.edu}. \newpage {\large\bf Messages \& Additional Information} \smallskip Center For Tomorrow: (716) 645-2018. The site is staffed during normal daytime hours. Internet access from the conference site will be provided. UB Conference Operations: (716) 645-3705; or e-mail to {\sf wjw2@acsu.buffalo.edu}. \bigskip {\large\bf Acknowledgments} \smallskip \topic{Sponsors} The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with ACM SIGACT and EATCS. Additional support was provided by the University at Buffalo, Computer Science Department and Faculty of Natural Sciences and Mathematics. \topic{Local Arrangements} Ken Regan (Chair), Jin-Yi Cai, Alan Selman. \topic{Program Committee} Joan Feigenbaum (Chair), Richard Beigel, Stephen Fenner, Judy Goldsmith, Martin Kummer, Elvira Mayordomo, Moni Naor, Steven Rudich, Dan Spielman, Alan Selman. \topic{Conference Committee} Eric Allender (Chair), Richard Beigel, Jin-Yi Cai, Anne Condon, Lance Fortnow, Steven Homer, Luc Longpr\'e, Jacobo Tor\'an, Avi Wigderson. %%% %%% The Technical Program %%% \parskip 1.4ex \begin{center} {\large\bf PROGRAM} \end{center} All sessions will be in the Center for Tomorrow. {\bf RECEPTION/REGISTRATION:} Sunday from 4pm to 9pm, Center For Tomorrow. \frenchspacing \when{8:50--9:00} Welcoming Remarks {\bf SESSION 1:} Monday, June 15, Morning\\ Chair: R. Beigel (Lehigh Univ.) \when{9:00--9:30} {\em On Membership Comparable Sets,} D. Sivakumar (Univ.\ Houston) \begin{sloppypar} \when{9:30--10:00} {\em Nonrelativizing Separations,} H. Buhrman (CWI), L. Fortnow (Univ.\ Chicago), T. Thierauf (Univ.\ Ulm) \end{sloppypar} \when{10:00--10:30} {\em Two Queries,} H. Buhrman (CWI), L. Fortnow (Univ.\ Chicago) \when{10:30--11:00} Break {\bf Survey Talk 1:} Chair: J. Feigenbaum (AT\&T Labs) \when{11:00--12:15} {\em The Status of {\rm P} vs.\ {\rm NP} and Lower Bounds,} S. Rudich (Carnegie Mellon Univ.) \bigskip {\bf SESSION 2:} Monday, June 15, Afternoon \\ Chair: S. Rudich (Carnegie Mellon Univ.) \when{2:00--2:30} {\em Computational Indistinguishability: A Sample Hierarchy,} O. Goldreich (Weizmann Inst. and Mass. Inst. of Tech.), M. Sudan (Mass. Inst. of Tech.) \when{2:30--3:00} {\em Proofs of Membership vs.\ Proofs of Knowledge,} G. Di Crescenzo and R. Impagliazzo (UC San Diego) \when{3:00--3:30} {\em Approximating the SVP to within a factor $(1 + 1/(dim^{\epsilon}))$ is {\rm NP}-hard under randomized reductions,} J.-Y. Cai and A. Nerurkar (Univ.\ at Buffalo) \when{3:30--4:00} Break {\bf SESSION 3:} Monday, June 15, Late Afternoon \\ Chair: M. Naor (Weizmann Inst.) \when{4:00--4:30} {\em Arthur-Merlin Games in Boolean Decision Trees,} R. Raz (Weizmann Inst.), G. Tardos (Math. Inst.\ of the Hungarian Acad.\ of Sci.), O. Verbitsky (Lviv Univ.), N. Vereshchagin (Moscow State Univ.) \when{4:30--5:00} {\em On Arithmetic Branching Programs,} A. Beimel (Harvard Univ.), A. Gal (UT Austin) \when{5:00--5:30} {\em The Satisfiability Problem for Probabilistic Ordered Branching Programs,} M. Agrawal (IIT Kanpur), T. Thierauf (Univ.\ Ulm) \begin{center} {\large\bf TUESDAY} \end{center} \vspace{-0.2in} \bigskip{\bf SESSION 4:} Tuesday, June 16, Morning\\ Chair: D. Spielman (Mass. Inst.\ of Tech.) \when{9:00--9:30} {\em Isolation, Matching, and Counting,} E. Allender (Rutgers Univ.), K. Reinhardt (Univ.\ T\"ubingen) \when{9:30--10:00} {\em A Note on the Hardness of Tree Isomorphism,} B. Jenner (Univ.\ T\"ubingen and Univ.\ Ulm), P. McKenzie (Montr\'eal Univ.\ and Univ.\ T\"ubingen), J. Tor\'an (Univ.\ Ulm) \when{10:00--10:30} {\em Theory of Periodically Specified Problems: Complexity and Approximability,} M. Marathe (Los Alamos Natl. Lab.), H. Hunt, D. Rosenkrantz, R. Stearns (Univ.\ at Albany) \when{10:30--11:00} Break {\bf Survey Talk 2:} Chair: J. Feigenbaum (AT\&T Labs) \when{11:00--12:15} {\em Formal Models of Computation in Complexity and Coding Theory,} D. Spielman (Mass.\ Inst.\ of Tech.) \bigskip{\bf TUESDAY AFTERNOON:}\ Excursion to Niagara Falls. Departure at 2pm. \begin{center} {\large\bf WEDNESDAY} \end{center} \vspace{-0.2in} \bigskip{\bf SESSION 5:} Wednesday, June 17, Morning \\ Chair: S. Fenner (Univ.\ Southern Maine) \when{9:00--9:30} {\em How to Encode a Logical Structure as an OBDD,} H. Veith (Tech. Univ. Wien) \begin{sloppypar} \when{9:30--10:00} {\em Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets,} J. K\"obler and J. Messner (Univ.\ Ulm) \end{sloppypar} \when{10:00--10:30} {\em Lower Bounds for Computation with Limited Nondeterminism,} H. Klauck (Univ.\ Frankfurt) \when{10:30--11:00} Break {\bf Survey Talk 3:} Chair: J. Feigenbaum (AT\&T Labs) \when{11:00--12:15} {\em DNA Computing,} R. Beigel and B. Fu (Lehigh Univ.) \bigskip{\bf SESSION 6:} Wednesday, June 17, Afternoon \\ Chair: E. Mayordomo (Univ.\ Zaragoza) \when{2:00--2:30} {\em Hard Sets are Hard to Find,} H. Buhrman (CWI), D. van Melkebeek (CWI and Univ.\ Chicago) \when{2:30--3:00} {\em On the Resource Bounded Measure of {\rm P/poly},} J. K\"obler and W. Lindner (Univ.\ Ulm) \when{3:00--3:30} {\em Probabilistic Martingales and {\rm BPTIME} Classes,} K. Regan (Univ.\ at Buffalo), D. Sivakumar (Univ.\ Houston) \when{3:30--4:00} Break \bigskip{\bf SESSION 7:} Wednesday, June 17, Late Afternoon \\ Chair: J. Goldsmith (Univ.\ Kentucky) \when{4:00--4:30} {\em Complexity Limitations on Quantum Computation,} L. Fortnow (Univ.\ Chicago), J. Rogers (DePaul Univ.) \when{4:30--5:00} {\em Relationships between quantum and classical space-bounded complexity classes,} J. Watrous (Univ.\ Wisconsin at Madison) \when{5:00--5:30} {\em Uniformly Hard Languages,} R. Downey (Victoria Univ.), L. Fortnow (Univ.\ Chicago) \bigskip{\bf BUSINESS MEETING:}\ From 6pm in Center For Tomorrow. \bigskip{\bf RUMP SESSION:}\ After the business meeting. \begin{center} {\large\bf THURSDAY} \end{center} \vspace{-0.2in} \bigskip{\bf SESSION 8:} Thursday, June 18, Morning\\ Chair: A. Selman (Univ.\ at Buffalo) \when{9:00--9:30} {\em Resource-Bounded Measure,} J. Lutz (Iowa State Univ.) \when{9:30--10:00} {\em Randomness is Hard,} H. Buhrman (CWI) and L. Torenvliet (Univ.\ Amsterdam) \when{10:00--10:30} {\em Resource-Bounded Measure and Learnability,} W. Lindner and R. Schuler (Univ.\ Ulm), O. Watanabe (Tokyo Inst.\ of Tech.) \when{10:30--11:00} Break {\bf Survey Talk 4:} Chair: J. Feigenbaum (AT\&T Labs) \when{11:00--12:15} {\em Complexity Issues in Markov Decision Processes,} J. Goldsmith (Univ.\ Kentucky), M. Mundhenk (Univ. Trier) \end{document}