royer@top.cis.syr.edu (Jim Royer) (03/23/91)
STRUCTURE IN COMPLEXITY THEORY
Sixth Annual Conference
Sponsored by the
IEEE Computer Society Technical Committee on
Mathematical Foundations of Computing
and the
University of Chicago
In cooperation with
ACM-SIGACT and EATCS
Sunday, June 30 -- Wednesday, July 3, 1991
University of Chicago, Chicago, Illinois USA
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
ADVANCE REGISTRATION FORM
Last name ______________________ First name __________________________
Affiliation __________________________________________________________
Mailing address ______________________________________________________
______________________________________________________________________
______________________________________________________________________
EMail address __________________________ Telephone ___________________
Special dietary needs ________________________________________________
CONFERENCE FEE $ ____________
ADDITIONAL PROCEEDINGS ($20 each) $ ____________
HOUSING FEE (for the NGRH only) $ ____________
TOTAL ENCLOSED $ ____________
*N.B.* Following this form is all the information on the rates for the
conference, NGRH housing fees, and permitted methods of payment. Please
make checks payable to the ``1991 IEEE Structures Conference.''
CREDIT CARD INFORMATION (if applicable)
VISA / MasterCard (circle one) Exp. Date __________________________
Card Number __________________________________________________________
Signature ___________________________________________________________
HOUSING INFORMATION
Check-in date ____________________ Check-out date ____________________
If sharing a double NGRH room, with whom?
______________________________________________________________________
RETURN THIS FORM TO:
Structures c/o Stuart Kurtz
Department of Computer Science
University of Chicago
1100 E 58th Street
Chicago, IL 60637 USA
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
CONFERENCE FEE
By May 31 After May 31
IEEE, ACM, SIGACT or EATCS members $160.00 $200.00
Nonmembers $210.00 $250.00
Students $90.00 $130.00
This fee includes proceedings and all social events. Additional banquet
tickets will be available at the conference. The fee does *not* include
lunches. In place of catered lunches, the conference will break out at
noontime to take advantage of the variety of restaurants in and around the
campus.
HOUSING
Primary housing is at the New Graduate Residence Hall (NGRH) at the
University of Chicago--1307 East 60th St., Chicago, IL 60637, Phone:
312-702-4000. Rates are $45 night/single, $55 night/double. There is a
secure parking lot available. Rooms are air conditioned, and furnished;
maid service is included. The NGRH is a short walk from the conference
lecture hall. The Conference is handling housing at the NGRH. Include
payment for housing at the NGRH along with your registration.
*Note:* Friday arrivals and Thursday departures can be accommodated.
Secondary housing is available at the Ramada Lakeshore Inn---4900 South
Lakeshore Drive, Chicago, IL 60615, Phone: 312-288-5800. Rates are $69
night (single or double) plus tax. There is a shuttle bus that runs
between the Ramada Inn and the University. Make your reservations by
calling Ramada reservations: 1-800-237-4933 (from outside Illinois), or
1-800-237-7275 (from Illinois). Please mention that you are a participant
in the ``1991 IEEE Structures Conference.''
METHODS OF PAYMENT
Payment can be through VISA, MasterCard, a check in US$ drawn on a US or
Canadian bank, or an international money order in US$ payable through a US
bank, made out to ``IEEE Structures 1991.'' Eurochecks, etc., may be
subject to collection charges which can be $25 or more.
CONFERENCE INFORMATION
LOCATION The University of Chicago is located in Hyde Park, a neighborhood
of Chicago eight miles south of downtown. Hyde Park is a quiet urban
community known for its bookstores and museums.
Chicago's downtown, the Loop, is accessible by train, bus, or cab. The Loop
offers a variety of stores, restaurants, museums, theaters, and other
attractions. The Taste of Chicago, a major outdoor festival featuring
Chicago's restaurants will be running from June 27th--July 4th. There are
many interesting things to do in Chicago, and some of the best are free.
The average high temperature is 82 F (28 C), average low is 61 F (16 C).
Some rain is likely.
SOCIAL PROGRAM There will be a reception on Saturday night (8pm-10pm in the
NGRH), a banquet on Monday night, and business meeting on Tuesday night.
Times and places for the banquet and business meeting will be announced at
the conference.
GETTING THERE
If you are flying to Midway or O'Hare airport, upon arrival look for
``ground transportation'' and take the C&W limousine which goes to the
University and the Ramada Inn. For the NGRH, get off at Ida Noyes Hall at
the University. The NGRH is south across the Midway (a grassy mall), and a
half block east. The limousine is under $15. A taxi from Midway to the
University is typically under $15, but a taxi from O'Hare to the University
is typically over $40.
If you are driving, take I-55 North to Lake Shore Drive. Head south on
Lake Shore Drive. Going to the Ramada Inn, get off at the Hyde Park exit
and the Ramada will be a right turn just after you get off the exit ramp.
Going to the NGRH, continue past the Hyde Park exit to 57th Street Place,
which will be the first light on Lake Shore Drive. Follow 57th Street
Place to the Midway Plaisance. Turn left (south) on Woodlawn, and make the
second left onto 60th Street. The NGRH is one block east on 60th.
MESSAGES & ADDITIONAL INFORMATION
In the event that you need to be contacted at the conference, messages can
be left at 312-702-8070, the Computer Science Department of the University
of Chicago. Further questions can be addressed by email to Stuart Kurtz at
stuart@cs.uchicago.edu.
ACKNOWLEDGMENTS
The Program Committee consisted of Jose Balcazar, Alan Borodin, William
Gasarch, Neil Immerman (chair), Christos Papadimitriou, Walter Ruzzo, Paul
Vitanyi, and Christopher Wilson. The conference committee consists of
Juris Hartmanis, Steve Homer, Tim Long, Stephen Mahaney (chair), James
Royer, Alan Selman, Gerd Wechsung and Paul Young. The local arrangements
chair is Stuart Kurtz.
STRUCTURES ABSTRACTS
This year, brief abstracts on current research will be produced at the
conference. Submission is open to all. For submission information contact
Debbie Joseph, Computer Science Dept., Univ. of Wisconsin, 1210 W. Dayton
St., Madison, WI 53706 USA, Phone: 608-262-1204, Email: abstract@cs.wisc.edu.
PROGRAM
All formal talks will take place in Kent 107. Informal rump sessions are
scheduled from 4:45-5:45pm at the end of each day's formal session.
Evening rump sessions will also be scheduled. All rump session talks will
be in Ryerson 276. *** Please Note *** Talks begin *Sunday* morning.
REGISTRATION: Begins Saturday at 6:00pm in the NGRH.
RECEPTION: Saturday 8:00--10:00pm in the NGRH.
SESSION 1: Sunday, June 30, Morning
Chair: C. Wilson (Oregon)
8:35-9:10 Counting classes are at least as hard as the polynomial-time
hierarchy, S. Toda (U. Electro-Comm.) and M. Ogiwara (Tokyo Inst. Tech.)
9:10-9:45 PP is Closed Under Truth-Table Reductions, L. Fortnow
(Chicago), N. Reingold (Yale)
9:45-10:15 Break
10:15-10:50 A Complexity Theory for Closure Properties, M. Ogiwara (Tokyo
Inst. Tech.), L. Hemachandra (Rochester)
10:50-11:25 Gap-Definable Counting Classes, S. Fenner, L. Fortnow, S.
Kurtz (Chicago)
11:25-12:00 The Power of Witness Reduction, S. Gupta (Ohio State)
12:00-1:45 Lunch Break
SESSION 2: Sunday, June 30, Afternoon.
Chair: W. Gasarch (Maryland)
1:45-2:20 Bounded Queries in Recursion Theory: A Survey, W. Gasarch
(Maryland)
2:20-2:55 On Reductions of NP Sets to Sparse Sets, S. Homer (Boston U.),
L. Longpre (Northeastern)
2:55-2:25 Break
3:25-4:00 Computational Complexity of Small Descriptions, R. Gavalda
(U. Catalunya), O. Watanabe (Tokyo Inst. Tech.)
4:00-4:35 Complexity Classes and Sparse Oracles, D. Bovet (U. Roma),
P. Crescenzi (U. L'Aquila), R. Silvestri (U. Roma)
SESSION 3: Monday, July 1, Morning
Chair: J. Balcazar (U. Catalunya)
8:35-9:10 PSPACE Is Provable By Two Provers in One Round, J. Cai
(Princeton), A. Condon (U. Wisconsin/Madison), R. Lipton (Princeton)
9:10-9:45 On the Success Probability of the Two Provers in One-Round
Proof Systems, U. Feige (Princeton)
9:45-10:15 Break
10:15-10:50 On the Random-Self-Reducibility of Complete Sets, J.
Feigenbaum (AT&T Bell Labs), L. Fortnow (Chicago)
10:50-11:25 One-Way Functions, Hard on Average Problems, and Statistical
Zero-Knowledge Proofs, R. Ostrovsky (MIT)
11:25-12:00 On One Query Self-Reducible Sets, M. Ogiwara (Tokyo Inst.
Tech.), A. Lozano (U. Catalunya)
12:00-1:45 Lunch Break
SESSION 4: Monday, July 1, Afternoon
Chair: P. Vitanyi (CWI)
1:45-2:20 Combinatorics and Kolmogorov Complexity, Ming Li (Waterloo),
Paul Vitanyi (CWI)
2:20-2:55 The Complexity of Malign Ensembles, P. Miltersen (Aarhus)
2:55-2:25 Break
3:25-4:00 Randomized vs. Deterministic Decision Tree Complexity for
Read-Once Boolean Functions, R. Heiman (Princeton, Weizmann Inst.), A.
Wigderson (Princeton, Hebrew U.)
4:00-4:35 On the Monte Carlo Boolean Decision Tree Complexity of
Read-Once Formulae, M. Santha (U. Paris-Sud)
SESSION 5: Tuesday, July 2, Morning
Chair: C. Wilson (Oregon)
8:35-9:10 A Pseudorandom Oracle Characterization of BPP, J. Lutz (Iowa)
9:10-9:45 Notions of Resource-Bounded Category and Genericity, S.
Fenner (Chicago)
9:45-10:15 Break
10:15-10:50 BPP has Subexponential Time Simulations Unless EXPTIME has
Publishable Proofs, L. Babai, L. Fortnow (Chicago), N. Nisan, A. Wigderson
(Hebrew U.)
10:50-11:25 Relating Equivalence and Reducibility to Sparse Sets, E.
Allender (Rutgers), L. Hemachandra (Rochester), M. Ogiwara, O. Watanabe
(Tokyo Inst. Tech.)
11:25-12:00 Exponential Time and Subexponential Time Sets, S. Tang, B. Fu,
T. Lu (Beijing Comp. Inst.)
12:00-1:45 Lunch Break
SESSION 6: Tuesday, July 2, Afternoon
Chair: J. Balcazar (U. Catalunya)
1:45-2:20 Adaptive Logspace and Depth-Bounded Reducibilities, J.
Balcazar (U. Catalunya)
2:20-2:55 Connections between the Complexity of Unique Satisfiability
and the Threshold Behavior of Randomized Reductions, R. Chang (Cornell), J.
Kadin (Maine), P. Rohatigi (Cornell)
2:55-3:25 Break
3:25-4:00 Counting Auxiliary Pushdown Automata and Semi-Unbounded
Arithmetic Circuits, V. Vinay (Indian Inst. Science-Bangalore)
4:00-4:17 Degree Complexity of Boolean Functions and Its Applications
to Relativized Separations, J. Tarui (Rochester)
4:17-4:34 The Perceptron Strikes Back, R. Beigel, N. Reingold, D.
Spielman (Yale)
SESSION 7: Wednesday, July 3, Morning
Chair: W. Gasarch (Maryland)
8:35-9:10 Monotone Separation of Logspace from NC^1, M. Grigni, M.
Sipser (MIT)
9:10-9:45 On Proving Super-logarithmic Depth Lower Bounds via the Direct
Sum in Communication Complexity, M. Karchmer (MIT), R. Raz (Hebrew U.), A.
Wigderson (Princeton, Hebrew U.)
9:45-10:15 Break
10:15-10:50 Superlinear Lower Bounds for Bounded-Width Branching
Programs, D. Barrington (UMass-Amherst), H. Straubing (Boston College)
10:50-11:25 Geometric Arguments Yield Better Bounds for Threshold
Circuits and Distributed Computing, M. Krause (Humboldt U.-Berlin)
11:25-12:00 Lower Bounds with Smaller Domain Size on Concurrent Write
Parallel Machines, J. Edmonds (Toronto)
12:00-1:45 Lunch Break
SESSION 8: Wednesday, July 3, Afternoon
Chair: N. Immerman (UMass-Amherst)
1:45-2:20 Trade-Offs in Descriptive Complexity, N. Immerman
(UMass-Amherst)
2:20-2:55 Capturing Complexity Classes by Fragments of Second Order
Logic, E. Graedel (U. Basel)
2:55-3:25 Break
3:25-4:00 Approximation Properties of NP Minimization Classes, P.
Kolaitis, M. Thakur (UCSC)
4:00-4:35 Approximation and Small-Depth Frege Proofs, S. Bellantoni,
T. Pitassi, A. Urquhart (Toronto)