Computational Complexity Conference
Buffalo, U.S.A., June 15 to 18 1998
A Trip Report, by
V Vinay
CSA, IISC, Bangalore
E-mail: vinay@csa.iisc.ernet.in
June 13th 1998:
My journey to the Computational Complexity conference started at
Rutgers University, courtsey Eric Allender. We were joined by
Klaus Reinhardt and Uli Hertrampf. Eric's plan was to start early
and drive to Buffalo. Seven hours seemed like a reasonable
estimate on the length of the journey. Early in the morning,
Samir Datta joined us. Eric, Klaus, Samir and myself were all in
one car. Uli had rented a car and had a different plan than
ours, so he was on his own. The journey was peppered with with
showers making driving sometimes difficult. And we had rather
bright sunshine otherwise, especially during lunch. Since Eric
had to drive the entire distance, Claire -- Eric's wife -- had
thoughtfully picked up some audio cassettes including some
Sherlock Holmes stories from a local library. The narrator did a
very good job of it and eased the strain of the joruney. We
reached Buffalo by 6pm and reached our respective destinations.
The evening was spent discussing some problems with Samir and
Klaus.
June 14th 1998:
The morning turned out to be windy and rainy. The registration
commenced at 4pm at the "Center for Tommorow." (The quotes are
important. I had innocently asked Eric the previous day,
"ok.. this is the center for tommorow; but why have they not
marked the conference venue?!") By six, most participants had
come in, registered and had food. Some, like me had {\em some}
food! Harry Buhrman had, not surprisingly, a tale to tell; their
plane ran out of fuel while circling for permission to land and
landed elsewhere etc. (The Ulm clique had a much longer story
about flying in/out of US; they suffered in both directions!) At
some point, I took it upon myself to narrate the story to give
Harry some rest!
June 15th 1998:
The conference formally started this morning; Sivakumar was the
first speaker. He spoke on membership comparability sets and
showed some results could be extended using error correcting
codes. I enjoyed the talk. This was followed by two back to back
talks by Harry. Harry is a gifted speaker and his talk was
fun. (Well, Harry hosted me at Amsterdam after the conference.)
In his second talk, he indicated why Thierauf was not a co-author
(unlike in the pervious paper); a nice photograph of Thierauf
cleaning with a broom! Harry's first talk was on the ``first
non-relativising separation''; his second was on the power of two
queries to an NP oracle.
Lunch time was war-time; Richard Chang did not like the claim to
the firstness of non-relativising separation; he reeled out
several examples which Harry rejected on the grounds of
``suspicious access to oracle.'' I tried intervening and the net
effect was very positive: Richard, Siva, Samir and I went to an
Indian restaurant for food later in the day.
In the afternoon, I listened to Beimel talk about arithmetic
branching programs; unfortunately, he could not get beyond the
definitions. He was followed by Thierauf (co-authored by
Manindra) who spoke on satisfiability of certain branching
programs. It was now Thierauf's turn to indicate why Harry was
not a co-author; a cartoon of a Harry snoozing on an equally big
sofa!
June 16th 1998:
The first talk was by Eric. He spoke on an improved upper bound
on Matching (placing it in SPL). About half the talk was spent
on describing the work of Meena and myself on clow sequences and
determinant. I must confess he did a very good job of it; much
better than what we could have hoped to do! Needless to say,
this had a positive effect on my social standing for the rest of
the conference!
This talk was followed by an equally enjoyable talk by Toran on
the hardness of graph isomorphism. He showed that it is at least
NL-hard. Unfortunately, the proceedings do not carry this
result.
The afternoon was spent at Niagara. I could not go onto the
Canadian side to get a good look of the horseshoe, but otherwise
it was nice evening.
June 17th 1998:
Ken Regan gave a wonderful talk on probabilistic martingales.
Ken said it took him about 2 hours per slide and the result was
there to see. Then there were a couple of papers on Quantum
Computing including one by Watrous who got the best student paper
award. Fortnow presented the last talk of the day, where he spoke
about languages having nice properties under mild conditions:
$P=PSPACE$; the lack of oxygen in the Center was obvious as most
people were gasping!
And then we had a Business meeting. Eric, as a conference chair
made a short presentation. The program chair, Joan Feigenbaum,
also spoke at some length. Her nightmare was that most
submissions would turn out to be garbage and then would it be
alright to skip the conference for the year? To be fair, the
number of submissions were low this year, so much so that the
proceedings does not have an editorial! (Ok, I am guessing here.)
And then there was a discussion whether COCO should be a part of
FCRCS (it is every four years). The opinion was mixed and most
did not have any; their main question was whether the conference
could alternate between US and Europe.
We then had elections. The list of candidates was quite long. I
took this opportunity to discuss my daily allowance at Amsterdam
with Harry; but as it turned out, he was popular enough to win. I
was reminded of the Rajya Sabha when one of the losing candidates
was nominated onto the committee.
June 18th 1998:
The last day of the conference. Jack Lutz started the proceedings
with why there was a need for a "new" measure theoretic
approach. All current measure theoretic work is done on the
premise that they can separate some classes. My neighbour, who
has done considerable work in this area, asked me, "Don't you
think this is bogus? It is not going to separate anything!"
By this time, most people were getting ready to leave to their
places. Some had their food packed and most disappeared by
mid-day. The ``survivors'' were invited to an evening party at
Ken Regan's place. About ten of us landed up there.
Ken was the organizing chair and he did a wonderful job of it.
Overall, it was a good enjoyable conference.
June 19th 1998:
We were the first to arrive and the last to leave. LOGCFL eh! We
started immediately after breakfast and Eric drove us back to New
Jersey. On the way, we stopped by a small town that had a
picturesque stream running through it. We had the cassettes, of
course, to keep us glued to an interesting story.
By 5, we reached Eric house. Claire was there to greet us; it was
nice to be back home.