COMPUTATIONAL COMPLEXITY
Sixteenth Annual IEEE Conference
Sponsored by
The IEEE Computer Society Technical Committee on
Mathematical Foundations of Computing,
In cooperation with
ACM-SIGACT and EATCS
With generous support from
The Depaul School of Computer Science,
Telecommunications & Information Systems
June 18 --- 21, 2001
Chicago, Illinois
PROGRAM
All sessions will be at the DePaul Center, 1 E. Jackson Blvd.
RECEPTION/REGISTRATION:
Starting at 6:00 p.m. at the Cliff Dwellers Club.
MONDAY, June 18
SESSION 1:
Chair: Peter Bro Miltersen (U. of Aarhus)
9:00--9:40
In search of an easy witness: Exponential time vs. probabilistic
polynomial time,
Russell Impagliazzo (University of California, San Diego),
Valentine Kabanets (Institute for Advanced Study),
and Avi Wigderson (Institute for Advanced Study).
9:40--10:20
Towards Uniform AC^0-Isomorphisms,
Manindra Agrawal (IIT Kanpur).
10:20--11:00
Break
11:00--11:30
Universal Traversal Sequences with Backtracking,
Michal Koucky (Rutgers University).
11:30--12:00
Comparing notions of full derandomization,
Lance Fortnow (NEC Research Institute).
SESSION 2:
Chair: Toniann Pitassi (U. Toronto)
1:40--2:10
Monotone Simulations of Nonmonotone Proofs,
Albert Atserias (Universitat Politecnica de Catalunya),
Nicola Galesi (Institute for Advanced Study),
and Pavel Pudlak (IAS & Mathematical Institute of the
Academy of Sciences of the Czech Republic).
2:10--2:40
Space Complexity of Random Formulae in Resolution,
Eli Ben-Sasson (Hebrew University & IAS)
and Nicola Galesi (Institute for Advanced Study).
2:40--3:10
Resolution Complexity of Independent Sets in Random Graphs,
Paul Beame (University of Washington),
Russell Impagliazzo (University of California, San Diego),
and Ashish Sabharwal (University of Washington).
3:10--3:40
Tree Resolution proofs of the Weak Pigeon-Hole Principle,
Stefan Dantchev (BRICS, University of Aarhus & University of London)
and Soren Riis (University of London).
3:40--4:00
Break
SESSION 3:
Chair: D. Sivakumar (IBM Almaden)
4:00--4:30
Separation of NP-completeness notions,
A. Pavan (University at Buffalo)
and Alan L. Selman (University at Buffalo).
4:30--5:00
Bounded Query Functions with Limited Output Bits,
Richard Chang (University of Maryland Baltimore County)
and Jon S. Squire (University of Maryland Baltimore County).
BUSINESS MEETING: Starting at 9:00 p.m.
TUESDAY, June 19
SESSION 4:
Chair: Rainer Schuler (U. Ulm)
9:00--9:30
A Linear Lower Bound On the Unbounded Error Probabilistic
Communication Complexity,
Juergen Forster (Ruhr-Universitat Bochum).
9:30--10:00
Towards proving strong direct product theorems,
Ronen Shaltiel (Hebrew University & IAS).
10:00--10:30
Break
SESSION 5:
Chair: Richard Cleve (U. Calgary)
10:30--11:00
Communication Complexity Lower Bounds by Polynomials,
Harry Buhrman (CWI & University of Amsterdam)
and Ronald de Wolf (CWI and University of Amsterdam).
11:00--11:30
Quantum Algorithms for Element Distinctness,
Harry Buhrman (CWI and University of Amsterdam),
Christoph Durr (Universite Paris-Sud, LRI),
Mark Heiligman (NSA),
Peter Hoyer (BRICS & University of Calgary),
Frederic Magniez (CNRS, Universite Paris-Sud),
Miklos Santha (CNRS, Universite Paris-Sud),
Ronald de Wolf (CWI and University of Amsterdam)
11:30-12:00
Quantum versus Classical Learnability,
Rocco A. Servedio (Harvard University)
and Steven J. Gortler (Harvard University).
RUMP SESSION :
Chair: to be announced
2:00--5:00 Informal session where attendants can present ongoing research.
Specific schedule will be made at the conference.
WEDNESDAY, June 20
SESSION 6:
Chair: Anna Gal (U. Texas, Austin)
9:00--9:40
Uniform Circuits for Division: Consequences and Problems,
Eric Allender (Rutgers University),
David Mix Barrington (University of Massachusetts),
and William Hesse (University of Massachusetts).
9:40--10:10
Affine Projections of Symmetric Polynomials,
Amir Shpilka (Hebrew University).
10:10--10:30
Break.
10:30--11:00
On the Non-Approximability of Boolean Functions by
OBDDs and Read-k-Times Branching Programs,
Beate Bollig (University of Dortmund),
Martin Sauerhoff (University of Dortmund),
and Ingo Wegener (University of Dortmund).
11:00--11:30
Lower Bounds for Approximations by Low Degree Polynomials Over Z_m,
Noga Alon (Tel Aviv University)
and Richard Beigel (Temple University).
11:30--12:00
On the Power of Nonlinear Secret-Sharing,
Amos Beimel (Ben-Gurion University, Israel)
and Yuval Ishai (DIMACS and AT&T Labs).
SESSION 7:
Chair: D. Sivakumar (IBM Almaden)
1:40--2:10
Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure,
Jack Jie Dai (Iowa State University).
2:10--2:40
Hausdorff Dimension in Exponential Time,
Klaus Ambos-Spies (Universitat Heidelberg),
Wolfgang Merkle (Universitat Heidelberg),
Jan Reimann (Universitat Heidelberg),
and Frank Stephan (Universitat Heidelberg).
SESSION 8:
Chair: Salil Vadhan (IAS & Harvard U.)
3:10--3:40
On the Complexity of Approximating the VC Dimension,
Elchanan Mossel (Microsoft Research),
and Christopher Umans (Microsoft Research).
3:40--4:10
Links Between Complexity Theory and Constrained Block Coding,
Larry Stockmeyer (IBM Almaden Research Center)
and Dharmendra S. Modha (Treelet, Inc.).
4:10--4:40
Simple analysis of graph tests for linearity and PCP,
Johan Haastad (Royal Institute of Technology & IAS)
and Avi Wigderson (Hebrew University & IAS).
BANQUET:
Starting at 6:00 p.m. at Maggiano's Little Italy restaurant.
THURSDAY
SESSION 9:
Chair: Madhu Sudan (MIT)
9:00--9:30
Logical operations and Kolmogorov complexity,
Andrei A. Muchnik (Inst. of New Tech., Moscow)
and Nikolai K. Vereshchagin (Moscow State University).
9:30--10:00
Computational Depth,
Luis Antunes (University of Porto),
Lance Fortnow (NEC Research Institute),
and Dieter van Melkebeek (Institute for Advanced Study).
10:00--10:40
Quantum Algorithmic Entropy,
Peter Gacs (Boston University).
10:40--11:00
Break
SESSION 10:
Chair: Uriel Feige (Weizmann Inst.)
11:00--11:30
On separators, segregators and time versus space,
Rahul Santhanam (University of Chicago).
11:30--12:00
Time-Space Tradeoffs in the Counting Hierarchy,
Eric Allender (Rutgers University),
Michal Koucky (Rutgers University),
Detlef Ronneburger (Rutgers University),
Sambuddha Roy (Rutgers University),
and V. Vinay (Indian Institute of Science, Bangalore).
========================================================================
CONFERENCE FEES By May 18 After May 18
ACM, EATCS, IEEE, or $230 $280
SIGACT Members
Nonmembers $280 $350
Students $ 50 $ 70
Extra banquet tickets $ 40 $ 40
Extra Proceedings $ 40 $ 40
The registration fee includes a copy of proceedings and all social events.
========================================================================
ELECTRONIC REGISTRATION
Electronic registration is possible through the web site:
http://www.cs.depaul.edu/Complexity2001
Otherwise, fill the registration form below and return the form by mail
or fax.
ADVANCE REGISTRATION FORM
Last name ________________________ First name __________________________
Affiliation ____________________________________________________________
Mailing address ________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
EMail address ____________________ Telephone ___________________________
Homepage _______________________________________________________________
Special dietary needs __________________________________________________
PAYMENT COMPUTATION
Registration fee $___________
Extra Banquet Tickets (___) $___________
Extra Proceedings (___) $___________
Total $___________
METHODS OF PAYMENT
___ Check enclosed ___ Money Order Enclosed
Make check payable to "DePaul University".
**Do not send cash**
___ VISA
___ Master Card
___ American Express
Credit Card Number __________________________
Exp. Date ___________________________________
Name on Card ________________________________
Signature ___________________________________
RETURN REGISTRATION FORM TO:
Computational Complexity Conference
Suite 401, DePaul University
243 S. Wabash Ave.
Chicago, IL 60604
CONFERENCE HOMEPAGE
Information about this year's conference is available on the Web at
http://www.cs.depaul.edu/Complexity2001.
Information about the Computational Complexity conference is available at
http://www.cs.utep.edu/longpre/complexity.html.
LODGING
Lodging for the conference will be at Palmer House Hilton, at 17
East Monroe Street, Chicago, Illinois 60603.
Rate: \$125 for single or double, \$25 per extra person.
(312) 726-7500.
http://www.hilton.com/hotels/CHIPHHH/
A block of rooms has been reserved for the dates of June 16 to June 21.
For reservations, contact the hotel directly. To get the conference rate,
mention that you want a room reserved for the "16th annual IEEE CCC".
Prices above do not include tax (14.9%).
If you need alternative lodging, please consult the conference web site.
ADDITIONAL PROCEEDINGS
These can be ordered on the registration form and will also be available
for purchase on-site at $40.
CONFERENCE INFORMATION
LOCATION
The conference will take place in room 8005 of the Conference Center
in DePaul Center, 1 E. Jackson Blvd., located two blocks south of the
Palmer House. It is centrally located in the business district of Chicago.
It is walking distance to Chicago's Theater District, the Art Institute,
notable architecture, museums, etc. Other parts of the city can be reached
by cab or extensive public transportation. Maps will be provided.
Average temperature in June is 80F (27C).
SPECIAL SESSION
In celebration of Alan Selman's 60th birthday, there will be a special
session with invited talks starting at 2:00pm, Sunday, June 17th in
DePaul Center 8005. All conference registrants are invited.
Non registrants may also participate, but should inform the conference
organizers. There will be presentations by Juris Hartmanis,
Lane Hemaspaandra, Steve Homer, and Stephen Mahaney. These will be
followed by the opening reception of the Conference.
SOCIAL PROGRAM
Sunday evening: Reception at the Cliff Dwellers Club, 22nd floor,
Borg-Warner Building, 200 S. Michigan Ave., at 6 p.m.
Monday evening: Business meeting at 9 p.m.
at the conference site.
Tuesday afternoon: Rump session at 2 p.m. Otherwise, the afternoon is free.
Attendants can use this time for informal discussions. Tickets for a
variety of events will be available.
Wednesday evening: There will be a banquet at 6 p.m. at Maggiano's
Little Italy restaurant, 516 N. Clark St. Extra tickets are available.
REGISTRATION
Registration will be at the conference site, starting at the Sunday night
reception, and through the conference.
GETTING THERE
BY AIRPLANE:
You can arrive either at O'Hare International Airport or at Midway Airport.
From O'Hare airport, you can reach downtown by taxi, for about $30 plus tip.
You can also take the shuttle, operated by Continental Air Transport
Company. The cost is $16 one-way, $29 roundtrip. The busses pick up
outside the baggage claim areas of terminals 1, 2 and 3. You can also
use Public transportation (subway). Take the Blue Line to downtown.
Get off at the Monroe stop and leave by the Monroe Street exit. Walk east
along Monroe for a couple of blocks.
From Midway airport, you can reach downtown by taxi, for about $20 plus tip.
You can also take the shuttle, operated by Continental Air Transport
Company. The cost is $11 one-way, $20 roundtrip. You can also use
Public transportation (subway). Take the Orange Line to downtown.
Get off at the Madison and Wabash stop. Walk downstairs to Madison
and walk south along Wabash to Palmer House Hilton.
BY OTHER MEANS:
For information on arriving by train or by car, please consult the
conference website.
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 13 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
Messages for attendees can be sent to the DePaul CTI front desk at
telephone 312-362-8381. Electronic messages can be sent to
complexity2001@cs.depaul.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. Generous support was provided by
DePaul School of Computer Science, Telecommunications & Information Systems.
LOCAL ARRANGEMENTS
John Rogers, DePaul Univ.
PROGRAM COMMITTEE CONFERENCE COMMITTEE
Madhu Sudan (Chair) Lance Fortnow (Chair)
Richard Cleve Eric Allender
Uriel Feige Harry Buhrman
Anna Gal Russell Impagliazzo
Peter Bro Milterson Luc Longpre
Toniann Pitassi Jack Lutz
Rainer Schuler Pierre McKenzie
D. Sivakumar Alexander Razborov
Salil Vadhan Madhu Sudan