arvind@utcsri.UUCP (04/10/87)
From: kozen@gvax.cs.cornell.edu (Dexter Kozen)
Subject: structures 87 conference announcement (corrected)
STRUCTURE IN COMPLEXITY THEORY
SECOND ANNUAL CONFERENCE
Sponsored by the IEEE Computer Society Technical Committee on
Mathematical Foundations of Computing
Cornell University
Northeastern University
in cooperation with the
Association for Computing Machinery
Special Interest Group on Automata and Computability Theory
June 16-19, 1987
Cornell University
Ithaca, New York
=============================================================
Advance Registration Form
Please type or print legibly.
Name____________________________________Title________________
(last) (first)
Affiliation__________________________________________________
Address______________________________________________________
City___________________State/Country_______________Zip_______
Phone_________________Netmail________________________________
Arrival date___________________time__________________________
Departure date_________________time__________________________
Registration fee:
Before 6/1 After 6/1
Member IEEE-CS, ACM, EATCS [ ] $150 [ ] $195
Nonmember [ ] $190 [ ] $245
Author/Program Committee [ ] $150 [ ] $195
Full-time Student [ ] $50 [ ] $75
Registration fee includes proceedings, Sunday evening reception,
breakfast and lunch Monday through Thursday, and barbecue.
On-campus accommodations:
# of people: # of nights:
_____standard single @ $21.50/person x _____ = $_____
_____standard double @ $15.75/person x _____ = $_____
_____townhouse single @ $38.00/person x _____ = $_____
_____townhouse double @ $24.00/person x _____ = $_____
[ ] male [ ] female [ ] smoking [ ] nonsmoking
Name of roommate if double occupancy requested
_____________________________________________________________
Please describe any disability requiring special
consideration (e.g., cannot climb stairs, wheelchair, etc.)
_____________________________________________________________
Meals: [ ] kosher [ ] vegetarian
Total enclosed (registration + accommodation): $_____________
Please make checks payable to Cornell University. Submit this
form with your check or money order in US dollars to:
Cornell University Conference Services
Box 3, Robert Purcell Union
Cornell University
Ithaca, New York 14853
==============================================================
Cornell University Conference Services
Box 3, Robert Purcell Union
(607) 255-6290
Structure in Complexity Theory
General Information
LOCATION AND CLIMATE. Ithaca is located in the finger lakes district
of upstate New York, about 225 miles northwest of New York City and
about 150 miles east-southeast of Buffalo. Founded in 1865, Cornell
is the youngest member of the Ivy League. The main campus has been
acclaimed as one of the most beautiful in the world, with over seven
hundred acres of open lawns, manicured pathways, wooded areas, and
distinctive buildings located on a hill overlooking the city of Ithaca
and Cayuga Lake. The waters that feed the lake have created spectacular
gorges and waterfalls on campus and throughout the area. Summer in
Ithaca is beautiful with warm days and cooler evenings. Casual clothing
is in order with a sweater or light jacket for evening and comfortable
walking shoes during the day. The Finger Lakes area is very scenic,
so you may want to bring a camera. We can expect a rain shower every
few days...do bring an umbrella.
TRAVEL INFORMATION. State highways serving Ithaca include Routes 13,
34, 79, 89, and 96. Interstate 81 comes within 35 miles of Ithaca and
the New York State Thruway (Interstate 90) is less than 50 miles to the
north. Driving from the North: Route 81 South to Exit 12 (Cortland).
Route 13 south to N. Triphammer Road exit. Left onto Triphammer Road.
Proceed through traffic lights to stop sign. Left onto Hanshaw Road.
Proceed 1/8 mile to Sunoco Gas Station (on right), right turn onto Pleasant
Grove Road. Proceed one mile on Pleasant Grove, then turn right onto
George Jessup Road. Follow signs to registration area. Driving from
the south: Route 81 north to Route 17 west to Route 96B (Owego) to Ithaca.
At the foot of the hill in downtown Ithaca bear left onto Seneca Street.
Proceed to Route 13 (Meadow Street), turn right. DO NOT FOLLOW SIGNS
TO CORNELL UNIVERSITY. Proceed on 13 to N. Triphammer Road exit, turn
right onto Triphammer Road. Proceed as if coming from the north. Driving
from the west: Route 90 east to 81 south (Syracuse) and proceed as if
approaching from the north. Driving from the east: Take Route 17 west
to Binghamton and proceed as if coming from the south. A map will be
enclosed with your advance registration confirmation letter.
AIRLINE INFORMATION. Ithaca is served by USAir, Piedmont and Brockway
Airlines. The number of seats into Ithaca is about 900 per day. Airport
limosine service will take you from airport to motels or campus living
units. The campus residence halls are about four miles from the airport.
Hancock International Airport in Syracuse is 55 miles from Ithaca and is
served by numerous airlines. Limited bus service from the Syracuse
Airport is provided by Greyhound.
BUS SERVICE. Bus service to Ithaca is provided by Greyhound Bus Lines.
The ride from New York City to Ithaca takes about five hours. Taxi service
is available from the downtown Greyhound terminal to campus (fare
approximately $5).
PARKING AND LOCAL TRANSPORTATION. Parking on campus is by permit only.
Conference parking permits (in peripheral lots) will be available at
registration for $1.00 per car per day. Campus buses make a circuit
of the campus every fifteen minutes. Maps of the bus routes and stops
will be available at registration. Conference name badges will serve
as your bus pass. Parking in the center of campus is available only
on evenings and weekends. The campus is accessible to the handicapped;
please indicate on the registration form that you need assistance.
REGISTRATION. Arriving conference participants should register at the
Robert Purcell Union, North Campus. Campus maps and further information
will be available at registration.
ON-CAMPUS ACCOMMODATIONS. Conference participants are invited to live
on-campus in our residence halls. There are two classes of residence
hall accommodations: standard residence halls and townhouses.
STANDARD RESIDENCE HALLS. While style and architecture vary, each hall
provides comfortable sleeping rooms and spacious lounge areas for
informal gatherings. Both single and double rooms are available;
single rooms are reserved on a first request basis. Families can be
accommodated in a combination of adjoining singles and doubles.
Accommodations include linen (two sheets, pillow case, pillow, blanket
and bedspread) and supplies (bath towel, wash cloth, small bar of soap,
disposable water glass). Housekeeping service is provided daily.
Wake-up service is not provided; participants should bring an alarm
clock or radio. Rate: single $21.50/person, double $15.75/person,
nonrefundable after 6/1.
TOWNHOUSES. The townhouse residence halls are contemporary in style
and decor, and are located on the north edge of campus. Each unit has
two sleeping rooms sharing a living room area, kitchenette and bathroom.
Each sleeping room has two single beds. The townhouses are air-conditioned
and can accommodate single or double occupancy. Townhouse rooms include
the complete linen package. Housekeeping service is provided daily and
an amenities package is included (toothpaste, toothbrush, disposable razor,
shampoo, comb and conditioner) on the day of arrival. The townhouses
are fully carpeted and air-conditioned. Wake-up service is not provided.
Rate: single $38.00/person, double $24.00/person, nonrefundable after 6/1.
Participants staying on for the Logic in Computer Science conference may
keep the same room, and may stay over the weekend; please indicate on the
registration form. Accompanying children under 12 are 1/2 price; with
sleeping bag, free of charge.
OFF-CAMPUS ACCOMMODATIONS. A block of rooms have been reserved at the
Ithaca Holiday Inn for the nights of June 15-18. CONFERENCE PARTICIPANTS
DESIRING OFF-CAMPUS HOUSING MUST MAKE THEIR OWN ARRANGEMENTS. When
making your reservation with the Holiday Inn, be sure to indicate that
you will be attending the 2nd Annual Conference on Structure in Complexity
Theory in order to receive the special conference rate of $50 single,
$60 double. Be sure to make your hotel reservation early, as the block
of rooms is being held only until May 17. Transportation between the
hotel and the conference will not be provided; taxi service is available.
The distance from the conference site is about three miles.
Holiday Inn of Ithaca
2310 North Triphammer Road
Ithaca, New York 14853
(607) 257-3100
MEALS. University cafeteria meals provide a choice of 3-5 entrees, cold
foods, salad bar, several types of salads, a variety of fresh fruits,
vegetables, rolls/breads and desserts with unlimited additional servings.
Breakfast and lunch for Monday, June 22 through Thursday, June 25 are
included in the registration fee. There are a number of good restaurants
within walking distance or a short drive from campus.
SOCIAL PROGRAM.
Monday, June 15, 1987, 7-10 p.m.: An opening mixer, featuring hot and cold hor
s d'oeuvres, drinks, wine and soda will be held at the Johnson Museum of Art.
Admission is included in the conference registration fee.
Thursday, June 18, 1987: A Cornell-style chicken barbecue will be hosted lakes
ide at Taughannock Falls State Park.
UNIVERSITY FACILITIES. At registration, conference participants will be
issued an official University name badge and an identification card. These
will allow participants to use the athletic facilities (tennis courts, golf
course, squash courts, swimming pools, locker rooms, etc.) during public
access hours free of charge. Guests using University swimming pools must
bring their own swim suits and a swim cap for long hair. Conference
participants are welcome to use the libraries, student unions, and museums;
visit the Cornell Plantations with their renowned gardens and plant
collections; or drive to the world-famous Laboratory of Ornithology to
walk through Sapsucker Woods Bird Sanctuary or to view the exhibits on display.
OTHER INFORMATION. The organizers wish to encourage a workshop atmosphere
as much as possible. All participants are invited to volunteer talks on
recent work at the Informal Sessions. Participants are encouraged to bring
preprints of recent papers.
The reception on Monday evening is hosted by the Mathematical Sciences
Institute of Cornell University.
Because of a generous donation made by the Mathematical Sciences Institute
a modest partial reimbursement of travel expenses to the conference may
be possible for full-time students who are not from the Cornell University
area and for attendees from outside the United States. Full-time students
and traveler's from abroad should bring a copy of their flight coupon (or
other verification of travel expenses) to the conference. There will be an
opportunity at that time to register for such reimbursement.
Program Committee: Shafi Goldwasser, Juris Hartmanis, Neil Immerman, Deborah
Joseph, Stephen Mahaney (Chair), Uwe Schoening, Alan Selman, Mike Sipser, Larry
Stockmeyer, Peter van Emde Boas.
Conference chair: Alan Selman, College of Computer Science, Northeastern
University, 360 Huntington Av., Boston, MA 02115; (617) 437-8688;
selman@corwin.ccs.northeastern.edu.
Local Arrangements: Dexter Kozen, Computer Science, Upson Hall, Cornell
University, Ithaca, New York 14853; (607) 255-9209; kozen@gvax.cs.cornell.edu.
=========================================================================
Structure in Complexity Theory
Technical Program
Monday, June 15, 1987
19:00 Reception, hosted by Mathematical Sciences Institute, Cornell
Tuesday, June 16, 1987
Session 1. Chair: Mike Sipser
08:45 Lowness and Probabilistic Complexity Classes. Uwe Schoening,
EWH Koblenz
09:45 On Hiding Information from an Oracle. Martin Abadi, DEC-SRC,
Joan Feigenbaum, Bell Labs, and Joe Kilian, MIT
10:30 Break
11:00 Complexity Characterizations of Attribute Grammar Languages.
Sophocles Ephremidis, Athens, Christos Papadimitriou, Athens
and Stanford, and Martha Sideris, Athens
11:45 Reversal Complexity. Jian-er Chen and Chee-Keng Yap, NYU
12:30 Lunch
Session 2. Chair: Uwe Schoening
14:00 Polynomial Terse Sets. Amihood Amir and William I. Gasarch, Maryland
14:45 A Structural Theorem that Depends Quantitatively on the Complexity
of SAT. Richard Beigel, Johns Hopkins
15:30 Break
16:00 P^NP[log n] and Sparse Turing Complete Sets for NP. Jim Kadin,
Cornell
16:45 The Probabilistic Communication Complexity of Set Intersection.
Georg Schnitger and Balasubramanian Kalyanasundaram, Penn State
Wednesday, June 17, 1987
Session 3. Chair: Neil Immerman
08:45 Near-Testable, P-Cheatable, and P-Terse Sets. Judy Goldsmith,
Deborah Joseph, Wisconsin, and Paul Young, Washington
09:45 Honest Polynomial Reducibilities, Recursively Enumerable Sets,
and the P=?NP Problem. Klaus Ambos-Spies, Dortmund
10:30 Break
11:00 Unprovably Intractable Languages. Kenneth W. Regan, Cornell
11:45 Resource Bounded Baire Category and Small Circuits in Exponential
Space. Jack H. Lutz, Caltech
12:30 Lunch
Session 4. Chair: Peter van Emde Boas
14:00 PSPACE Survives Three-Bit Bottlenecks. Jin-Yi Cai, Yale, and Merrick
L. Furst, CMU
14:45 On Ranking. Lane A. Hemachandra, Cornell
15:30 Break
16:00 On Threshold Circuits and Polynomial Computation. John Reif, Duke
16:45 Informal Talks
21:00 Business Meeting
Thursday, June 18, 1987
Session 5. Chair: Stephen Mahaney
08:45 One-Way Functions, Robustness, and the Non-Isomorphism of
NP-Complete Sets. Juris Hartmanis and Lane Hemachandra, Cornell
09:45 Strong Nondeterministic Reduction: A Technique for Proving
Intractability. Moon Jung Chung, RPI, and B. Ravikumar, Minnesota
10:30 Break
11:00 Polynomial Time Reducibility to a Set of Small Density. Osamu
Watanabe, Tokyo Institute of Technology
11:45 On Sets Reducible to Sparse Sets. Ronald V. Book, UC Santa Barbara,
and Ker-I Ko, SUNY Stony Brook
12:30 Lunch
Session 6. Chair: Alan Selman
14:00 The Complexity of Perfect Zero-Knowledge. Lance Fortnow, MIT
14:45 Some Consequences of the Existence of Pseudorandom Generators.
Eric W. Allender, Rutgers
16:00 Excursion and Barbecue
Friday, June 19, 1987
Session 7. Chair: Juris Hartmanis
08:45 Progress on Collapsing Degrees. Stuart Kurtz, Chicago, Stephen Mahaney,
Bell Labs, and James Royer, Chicago
09:45 A Theory of Oracle Machines. Jonathan F. Buss, Waterloo
10:30 Break
11:00 On Helping by Robust Oracle Machines. Ker-I Ko, SUNY Stony Brook
11:45 The Strong Exponential Hierarchy Collapses. Lane A. Hemachandra,
Cornell
12:30 Lunch
Session 8. Chair: Deborah Joseph
14:00 Expressibility as a Complexity Measure: Results and Directions. Neil
Immerman, Yale
15:00 Characterization of Complexity Classes in Higher-Order Logic. Daniel
Leivant, CMU
15:45 Break
16:15 Complexity Theoretic Algebra I: Vector Spaces over Finite Fields.
Anil Nerode, Cornell and J. B. Remmel, UC San Diego
17:00 Informal Talks