COMPUTATIONAL COMPLEXITY
Thirteenth Annual IEEE Conference

Sponsored by

The IEEE Computer Society Technical Committee on
Mathematical Foundations of Computing,

and

University at Buffalo

In cooperation with
ACM-SIGACT and EATCS

June 15 --- 18, 1998

Buffalo, NY, USA




PROGRAM


All sessions will be in the Center for Tomorrow.

RECEPTION/REGISTRATION: Sunday from 4pm to 9pm,
Center For Tomorrow.

8:50--9:00
Welcoming Remarks


SESSION 1: Monday, June 15, Morning
Chair: R. Beigel (Lehigh Univ.)

9:00--9:30
On Membership Comparable Sets,
D. Sivakumar (Univ. Houston)

9:30--10:00
Nonrelativizing Separations,
H. Buhrman (CWI),
L. Fortnow (Univ. Chicago),
T. Thierauf (Univ. Ulm)

10:00--10:30
Two Queries,
H. Buhrman (CWI),
L. Fortnow (Univ. Chicago)

10:30--11:00
Break

Survey Talk 1:
Chair: J. Feigenbaum (AT&T Labs)

11:00--12:15
The Status of P vs. NP and Lower Bounds,
S. Rudich (Carnegie Mellon Univ.)


SESSION 2: Monday, June 15, Afternoon
Chair: S. Rudich (Carnegie Mellon Univ.)

2:00--2:30
Computational Indistinguishability: A Sample Hierarchy,
O. Goldreich (Weizmann Inst. and Mass. Inst. of Tech.),
M. Sudan (Mass. Inst. of Tech.)

2:30--3:00
Proofs of Membership vs. Proofs of Knowledge,
G. Di Crescenzo and R. Impagliazzo (UC San Diego)

3:00--3:30
Approximating the SVP to within a factor
$(1 + 1/(dim^{epsilon}))$ is NP-hard under randomized reductions,
J.-Y. Cai and A. Nerurkar (Univ. at Buffalo)

3:30--4:00 Break

SESSION 3: Monday, June 15, Late Afternoon
Chair: M. Naor (Weizmann Inst.)

4:00--4:30
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.)

4:30--5:00
On Arithmetic Branching Programs,
A. Beimel (Harvard Univ.),
A. Gal (UT Austin)

5:00--5:30
The Satisfiability Problem for Probabilistic Ordered
Branching Programs,
M. Agrawal (IIT Kanpur),
T. Thierauf (Univ. Ulm)


SESSION 4: Tuesday, June 16, Morning
Chair: D. Spielman (Mass. Inst. of Tech.)

9:00--9:30
Isolation, Matching, and Counting,
E. Allender (Rutgers Univ.),
K. Reinhardt (Univ. T\"ubingen)

9:30--10:00
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)

10:00--10:30
Theory of Periodically Specified Problems: Complexity and
Approximability,
M. Marathe (Los Alamos Natl. Lab.),
H. Hunt, D. Rosenkrantz, R. Stearns (Univ. at Albany)

10:30--11:00
Break

Survey Talk 2:
Chair: J. Feigenbaum (AT&T Labs)

11:00--12:15
Formal Models of Computation in Complexity and Coding Theory,
D. Spielman (Mass. Inst. of Tech.)

TUESDAY AFTERNOON: Excursion to Niagara Falls.
Departure at 2pm.


SESSION 5: Wednesday, June 17, Morning
Chair: S. Fenner (Univ. Southern Maine)

9:00--9:30
How to Encode a Logical Structure as an OBDD,
H. Veith (Tech. Univ. Wien)

9:30--10:00
Complete Problems for Promise Classes by Optimal Proof
Systems for Test Sets,
J. K\"obler and J. Messner (Univ. Ulm)

10:00--10:30
Lower Bounds for Computation with Limited Nondeterminism,
H. Klauck (Univ. Frankfurt)

10:30--11:00
Break

Survey Talk 3:
Chair: J. Feigenbaum (AT&T Labs)

11:00--12:15
DNA Computing,
R. Beigel and B. Fu (Lehigh Univ.)


SESSION 6: Wednesday, June 17, Afternoon
Chair: E. Mayordomo (Univ. Zaragoza)

2:00--2:30
Hard Sets are Hard to Find,
H. Buhrman (CWI),
D. van Melkebeek (CWI and Univ. Chicago)

2:30--3:00
On the Resource Bounded Measure of P/poly,
J. K\"obler and W. Lindner (Univ. Ulm)

3:00--3:30
Probabilistic Martingales and BPTIME Classes,
K. Regan (Univ. at Buffalo),
D. Sivakumar (Univ. Houston)

3:30--4:00
Break


SESSION 7: Wednesday, June 17, Late Afternoon
Chair: J. Goldsmith (Univ. Kentucky)

4:00--4:30
Complexity Limitations on Quantum Computation,
L. Fortnow (Univ. Chicago),
J. Rogers (DePaul Univ.)

4:30--5:00
Relationships between quantum and classical space-bounded
complexity classes,
J. Watrous (Univ. Wisconsin at Madison)

5:00--5:30
Uniformly Hard Languages,
R. Downey (Victoria Univ.),
L. Fortnow (Univ. Chicago)

BUSINESS MEETING: From 6pm in Center For Tomorrow.

RUMP SESSION: After the business meeting.


SESSION 8: Thursday, June 18, Morning
Chair: A. Selman (Univ. at Buffalo)

9:00--9:30
Resource-Bounded Measure,
J. Lutz (Iowa State Univ.)

9:30--10:00
Randomness is Hard,
H. Buhrman (CWI) and L. Torenvliet (Univ. Amsterdam)

10:00--10:30
Resource-Bounded Measure and Learnability,
W. Lindner and R. Schuler (Univ. Ulm),
O. Watanabe (Tokyo Inst. of Tech.)

10:30--11:00
Break

Survey Talk 4:
Chair: J. Feigenbaum (AT&T Labs)

11:00--12:15
Complexity Issues in Markov Decision Processes,
J. Goldsmith (Univ. Kentucky),
M. Mundhenk (Univ. Trier)

========================================================================
CONFERENCE FEES By May 29 After May 29

ACM, EATCS, IEEE, or $235 $290
SIGACT Members
Nonmembers $295 $360
Students $115 $140
Extra Proceedings $ 40 $ 40

The registration fee includes lunches, proceedings and all social events.
========================================================================

ADVANCE REGISTRATION FORM

Last name ________________________ First name __________________________
Affiliation ____________________________________________________________
Mailing address ________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
EMail address ____________________ Telephone ___________________________
Homepage _______________________________________________________________
Special dietary needs __________________________________________________
Special accessibility needs ____________________________________________


PAYMENT COMPUTATION

Registration fee $___________
Extra Proceedings (___) $___________
Voluntary contribution $___________

Total $___________


SOCIAL EVENTS

Estimated number of family members (including you) attending.
Family of registrants included FREE:

Welcoming Barbecue ___________
Niagara Falls excursion ___________

METHODS OF PAYMENT

___ Check enclosed ___ Money Order Enclosed

Make check payable to "UB Foundation/CCC'98".
**Do not send cash**

___ VISA ___ American Express
___ Master Card ___ Discover
___ Carte Blanche ___ Diner's Club

Credit Card Number __________________________
Exp. Date ___________________________________
Name on Card ________________________________
Signature ___________________________________

ELECTRONIC REGISTRATION

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.


RETURN REGISTRATION FORM TO:

IEEE Conference on Computational Complexity
University at Buffalo
Office of Conference Operations
120 Center For Tomorrow
Buffalo, NY 14260

CONFERENCE HOMEPAGE

Information about this year's conference is available on the web at
http://www.cs.buffalo.edu/~regan/ccc98/

Information about the Computational Complexity conference is available at
http://cs.utep.edu/longpre/complexity.html

LODGING

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.

1. 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.

http://www.hamptoninn.com/

2. University Inn & Conference Center, 2401 N. Forest Road,
Amherst, NY 14226.
Rate: $62 (double).
(716) 636-7500; FAX (716) 636-8296

http://www.universityinn.com/

We have not arranged for special conference rates at following
alternate hotels. Current single-room rates for June 15 are shown,
and are subject to change. Certain discounts may apply for you.

3. Buffalo/Niagara Marriott,
1340 Millersport Hwy., Amherst, NY 14221.
Rate $109, $109 with AAA.
(716) 689-6900; FAX (716) 689-0483.
Reservations: 1-800-334-4040, 1-800-228-9290

http://www.marriott.com/marriott/BUFNY/

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.

http://www.redroof.com/

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.

http://www.super8.com/

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.


VOLUNTARY CONTRIBUTIONS

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.


SPECIAL DIETARY/ACCESSIBILITY NEEDS

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.

ADDITIONAL PROCEEDINGS

These can be ordered on the registration form and will also
be available for purchase on-site at $40.

CONFERENCE INFORMATION

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.

SOCIAL PROGRAM
Sunday Night: There will be a Welcoming Barbecue, Center For Tomorrow,
4pm to 9pm. Family of registered participants are invited at no extra cost.

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.

Wednesday Night: Business Meeting at 6:00pm in Center For Tomorrow.
Food will be served.


GETTING THERE

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, www.nfttravel.com.

BY AUTOMOBILE:
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.


COMPLEXITY ABSTRACTS

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
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: gasarch@cs.umd.edu.


MESSAGES & ADDITIONAL INFORMATION

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
wjw2@acsu.buffalo.edu.



ACKNOWLEDGMENTS

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.

LOCAL ARRANGEMENTS
Ken Regan (Chair)
Jin-Yi Cai
Alan Selman

PROGRAM COMMITTEE CONFERENCE COMMITTEE
Joan Feigenbaum (Chair) Eric Allender (Chair)
Richard Beigel Richard Beigel
Stephen Fenner Jin-Yi Cai
Judy Goldsmith Anne Condon
Martin Kummer Lance Fortnow
Elvira Mayordomo Steven Homer
Moni Naor Luc Longpr\'e
Steven Rudich Jacobo Tor\'an
Dan Spielman Avi Wigderson
Alan Selman